5

という事は承知しています：

head (map (2**) [1..999999])

実際には 2**1 のみを評価し、残りは評価しませんが、私が読んでいる本には次のように書かれています。

head (sort somelist)

使用されるのはそれだけなので、リスト内の最小のアイテムを見つけるだけで済みます。これはどのように作動しますか？私が知る限り、これは私が知っているソート アルゴリズム (バブル ソートなど) では不可能です。

これが機能すると私が考えることができる唯一の方法は、並べ替えアルゴリズムがリスト全体を調べて最小のアイテムを探し、そのアイテムなしでリストを再帰する場合です。私には、これは本当に遅く聞こえます。

これはソート機能の仕組みですか、それとも私が知らない別のソートアルゴリズムがあり、そのような短絡を可能にしますか?

4

3 に答える 3

10

これ：

使用されるのはそれだけなので、リスト内の最小のアイテムを見つけるだけで済みます。

... 本当に、この関数は、並べ替えアルゴリズムが最小の要素を見つけるために必要とする最小限の作業のみを行う必要があると言うべきです。

たとえば、基礎となるソート アルゴリズムとしてクイックソートを使用している場合、 ' quickselect ' として知られる最適な(!) 選択アルゴリズムhead . quicksortと同等であり、これは最悪の場合の線形です。さらに、だけでk -quickselectを実装できます。take k . quicksort

ウィキペディアは、選択アルゴリズムに関するその記事で次のように述べています（私の強調）：

ソートの言語サポートはよりユビキタスであるため、多くの環境では、ソートの後にインデックスを作成するという単純なアプローチが好まれますが、速度は劣ります。実際、遅延言語の場合、ソートが十分に遅延している場合、この単純化されたアプローチにより、ソートされた k 個の最小/最大 (特殊なケースとして最大/最小) に対して可能な限り最高の複雑さを得ることができます。

クイックソートはこのシナリオでうまく機能しますが、Haskell のデフォルトのソート (マージソート) は、ソートされたリストの各要素を返すために厳密に必要以上の作業を行うため、うまく構成できません。Haskellメーリングリストのこの投稿にあるように：

遅延クイックソートは、最初の k 個の最小要素のバッチを生成できます

O(n + k log k) 合計時間 [1]

遅延マージソートが必要な間

O(n + k log n) 合計時間 [2]

詳細については、このブログ投稿をお読みください。

于 2009-12-01T22:23:05.733 に答える
6

GHCi のコマンド ラインで次のように、引数を追跡する比較関数を作成する場合:

> :module + Data.List Debug.Trace
> let myCompare x y = trace ("\tCmp " ++ show x ++ " " ++ show y) $ compare x y

次に、自分で動作を確認できます。

> sortBy myCompare "foobar"

"     Cmp 'f' 'o'
      Cmp 'o' 'b'
      Cmp 'f' 'b'
      Cmp 'a' 'r'
      Cmp 'b' 'a'
a     Cmp 'b' 'r'
b     Cmp 'f' 'o'
      Cmp 'f' 'r'
f     Cmp 'o' 'o'
      Cmp 'o' 'r'
o     Cmp 'o' 'r'
or"

Haskell は、一度に 1 文字ずつ文字列を遅延評価しています。左側の列は各文字が検出されるたびに出力され、右側の列は「trace」によって出力されるように、必要な比較が記録されます。

特に最適化をオンにしてこれをコンパイルすると、異なる結果が得られる可能性があることに注意してください。オプティマイザーは厳密性アナライザーを実行し、文字列全体が出力されることにおそらく気付くので、積極的に評価する方が効率的です。

それから試してください

> head $ sortBy myCompare "foobar"

      Cmp 'f' 'o'
      Cmp 'o' 'b'
      Cmp 'f' 'b'
      Cmp 'a' 'r'
      Cmp 'b' 'a'
'a'

これがどのように機能するかを理解したい場合は、ソート機能のソースコードを調べて、紙の上で「sort "foobar"」を手動で評価してください。

qsort [] = []
qsort (x:xs) = qsort less ++ [x] ++ qsort greater
   where (less, greater) = partition (< x) xs

そう

   qsort ('f':"oobar")
 = qsort ('b':"a") ++ "f" ++ qsort ('o':"or")
 = ("a" ++ "b") ++ "f" ++ qsort ('o':"or")

これで、「qsort」への他の呼び出しを評価することなく、「a」が結果の最初の項目であることを見つけるのに十分なことができました。「パーティション」の呼び出し内に隠されているため、実際の比較は省略しました。実は「partition」も怠け者なので、実はもう一方の「qsort」への引数は、私が示した限りでは評価されていません。

于 2009-12-01T22:12:26.470 に答える
2

今説明したアルゴリズムには、「選択ソート」という特定の名前があります。これはO（n 2）なので、実行できる最速のことではありません。ただし、並べ替えられた配列の最初の「k」要素が必要な場合、複雑さはO（kn）になります。これは、「k」が十分に小さい場合に適しています（例のように）。

関数型言語で純粋関数を使用していることに注意してください。sortコンパイラーは、関数の構成方法を調べることにより、どちらの場合も最適化されたコードを生成できる可能性があります。headとを作成するときに、最小の要素が必要であると簡単に推測できますsort。

于 2009-12-01T21:33:23.200 に答える