1

100 billionさて、並べ替える必要があるアイテムがあるとしましょう。

私たちの記憶は、これらの項目に対して十分な大きさです。

List.sort (Merge sort) を使用して並べ替えることはできますか?

私の懸念には 2 つの部分があります。

  1. この場合、必要な余分なスペースmergesortは問題になりますか?
  2. 不変のデータ構造を使用しているため、並べ替え中にアイテムの新しいリストを繰り返し作成する必要がありますが、100 billionこれは不利になりますか? パフォーマンスの面で？

100 billionアイテムのソートにはarray、この場合使用する必要がありますか?

4

1 に答える 1

2

標準のマージソートの実装は、あまり多くのメモリを再割り当てしないという点で巧妙です（最初に半分に分割しても新しいメモリは割り当てられません）。consesの入力リストが与えられると、最悪の場合（本質的に同一の最良の場合）にリストconsesnが割り当てられます。n * log(n)要素自体の値が入力リスト、中間リスト、および出力リスト間で共有されることを考えると、リストconsによって3ワードのみを割り当てます。つまり、ソートは3 * n * log(n)合計でメモリ内のワードを割り当てます（の場合n = 100 billion、3 * log(n)は110、かなりです。巨大な一定の要因）。

一方、ガベージコレクションは、そのメモリの一部を収集できます。最悪の場合のメモリ使用量は、割り当てられたメモリの合計ではなく、ライブメモリの合計です。実際、再帰サブコールのレイヤー中に作成された中間リストはlog(n)、結果が返される前に収集できるため（最終的mergeに新しいセルが割り当てられるのと同じ速度で死んでしまいます）、このアルゴリズムnは最悪の場合、追加のライブconsセルを保持します。3*n単語または24*nバイトのみを意味します。の場合n = 100 billion、これは、最初に入力リストのスパインを格納するために必要な量と同じ、2.4テラバイトの追加メモリを意味します。

最後に、入力リスト自体への参照を保持しない場合は、ソートされるとすぐに前半を収集して、のn/2代わりに最悪の場合の境界を与えることができますn。また、前半を並べ替えるときに、この前半の前半を収集して、のn/4代わりに最悪の場合の境界を指定できますn/2。この推論で限界に達すると、十分なGC作業があれば、実際にはリストを完全に適切に並べ替えることができると思います-stop＆copy第1世代GCの一定サイズのメモリプールを法として、そのサイズはの時間パフォーマンスに影響を与えますアルゴリズム。

于 2013-03-11T13:51:18.487 に答える