1 メガバイトと 100 万バイトの違いがあるからこそ、解決策が可能です。100 万個の 8 桁の数字を選択するには、2 の 8093729.5 乗の異なる方法があり、重複が許可され、順序が重要ではないため、100 万バイトの RAM しかないマシンには、すべての可能性を表すのに十分な状態がありません。しかし、1M (TCP/IP では 2k 未満) は 1022*1024*8 = 8372224 ビットなので、解決策は可能です。
パート 1、初期ソリューション
このアプローチには 1M 強が必要です。後で 1M に収まるように調整します。
0 から 99999999 までの範囲の数値のコンパクトな並べ替えリストを、7 ビット数値のサブリストのシーケンスとして格納します。最初のサブリストは 0 から 127 までの数字を保持し、2 番目のサブリストは 128 から 255 までの数字を保持します。
各サブリストは、2 ビットのサブリスト ヘッダーとそれに続くサブリスト ボディで構成されます。サブリスト本体は、サブリスト エントリごとに 7 ビットを使用します。サブリストはすべて連結されており、この形式により、1 つのサブリストがどこで終了し、次のサブリストが開始するかを判別できます。完全に入力されたリストに必要な合計ストレージは、2*781250 + 7*1000000 = 8562500 ビットで、これは約 1.021 M バイトです。
可能な 4 つのサブリスト ヘッダー値は次のとおりです。
00空のサブリスト、何も続きません。
01シングルトン。サブリストにはエントリが 1 つしかなく、次の 7 ビットがそれを保持します。
10サブリストには、少なくとも 2 つの個別の数値が含まれています。エントリは、最後のエントリが最初のエントリ以下であることを除いて、減少しない順序で格納されます。これにより、サブリストの終わりを識別できます。たとえば、数値 2,4,6 は (4,6,2) として格納されます。数値 2,2,3,4,4 は (2,3,4,4,2) として格納されます。
11サブリストは、単一の数値の 2 回以上の繰り返しを保持します。次の 7 ビットは数値を示します。次に、値 1 の 7 ビット エントリが 0 個以上続き、その後に値 0 の 7 ビット エントリが続きます。サブリスト本体の長さは、繰り返しの回数を示します。たとえば、数値 12,12 は (12,0) として格納され、数値 12,12,12 は (12,1,0) として格納され、12,12,12,12 は (12,1 ,1,0) など。
空のリストから始めて、一連の数値を読み取り、それらを 32 ビット整数として格納し、新しい数値をその場で並べ替え (おそらくヒープソートを使用)、それらを新しいコンパクトな並べ替え済みリストにマージします。読み取る数値がなくなるまで繰り返し、コンパクト リストをもう一度調べて出力を生成します。
以下の行は、リストのマージ操作が開始される直前のメモリを表しています。「O」は、ソートされた 32 ビット整数を保持する領域です。「X」は、古いコンパクト リストを保持する領域です。「=」記号は、「O」内の各整数に対して 7 ビットのコンパクト リストの拡張スペースです。「Z」はその他のランダムなオーバーヘッドです。
ZZZOOOOOOOOOOOOOOOOOOOOOOOOOO==========XXXXXXXXXXXXXXXXXXXXXXXXXX
マージ ルーチンは、左端の「O」と左端の「X」から読み取りを開始し、左端の「=」から書き込みを開始します。書き込みポインターは、すべての新しい整数がマージされるまで、コンパクト リスト読み取りポインターをキャッチしません。これは、両方のポインターが、サブリストごとに 2 ビット、古いコンパクト リストの各エントリごとに 7 ビット進むためです。新しい数値の 7 ビット エントリ。
パート 2、1M に詰め込む
上記のソリューションを 1M に絞り込むには、コンパクトなリスト形式をもう少しコンパクトにする必要があります。サブリスト タイプの 1 つを削除して、可能なサブリスト ヘッダー値が 3 つだけになるようにします。次に、「00」、「01」、および「1」をサブリストのヘッダー値として使用して、数ビットを節約できます。サブリストのタイプは次のとおりです。
空のサブリスト、何も続きません。
B シングルトン、サブリストにはエントリが 1 つしかなく、次の 7 ビットがそれを保持します。
C サブリストは、少なくとも 2 つの個別の数値を保持します。エントリは、最後のエントリが最初のエントリ以下であることを除いて、減少しない順序で格納されます。これにより、サブリストの終わりを識別できます。たとえば、数値 2,4,6 は (4,6,2) として格納されます。数値 2,2,3,4,4 は (2,3,4,4,2) として格納されます。
D サブリストは、1 つの数値の 2 回以上の繰り返しで構成されます。
私の 3 つのサブリスト ヘッダー値は「A」、「B」、「C」になるため、D タイプのサブリストを表す方法が必要です。
「C[17][101][58]」のように、C タイプのサブリスト ヘッダーの後に 3 つのエントリが続くとします。3 番目のエントリは 2 番目のエントリよりも小さいが、最初のエントリよりも大きいため、これは上記のように有効な C タイプのサブリストの一部になることはできません。このタイプの構成を使用して、D タイプのサブリストを表すことができます。ちょっとした言葉で言えば、「C{00?????}{1??????}{01?????}」は不可能なCタイプのサブリストです。これを使用して、1 つの数字の 3 回以上の繰り返しからなるサブリストを表します。最初の 2 つの 7 ビット ワードは、数値 (以下の「N」ビット) をエンコードし、0 個以上の {0100001} ワードが続き、その後に {0100000} ワードが続きます。
For example, 3 repetitions: "C{00NNNNN}{1NN0000}{0100000}", 4 repetitions: "C{00NNNNN}{1NN0000}{0100001}{0100000}", and so on.
これにより、1 つの数値の正確な 2 回の繰り返しを保持するリストが残ります。別の不可能な C タイプのサブリスト パターン「C{0??????}{11?????}{10??????}」でそれらを表します。最初の 2 ワードの数値の 7 ビットには十分なスペースがありますが、このパターンはそれが表すサブリストよりも長いため、状況が少し複雑になります。最後の 5 つのクエスチョン マークはパターンの一部ではないと見なすことができるので、「C{0NNNNNN}{11N????}10」をパターンとして、「N "s. それは 2 ビット長すぎます。
このパターンでは、2 ビットを借りて、未使用の 4 ビットから返済する必要があります。読み取り時に「C{0NNNNNN}{11N00AB}10」に遭遇すると、「N」の数字の 2 つのインスタンスを出力し、ビット A と B で末尾の「10」を上書きし、読み取りポインターを 2 巻き戻します。ビット。このアルゴリズムでは、各コンパクト リストが 1 回だけ処理されるため、破壊的な読み取りは問題ありません。
単一の数値の 2 回の繰り返しのサブリストを書き込むときは、「C{0NNNNNN}11N00」と書き込み、借用ビット カウンターを 2 に設定します。カウンターがゼロになると「10」が書き込まれます。したがって、次に書き込まれる 2 ビットはスロット A と B に入り、最後に「10」がドロップされます。
「00」、「01」、「1」で表される 3 つのサブリスト ヘッダー値を使用して、最も人気のあるサブリスト タイプに「1」を割り当てることができます。サブリスト ヘッダー値をサブリスト タイプにマップするための小さなテーブルが必要です。また、最適なサブリスト ヘッダー マッピングが何かを知るために、サブリスト タイプごとにオカレンス カウンターが必要です。
すべてのサブリスト タイプが等しく人気がある場合、完全に入力されたコンパクト リストの最悪のケースの最小表現が発生します。その場合、3 つのサブリスト ヘッダーごとに 1 ビットを保存するので、リスト サイズは 2*781250 + 7*1000000 - 781250/3 = 8302083.3 ビットになります。32 ビットのワード境界に切り上げると、8302112 ビットまたは 1037764 バイトになります。
1M から TCP/IP 状態とバッファの 2k を引いた値は 1022*1024 = 1046528 バイトであり、8764 バイトが余ります。
しかし、サブリスト ヘッダー マッピングを変更するプロセスについてはどうでしょうか。以下のメモリ マップで、「Z」はランダム オーバーヘッド、「=」は空き領域、「X」はコンパクト リストです。
ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
左端の「X」から読み始め、左端の「=」から書き始め、右に進みます。それが完了すると、コンパクトリストは少し短くなり、メモリの間違った終わりになります:
ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======
したがって、右にシャントする必要があります。
ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
ヘッダー マッピング変更プロセスでは、サブリスト ヘッダーの最大 1/3 が 1 ビットから 2 ビットに変更されます。最悪の場合、これらはすべてリストの先頭にあるため、開始する前に少なくとも 781250/3 ビットの空きストレージが必要になります。これにより、以前のバージョンのコンパクト リストのメモリ要件に戻ります。 (
これを回避するために、781250 個のサブリストをそれぞれ 78125 個のサブリストからなる 10 個のサブリスト グループに分割します。各グループには、独自の独立したサブリスト ヘッダー マッピングがあります。グループに A から J の文字を使用すると、次のようになります。
ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
各サブリスト グループは、サブリスト ヘッダー マッピングの変更中に縮小または同じままになります。
ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAA=====BBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABB=====CCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCC======DDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDD======EEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEE======FFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFF======GGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGG=======HHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHH=======IJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHI=======JJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ=======
ZZZ=======AAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
マッピング変更中のサブリスト グループの最悪の場合の一時的な拡張は、4k 未満で 78125/3 = 26042 ビットです。完全に入力されたコンパクト リストに 4k プラス 1037764 バイトを許可すると、メモリ マップの "Z" に 8764 - 4096 = 4668 バイトが残ります。
これは、10 個のサブリスト ヘッダー マッピング テーブル、30 個のサブリスト ヘッダーのオカレンス カウント、およびその他のいくつかのカウンター、必要なポインターと小さなバッファー、および関数呼び出しのリターン アドレス用のスタック スペースなど、気付かずに使用したスペースには十分なはずです。ローカル変数。
パート 3、実行するのにどのくらいかかりますか?
空のコンパクト リストでは、1 ビットのリスト ヘッダーが空のサブリストに使用され、リストの開始サイズは 781250 ビットになります。最悪の場合、リストは数値が追加されるたびに 8 ビット増加するため、32 ビットの各数値をリスト バッファーの先頭に配置し、並べ替えてマージするには、32 + 8 = 40 ビットの空き領域が必要です。最悪の場合、サブリスト ヘッダー マッピングを変更すると、2*781250 + 7*エントリ - 781250/3 ビットのスペースが使用されます。
リストに少なくとも 800000 個の番号がある場合、5 回目のマージごとにサブリスト ヘッダー マッピングを変更するというポリシーでは、最悪の場合の実行では、合計約 30M のコンパクト リストの読み取りおよび書き込みアクティビティが必要になります。
ソース:
http://nick.cleaton.net/ramsortsol.html