2

私は C++ のバックグラウンドを持っているので、これを適切に行っているかどうかさえわかりません。しかし、私がやろうとしているのは、クイックソートを作成することですが、リストの長さが特定のしきい値未満の場合は挿入ソートにフォールバックします。これまでのところ、私はこのコードを持っています:

insertionSort :: (Ord a) => [a] -> [a]
insertionSort [] = []
insertionSort (x:xs) = insert x (insertionSort xs)

quickSort :: (Ord a) => [a] -> [a]
quickSort x = qsHelper x (length x)

qsHelper :: (Ord a) => [a] -> Int -> [a]
qsHelper [] _ = []
qsHelper (x:xs) n 
    | n <= 10 = insertionSort xs
    | otherwise =  qsHelper before (length before) ++ [x] ++ qsHelper after (length after)
        where
            before = [a | a <- xs, a < x]
            after = [a | a <- xs, a >= x]

今私が心配しているのは、毎回各リストの長さを計算することです。Haskell が物事を最適化する方法や、上記のようなコードに対する遅延評価の完全な影響を完全には理解していません。しかし、リスト内包の前と後のそれぞれについてリストの長さを計算するのは良いことではないようです。リスト内包表記の実行中に、リスト内包表記で発生した一致の数を抽出する方法はありますか?

つまり、[x | x <- [1,2,3,4,5], x > 3](結果が [4,5]) だった場合、length の呼び出しを使用せずに [4,5] のカウントを取得できますか?

ヘルプ/説明をありがとう！

4

2 に答える 2

6

短い答え：いいえ。

短い答え: はい、偽造できます。import Data.Monoid、 それから

    | otherwise =  qsHelper before lenBefore ++ [x] ++ qsHelper after lenAfter
        where
            (before, Sum lenBefore) = mconcat [([a], Sum 1) | a <- xs, a < x]
            (after, Sum lenAfter) = mconcat [([a], Sum 1) | a <- xs, a >= x]

より良い答え：あなたはしたくありません。

避けるべき一般的な理由は次のlengthとおりです。

  • その実行時間は O(N)
    • とにかく、リストを作成するには O(N) の費用がかかります
  • リストのスパインを厳密にする
    • しかし、リストを並べ替えています。どの要素が最小かを知るために、各要素を (少なくとも部分的に) 評価する必要があります。リストの背骨はすでに厳格に強制されています
  • リストの長さを気にしない場合、それが別のリストまたはしきい値よりも短い/長いかどうかだけでlengthは無駄です:関係なくリストの最後まで歩きます
    • ビンゴ
isLongerThan :: Int -> [a] -> Bool
isLongerThan _ []     = False
isLongerThan 0 _      = True
isLongerThan n (_:xs) = isLongerThan (n-1) xs

quickSort :: (Ord a) => [a] -> [a]
quickSort []     = []
quickSort (x:xs) 
    | not (isLongerThan 10 (x:xs)) = insertionSort xs
    | otherwise =  quickSort before ++ [x] ++ quickSort after
        where
            before = [a | a <- xs, a < x]
            after = [a | a <- xs, a >= x]

ただし、ここでの本当の非効率性は と にbeforeありafterます。どちらもリスト全体をステップ実行し、各要素を と比較しxます。したがって、2 回ステップスルーxsし、各要素をx2 回比較しています。一度だけ行う必要があります。

            (before, after) = partition (< x) xs

partitionData.List にあります。

于 2012-07-31T08:46:57.340 に答える
0

いいえ、リスト内包表記を使用してフィルターを同時に実行し、見つかった要素の数をカウントする方法はありません。しかし、このパフォーマンスへの影響が心配な場合は、最初の方法でリスト内包表記を使用しないでください。リストを 2 回フィルター処理しているため、述語<xとその否定を各要素に適用しています。より良いバリアントは

(before, after) = partition (< x) xs

そこから始めて、関数を書くのは難しくありません

partitionAndCount :: (a -> Bool) -> [a] -> (([a],Int), ([a],Int))

リストを同時に分割してカウントし、返された各リストの要素をカウントします。

((before, lengthBefore), (after, lengthAfter)) = partitionAndCount (< x) xs

これは可能な実装です（少し並べ替えられた型を使用）：

{-# LANGUAGE BangPatterns #-}
import Control.Arrow

partitionAndCount :: (a -> Bool) -> [a] -> (([a], [a]), (Int, Int))
partitionAndCount p = go 0 0
    where go !c1 !c2 [] = (([],[]),(c1,c2))
          go !c1 !c2 (x:xs) = if p x 
                              then first (first (x:))  (go (c1 + 1) c2 xs)
                              else first (second (x:)) (go c1 (c2 + 1) xs)

そして、ここでそれを実際に見ることができます：

*Main> partitionAndCount (>=4) [1,2,3,4,5,3,4,5]
(([4,5,4,5],[1,2,3,3]),(4,4))
于 2012-07-31T08:43:15.403 に答える