1 MB の RAM を備えたコンピューターを使用しており、他のローカル ストレージはありません。これを使用して、TCP 接続で 100 万個の 8 桁の 10 進数を受け入れ、それらを並べ替え、並べ替えたリストを別の TCP 接続で送信する必要があります。
番号のリストには重複が含まれている可能性がありますが、これを破棄してはなりません。コードは ROM に配置されるため、1 MB からコードのサイズを差し引く必要はありません。イーサネット ポートを駆動し、TCP/IP 接続を処理するコードは既にありますが、コードがデータを読み書きするための 1 KB のバッファーを含め、状態データ用に 2 KB が必要です。この問題の解決策はありますか?
質問と回答のソース:
これまでに言及されていないかなり卑劣なトリックが 1 つあります。データを保存する追加の方法はないと想定していますが、厳密にはそうではありません。
問題を回避する方法の 1 つは、次の恐ろしいことを実行することです。これは、いかなる状況でも誰にも試みてはなりません: ネットワーク トラフィックを使用してデータを保存します。いいえ、NAS のことではありません。
次の方法で、数バイトの RAM だけで数値を並べ替えることができます。
COUNTERとVALUE.0ます。Iに、インクリメントCOUNTERして に設定VALUEしmax(VALUE, I)ます。Iルーターに送信します。消しIて繰り返す。にCOUNTER達する1000000と、すべての値が ICMP 要求の絶え間ないストリームに格納されVALUE、最大の整数が含まれるようになります。いくつかを選んthreshold T >> 1000000でください。ゼロに設定COUNTERします。ICMP パケットを受信するたびCOUNTERに、含まれている整数をインクリメントIして、別のエコー要求で送り返しI=VALUEます。一度COUNTER=T、 だけ減分VALUEし1、ゼロにリセットCOUNTERして繰り返します。ゼロにVALUE達すると、最大から最小の順にすべての整数を宛先に送信し、2 つの永続変数 (および一時的な値に必要な少量) に約 47 ビットの RAM しか使用していないはずです。
私はこれが恐ろしいことを知っていますし、あらゆる種類の実際的な問題があり得ることは知っていますが、あなたの何人かを笑わせるか、少なくともあなたを怖がらせるかもしれないと思いました.
問題を解決するいくつかの実用的な C++ コードを次に示します。
メモリの制約が満たされていることの証明:
編集者:この投稿でもブログでも、著者が提供する最大メモリ要件の証拠はありません。値をエンコードするために必要なビット数は、以前にエンコードされた値に依存するため、そのような証明は自明ではありません。著者は、経験的につまずいた最大のエンコード サイズはであり、任意1011732にバッファ サイズを選択したことに注意しています。1013000
typedef unsigned int u32;
namespace WorkArea
{
static const u32 circularSize = 253250;
u32 circular[circularSize] = { 0 }; // consumes 1013000 bytes
static const u32 stageSize = 8000;
u32 stage[stageSize]; // consumes 32000 bytes
...
これら 2 つの配列を合わせると、1045000 バイトのストレージが必要になります。1048576 - 1045000 - 2×1024 = 1528 バイトが残りの変数とスタック スペースに残ります。
Xeon W3520 で約 23 秒で実行されます。次の Python スクリプトを使用して、プログラムの動作を確認できます。プログラム名はsort1mb.exe.
from subprocess import *
import random
sequence = [random.randint(0, 99999999) for i in xrange(1000000)]
sorter = Popen('sort1mb.exe', stdin=PIPE, stdout=PIPE)
for value in sequence:
sorter.stdin.write('%08d\n' % value)
sorter.stdin.close()
result = [int(line) for line in sorter.stdout]
print('OK!' if result == sorted(sequence) else 'Error!')
アルゴリズムの詳細な説明は、次の一連の投稿で見つけることができます。
最初の正解か算術符号化後の正解を見てください。以下にいくつかの楽しみがあるかもしれませんが、100% 防弾ソリューションではありません。
これは非常に興味深い作業であり、別の解決策があります。誰かがその結果を役に立つ (または少なくとも興味深い) と思ってくれることを願っています。
ステージ 1: 初期データ構造、大まかな圧縮方法、基本的な結果
簡単な計算をしてみましょう: 10^6 の 8 桁の 10 進数を格納するために、最初は 1M (1048576 バイト) の RAM が利用可能です。[0;99999999]。したがって、1 つの数値を格納するには 27 ビットが必要です (符号なし数値が使用されると仮定します)。したがって、生ストリームを保存するには、最大 3.5M の RAM が必要になります。実行可能ではないようだと誰かがすでに言っていますが、入力が「十分」であれば、タスクは解決できると思います。基本的には、入力データを圧縮率 0.29 以上で圧縮し、適切にソートするという考え方です。
まず、圧縮の問題を解決しましょう。いくつかの関連するテストがすでに利用可能です:
http://www.theeggeadventure.com/wikimedia/index.php/Java_Data_Compression
「さまざまな形式の圧縮を使用して、100 万個の連続する整数を圧縮するテストを実行しました。結果は次のとおりです。」
None 4000027
Deflate 2006803
Filtered 1391833
BZip2 427067
Lzma 255040
LZMA ( Lempel–Ziv–Markov chain algorithm ) は、継続するのに適しているようです。簡単な PoC を用意しましたが、強調すべき詳細がまだいくつかあります。
添付のコードはPOCであり、最終的な解決策として使用することはできません。いくつかの小さなバッファーを使用して、事前に並べ替えられた数値を最適な方法 (おそらく圧縮) で格納するというアイデアを示しているだけです。LZMA は最終的な解決策として提案されていません。これは、この PoC に圧縮を導入する最速の方法として使用されます。
以下の PoC コードを参照してください (これは単なるデモであり、コンパイルするにはLZMA-Javaが必要になることに注意してください)。
public class MemorySortDemo {
static final int NUM_COUNT = 1000000;
static final int NUM_MAX = 100000000;
static final int BUCKETS = 5;
static final int DICT_SIZE = 16 * 1024; // LZMA dictionary size
static final int BUCKET_SIZE = 1024;
static final int BUFFER_SIZE = 10 * 1024;
static final int BUCKET_RANGE = NUM_MAX / BUCKETS;
static class Producer {
private Random random = new Random();
public int produce() { return random.nextInt(NUM_MAX); }
}
static class Bucket {
public int size, pointer;
public int[] buffer = new int[BUFFER_SIZE];
public ByteArrayOutputStream tempOut = new ByteArrayOutputStream();
public DataOutputStream tempDataOut = new DataOutputStream(tempOut);
public ByteArrayOutputStream compressedOut = new ByteArrayOutputStream();
public void submitBuffer() throws IOException {
Arrays.sort(buffer, 0, pointer);
for (int j = 0; j < pointer; j++) {
tempDataOut.writeInt(buffer[j]);
size++;
}
pointer = 0;
}
public void write(int value) throws IOException {
if (isBufferFull()) {
submitBuffer();
}
buffer[pointer++] = value;
}
public boolean isBufferFull() {
return pointer == BUFFER_SIZE;
}
public byte[] compressData() throws IOException {
tempDataOut.close();
return compress(tempOut.toByteArray());
}
private byte[] compress(byte[] input) throws IOException {
final BufferedInputStream in = new BufferedInputStream(new ByteArrayInputStream(input));
final DataOutputStream out = new DataOutputStream(new BufferedOutputStream(compressedOut));
final Encoder encoder = new Encoder();
encoder.setEndMarkerMode(true);
encoder.setNumFastBytes(0x20);
encoder.setDictionarySize(DICT_SIZE);
encoder.setMatchFinder(Encoder.EMatchFinderTypeBT4);
ByteArrayOutputStream encoderPrperties = new ByteArrayOutputStream();
encoder.writeCoderProperties(encoderPrperties);
encoderPrperties.flush();
encoderPrperties.close();
encoder.code(in, out, -1, -1, null);
out.flush();
out.close();
in.close();
return encoderPrperties.toByteArray();
}
public int[] decompress(byte[] properties) throws IOException {
InputStream in = new ByteArrayInputStream(compressedOut.toByteArray());
ByteArrayOutputStream data = new ByteArrayOutputStream(10 * 1024);
BufferedOutputStream out = new BufferedOutputStream(data);
Decoder decoder = new Decoder();
decoder.setDecoderProperties(properties);
decoder.code(in, out, 4 * size);
out.flush();
out.close();
in.close();
DataInputStream input = new DataInputStream(new ByteArrayInputStream(data.toByteArray()));
int[] array = new int[size];
for (int k = 0; k < size; k++) {
array[k] = input.readInt();
}
return array;
}
}
static class Sorter {
private Bucket[] bucket = new Bucket[BUCKETS];
public void doSort(Producer p, Consumer c) throws IOException {
for (int i = 0; i < bucket.length; i++) { // allocate buckets
bucket[i] = new Bucket();
}
for(int i=0; i< NUM_COUNT; i++) { // produce some data
int value = p.produce();
int bucketId = value/BUCKET_RANGE;
bucket[bucketId].write(value);
c.register(value);
}
for (int i = 0; i < bucket.length; i++) { // submit non-empty buffers
bucket[i].submitBuffer();
}
byte[] compressProperties = null;
for (int i = 0; i < bucket.length; i++) { // compress the data
compressProperties = bucket[i].compressData();
}
printStatistics();
for (int i = 0; i < bucket.length; i++) { // decode & sort buckets one by one
int[] array = bucket[i].decompress(compressProperties);
Arrays.sort(array);
for(int v : array) {
c.consume(v);
}
}
c.finalCheck();
}
public void printStatistics() {
int size = 0;
int sizeCompressed = 0;
for (int i = 0; i < BUCKETS; i++) {
int bucketSize = 4*bucket[i].size;
size += bucketSize;
sizeCompressed += bucket[i].compressedOut.size();
System.out.println(" bucket[" + i
+ "] contains: " + bucket[i].size
+ " numbers, compressed size: " + bucket[i].compressedOut.size()
+ String.format(" compression factor: %.2f", ((double)bucket[i].compressedOut.size())/bucketSize));
}
System.out.println(String.format("Data size: %.2fM",(double)size/(1014*1024))
+ String.format(" compressed %.2fM",(double)sizeCompressed/(1014*1024))
+ String.format(" compression factor %.2f",(double)sizeCompressed/size));
}
}
static class Consumer {
private Set<Integer> values = new HashSet<>();
int v = -1;
public void consume(int value) {
if(v < 0) v = value;
if(v > value) {
throw new IllegalArgumentException("Current value is greater than previous: " + v + " > " + value);
}else{
v = value;
values.remove(value);
}
}
public void register(int value) {
values.add(value);
}
public void finalCheck() {
System.out.println(values.size() > 0 ? "NOT OK: " + values.size() : "OK!");
}
}
public static void main(String[] args) throws IOException {
Producer p = new Producer();
Consumer c = new Consumer();
Sorter sorter = new Sorter();
sorter.doSort(p, c);
}
}
乱数を使用すると、次のようになります。
bucket[0] contains: 200357 numbers, compressed size: 353679 compression factor: 0.44
bucket[1] contains: 199465 numbers, compressed size: 352127 compression factor: 0.44
bucket[2] contains: 199682 numbers, compressed size: 352464 compression factor: 0.44
bucket[3] contains: 199949 numbers, compressed size: 352947 compression factor: 0.44
bucket[4] contains: 200547 numbers, compressed size: 353914 compression factor: 0.44
Data size: 3.85M compressed 1.70M compression factor 0.44
単純な昇順シーケンス (1 つのバケットが使用される) の場合、以下が生成されます。
bucket[0] contains: 1000000 numbers, compressed size: 256700 compression factor: 0.06
Data size: 3.85M compressed 0.25M compression factor 0.06
編集
結論：
ステージ 2: 強化された圧縮、最終結論
前のセクションですでに述べたように、適切な圧縮技術であればどれでも使用できます。したがって、LZMA を取り除き、よりシンプルで優れた (可能であれば) アプローチを採用しましょう。算術コーディング、基数ツリーなどを含む多くの優れたソリューションがあります。
とにかく、シンプルだが便利なエンコーディング スキームは、さらに別の外部ライブラリよりもわかりやすく、気の利いたアルゴリズムを提供します。実際の解決策は非常に簡単です。部分的にソートされたデータを含むバケットがあるため、数値の代わりにデルタを使用できます。
ランダム入力テストは、わずかに良い結果を示しています。
bucket[0] contains: 10103 numbers, compressed size: 13683 compression factor: 0.34
bucket[1] contains: 9885 numbers, compressed size: 13479 compression factor: 0.34
...
bucket[98] contains: 10026 numbers, compressed size: 13612 compression factor: 0.34
bucket[99] contains: 10058 numbers, compressed size: 13701 compression factor: 0.34
Data size: 3.85M compressed 1.31M compression factor 0.34
サンプルコード
public static void encode(int[] buffer, int length, BinaryOut output) {
short size = (short)(length & 0x7FFF);
output.write(size);
output.write(buffer[0]);
for(int i=1; i< size; i++) {
int next = buffer[i] - buffer[i-1];
int bits = getBinarySize(next);
int len = bits;
if(bits > 24) {
output.write(3, 2);
len = bits - 24;
}else if(bits > 16) {
output.write(2, 2);
len = bits-16;
}else if(bits > 8) {
output.write(1, 2);
len = bits - 8;
}else{
output.write(0, 2);
}
if (len > 0) {
if ((len % 2) > 0) {
len = len / 2;
output.write(len, 2);
output.write(false);
} else {
len = len / 2 - 1;
output.write(len, 2);
}
output.write(next, bits);
}
}
}
public static short decode(BinaryIn input, int[] buffer, int offset) {
short length = input.readShort();
int value = input.readInt();
buffer[offset] = value;
for (int i = 1; i < length; i++) {
int flag = input.readInt(2);
int bits;
int next = 0;
switch (flag) {
case 0:
bits = 2 * input.readInt(2) + 2;
next = input.readInt(bits);
break;
case 1:
bits = 8 + 2 * input.readInt(2) +2;
next = input.readInt(bits);
break;
case 2:
bits = 16 + 2 * input.readInt(2) +2;
next = input.readInt(bits);
break;
case 3:
bits = 24 + 2 * input.readInt(2) +2;
next = input.readInt(bits);
break;
}
buffer[offset + i] = buffer[offset + i - 1] + next;
}
return length;
}
このアプローチに注意してください：
完全なコードはここにあります。 BinaryInput と BinaryOutput の実装はここにあります。
最終的な結論
最終的な結論はありません :) 場合によっては、1 つ上のレベルに移動して、メタレベルの観点からタスクを確認することをお勧めします。
この作業に時間を費やすのは楽しかったです。ところで、以下に興味深い回答がたくさんあります。ご清聴ありがとうございました。
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 のコンパクト リストの読み取りおよび書き込みアクティビティが必要になります。
ソース：
ギルマノフの答えは、その仮定において非常に間違っています。100万個の連続する整数の無意味な測定に基づいて推測を開始します。つまり隙がない。これらのランダムなギャップは、どんなに小さくても、本当に悪い考えになります.
自分で試してみてください。100 万個のランダムな 27 ビット整数を取得し、並べ替え、7-Zip、 xz 、任意の LZMA で圧縮します。結果は 1.5 MB を超えています。上の前提は、連番の圧縮です。そのデルタ エンコーディングでも1.1 MB を超えます。気にしないでください。これは圧縮に 100 MB 以上の RAM を使用しています。したがって、圧縮された整数でさえ問題に適合せず、実行時の RAM 使用量を気にする必要はありません。
人々がきれいなグラフィックと合理化に賛成票を投じているのは悲しいことです。
#include <stdint.h>
#include <stdlib.h>
#include <time.h>
int32_t ints[1000000]; // Random 27-bit integers
int cmpi32(const void *a, const void *b) {
return ( *(int32_t *)a - *(int32_t *)b );
}
int main() {
int32_t *pi = ints; // Pointer to input ints (REPLACE W/ read from net)
// Fill pseudo-random integers of 27 bits
srand(time(NULL));
for (int i = 0; i < 1000000; i++)
ints[i] = rand() & ((1<<27) - 1); // Random 32 bits masked to 27 bits
qsort(ints, 1000000, sizeof (ints[0]), cmpi32); // Sort 1000000 int32s
// Now delta encode, optional, store differences to previous int
for (int i = 1, prev = ints[0]; i < 1000000; i++) {
ints[i] -= prev;
prev += ints[i];
}
FILE *f = fopen("ints.bin", "w");
fwrite(ints, 4, 1000000, f);
fclose(f);
exit(0);
}
今ints.binLZMAで圧縮...
$ xz -f --keep ints.bin # 100 MB RAM
$ 7z a ints.bin.7z ints.bin # 130 MB RAM
$ ls -lh ints.bin*
3.8M ints.bin
1.1M ints.bin.7z
1.2M ints.bin.xz
これについて考える 1 つの方法は、組み合わせ論の観点からだと思います。並べ替えられた数の順序付けの可能な組み合わせはいくつあるでしょうか。組み合わせ 0,0,0,....,0 をコード 0、0,0,0,...,1 をコード 1、99999999、99999999、... 99999999 をコード N とすると、 Nとは何ですか？言い換えれば、結果スペースはどのくらいの大きさですか?
これについて考える 1 つの方法は、これが N x M グリッド (N = 1,000,000 および M = 100,000,000) で単調パスの数を見つける問題の全単射であることに注意することです。つまり、幅 1,000,000、高さ 100,000,000 のグリッドがある場合、左下から右上への最短経路はいくつあるでしょうか? もちろん、最短経路では、右または上に移動するだけで済みます (下または左に移動すると、以前に達成した進行が取り消されることになります)。これがどのように数の並べ替え問題の全単射であるかを確認するには、次のことを確認してください。
パス内の水平な脚は、順序付けの数字として想像できます。脚の Y 位置が値を表します。
したがって、パスが単純に最後までずっと右に移動し、次に一番上までジャンプする場合、これは 0,0,0,...,0 の順序と同じです。代わりに、一番上までジャンプしてから右に 1,000,000 回移動する場合、これは 99999999,99999999,..., 99999999 に相当します。1 回右に移動し、次に 1 回上に移動し、次に右に移動するパス、次に 1 回、などを最後まで (その後、必然的に一番上までジャンプします)、0,1,2,3,...,999999 に相当します。
幸いなことに、この問題はすでに解決されています。このようなグリッドには (N + M) (M) 個のパスがあります。
(1,000,000 + 100,000,000) (100,000,000) を選択 ~= 2.27 * 10^2436455
したがって、N は 2.27 * 10^2436455 に等しいため、コード 0 は 0,0,0,...,0 を表し、コード 2.27 * 10^2436455 を表し、一部の変更は 99999999,99999999,..., 99999999 を表します。
0 から 2.27 * 10^2436455 までのすべての数値を格納するには、lg2 (2.27 * 10^2436455) = 8.0937 * 10^6 ビットが必要です。
1 メガバイト = 8388608 ビット > 8093700 ビット
したがって、少なくとも実際には結果を保存するのに十分なスペースがあるようです! もちろん、興味深いのは、数値がストリームインするときにソートを行うことです。294908 ビットが残っているため、これに対する最善のアプローチが与えられているかどうかはわかりません。それぞれの時点で、それが順序付け全体であると想定し、その順序付けのコードを見つけ、新しい番号を受け取ったら前のコードに戻って更新するのが興味深いテクニックだと思います。手で手を振る。
ここでの私の提案は、ダンのソリューションに大きく依存しています
まず、ソリューションは考えられるすべての入力リストを処理する必要があると思います。一般的な回答はこの仮定をしていないと思います（IMOは大きな間違いです）。
可逆圧縮の形式では、すべての入力のサイズが縮小されないことが知られています。
一般的な回答はすべて、余分なスペースを確保するのに十分効果的な圧縮を適用できると想定しています。実際、部分的に完成したリストの一部を非圧縮形式で保持し、並べ替え操作を実行できるようにするのに十分な大きさの余分なスペースの塊です。これはただの悪い仮定です。
このようなソリューションの場合、圧縮方法を知っている人なら誰でも、このスキームではうまく圧縮できない入力データを設計でき、「ソリューション」はスペース不足のために壊れる可能性が高くなります。
代わりに、私は数学的アプローチを取ります。可能な出力は、範囲 0..MAX の要素で構成される長さ LEN のすべてのリストです。ここで、LEN は 1,000,000 で、MAX は 100,000,000 です。
任意の LEN と MAX の場合、この状態をエンコードするために必要なビット数は次のとおりです。
Log2(最大マルチ選択 LEN)
したがって、数値については、受信と並べ替えが完了すると、可能なすべての出力を一意に区別できる方法で結果を格納するために、少なくとも Log2(100,000,000 MC 1,000,000) ビットが必要になります。
これは ~= 988kbです。したがって、実際には結果を保持するのに十分なスペースがあります。この観点から、それは可能です。
[より良い例が存在するため、無意味なとりとめを削除しました...]
ベストアンサーはこちら.
もう1つの良い答えはここにあり、基本的に挿入ソートを関数として使用して、リストを1要素ずつ拡張します（一度に複数の要素を挿入できるように、いくつかの要素と事前ソートをバッファリングし、時間を少し節約します）。コンパクトなステート エンコーディングも使用します。7 ビット デルタのバケットです。
このタスクが可能であるとします。出力の直前に、100 万個の並べ替えられた数値のメモリ内表現があります。そのような表現はいくつありますか? 数値が繰り返される可能性があるため、nCr (choose) は使用できませんが、 multisetsで機能する multichoose という操作があります。
したがって、理論的には、並べ替えられた数値のリストの適切な (十分な) 表現を考え出すことができれば、可能かもしれません。たとえば、非常識な表現には、10MB のルックアップ テーブルまたは数千行のコードが必要になる場合があります。
ただし、「1M RAM」が 100 万バイトを意味する場合、明らかに十分なスペースがありません。メモリを 5% 増やすと理論的に可能になるという事実は、表現が非常に効率的である必要があり、おそらく正気ではないことを示唆しています。
(私の最初の答えは間違っていました。悪い計算で申し訳ありません。ブレークの下を参照してください。)
これはどう？
最初の 27 ビットは、表示された最小の数値を格納し、次に表示された次の数値との差を次のようにエンコードして格納します: 差の格納に使用されるビット数を格納するための 5 ビット、次に差。00000 を使用して、その番号をもう一度見たことを示します。
これが機能するのは、より多くの数値が挿入されるにつれて、数値間の平均差が小さくなるため、より多くの数値を追加するにつれて、より少ないビットを使用して差を保存するためです。これはデルタリストと呼ばれるものだと思います。
私が考えることができる最悪のケースは、すべての数字が等間隔 (100 ずつ) に配置されていることです。たとえば、0 が最初の数字であると仮定します。
000000000000000000000000000 00111 1100100
^^^^^^^^^^^^^
a million times
27 + 1,000,000 * (5+7) bits = ~ 427k
救助にReddit！
それらを並べ替えるだけなら、この問題は簡単です。見た数字を保存するには 122k (100 万ビット) かかります (0 が見られた場合は 0 番目のビット、2300 が見られた場合は 2300 番目のビット、など)。
数値を読み取ってビット フィールドに格納し、カウントを維持しながらビットをシフト アウトします。
しかし、あなたが見た数を覚えておく必要があります。上記のサブリストの回答に触発されて、このスキームを思いつきました。
1 ビットを使用する代わりに、2 ビットまたは 27 ビットを使用します。
これはうまくいくと思います: 重複がなければ、244k のリストがあります。最悪の場合、各数字が 2 回表示されます (1 つの数字が 3 回表示されると、リストの残りが短くなります)。これは、50,000 が 1 回以上表示され、950,000 項目が 0 回または 1 回表示されたことを意味します。
50,000 * 27 + 950,000 * 2 = 396.7k.
次のエンコーディングを使用すると、さらに改善できます。
0 はその数字を見たことがないことを意味します 10 は一度見たことがあることを意味します 11 は数え続ける方法です
これは、平均して 280.7k のストレージになります。
編集: 私の日曜日の朝の数学は間違っていました。
最悪の場合、500,000 個の数字が 2 回表示されるため、計算は次のようになります。
500,000 *27 + 500,000 *2 = 1.77M
代替エンコーディングにより、平均ストレージは
500,000 * 27 + 500,000 = 1.70M
: (
この問題には、考えられるすべての入力に対して 1 つの解決策があります。浮気。
どのような種類のコンピュータを使用していますか? 他の「通常の」ローカルストレージがない場合がありますが、たとえばビデオ RAM はありますか? 1 メガピクセル x 32 ビット/ピクセル (たとえば) は、必要なデータ入力サイズにかなり近いです。
(低解像度または低色深度の画面モードを選択した場合、使用可能なシステム RAM を拡張するために VRAM を「借りる」ことができる古いAcorn RISC PCのメモリに主に尋ねます!)。これは、通常の RAM が数 MB しかないマシンではかなり役に立ちました。
Radix Treeを試してみます。データをツリーに格納できる場合は、順序どおりにトラバースしてデータを送信できます。
これを 1MB に収まるかどうかはわかりませんが、試してみる価値はあると思います。
10^8 の範囲には 10^6 の値があるため、平均して 100 コード ポイントごとに 1 つの値があります。N 番目の点から (N+1) 番目の点までの距離を格納します。重複値のスキップは 0 です。これは、スキップが保存するのに平均 7 ビット弱が必要であることを意味します。
これらのスキップは、ハフマン エンコーディングなどによって、ビットストリームにエンコードする必要があります。挿入は、ビットストリームを反復し、新しい値の後に書き換えることによって行われます。暗黙の値を反復して書き出すことによって出力します。実用性のために、たとえば、それぞれ 10^4 コード ポイント (および平均 100 個の値) をカバーする 10^4 リストとして実行することをお勧めします。
スキップの長さにポアソン分布 (平均 = 分散 = 100) を仮定することにより、ランダム データの優れたハフマン ツリーをアプリオリに構築できますが、実際の統計を入力に保持し、対処する最適なツリーを生成するために使用できます。病理学的症例。
基数ツリーは「プレフィックス圧縮」を利用するため、基数ツリー表現はこの問題の処理に近づくでしょう。しかし、単一のノードを 1 バイトで表現できる基数ツリー表現を想像するのは困難です。おそらく 2 つが限界です。
しかし、データがどのように表現されているかに関係なく、一度ソートされると、プレフィックス圧縮された形式で格納できます。この場合、数値 10、11、および 12 は、たとえば 001b、001b、001b で表され、1 の増分を示します。前の番号から。おそらく、10101b は 5 の増分、1101001b は 9 の増分などを表します。
解決策は、ビデオエンコーディングの手法、つまり離散コサイン変換を組み合わせることだと思います。デジタルビデオでは、ビデオの明るさや色の変化を110 112 115 116などの通常の値として記録するのではなく、それぞれが最後から差し引かれます（ランレングスエンコーディングと同様）。110 112115116は11023 1になります。値、2 3 1は、元の値よりも少ないビットを必要とします。
したがって、入力値がソケットに到着したときにそれらのリストを作成するとします。各要素には、値ではなく、その前の要素のオフセットを格納しています。並べ替えるときに、オフセットは正になるだけです。ただし、オフセットは10進数の8桁の幅で、3バイトに収まる可能性があります。各要素を3バイトにすることはできないため、これらをパックする必要があります。各バイトの最上位ビットを「継続ビット」として使用できます。これは、次のバイトが数値の一部であり、各バイトの下位7ビットを組み合わせる必要があることを示します。重複の場合はゼロが有効です。
リストがいっぱいになると、数値は互いに近づくはずです。つまり、次の値までの距離を決定するために、平均して1バイトだけが使用されます。便利な場合は7ビットの値と1ビットのオフセットですが、「継続」値に8ビット未満を必要とするスイートスポットがある場合があります。
とにかく、私はいくつかの実験をしました。私は乱数ジェネレーターを使用しており、100万個のソートされた8桁の10進数を約1279000バイトに収めることができます。各数値間の平均スペースは一貫して99です。
public class Test {
public static void main(String[] args) throws IOException {
// 1 million values
int[] values = new int[1000000];
// create random values up to 8 digits lrong
Random random = new Random();
for (int x=0;x<values.length;x++) {
values[x] = random.nextInt(100000000);
}
Arrays.sort(values);
ByteArrayOutputStream baos = new ByteArrayOutputStream();
int av = 0;
writeCompact(baos, values[0]); // first value
for (int x=1;x<values.length;x++) {
int v = values[x] - values[x-1]; // difference
av += v;
System.out.println(values[x] + " diff " + v);
writeCompact(baos, v);
}
System.out.println("Average offset " + (av/values.length));
System.out.println("Fits in " + baos.toByteArray().length);
}
public static void writeCompact(OutputStream os, long value) throws IOException {
do {
int b = (int) value & 0x7f;
value = (value & 0x7fffffffffffffffl) >> 7;
os.write(value == 0 ? b : (b | 0x80));
} while (value != 0);
}
}
1M の RAM を搭載したコンピューターを使用しており、他にローカル ストレージはありません
別のチート方法: 代わりに非ローカル (ネットワーク) ストレージを使用し (質問はこれを排除しません)、単純なディスクベースのマージソート (またはメモリ内でソートするのに十分な RAM) を使用できるネットワーク サービスを呼び出すことができます。 100 万個の数字を受け入れるだけで済みます)。既に与えられた (非常に巧妙な) ソリューションは必要ありません。
これは不正行為である可能性がありますが、現実の問題の解決策を探しているのか、それともルールの曲げを誘うパズルを探しているのかは明らかではありません...後者の場合、単純な不正行為は複雑な問題よりも良い結果をもたらす可能性がありますしかし、「本物の」ソリューション（他の人が指摘したように、圧縮可能な入力に対してのみ機能します）。
HNスレッドからのGoogleの（悪い）アプローチ。RLE スタイルのカウントを格納します。
最初のデータ構造は '99999999:0' (すべてゼロ、数字は表示されていません) であり、3,866,344 という数字が表示されるとします。データ構造は '3866343:0,1:1,96133654:0' になります。数字は常にゼロビットの数と「1」ビットの数の間で交互に表示されるため、奇数が0ビットを表し、偶数が1ビットを表すと仮定できます。これは (3866343,1,96133654) になります。
彼らの問題は重複をカバーしていないようですが、重複に「0:1」を使用しているとしましょう。
大きな問題 #1: 1M の整数の挿入には時間がかかります。
大きな問題 #2: すべての単純なデルタ エンコーディング ソリューションと同様に、一部のディストリビューションはこの方法ではカバーできません。たとえば、距離が 0:99 の 1m 整数 (例: それぞれ +99)。同じことを考えますが、ランダムな距離は 0:99の範囲です。(注: 99999999/1000000 = 99.99)
Google のアプローチは価値がなく (遅い)、正しくもありません。しかし、彼らを弁護するために、彼らの問題は少し異なっていたかもしれません。
I would exploit the retransmission behaviour of TCP.
This assumes some kind of benefit of buckets or multiple passes.
Probably by sorting the batches/buckets and merging them. -> radix trees
Use this technique to accept and sort the first 80% then read the last 20%, verify that the last 20% do not contain numbers that would land in the first 20% of the lowest numbers. Then send the 20% lowest numbers, remove from memory, accept the remaining 20% of new numbers and merge.**
すべての数値を取得する前に、ネットワーク スタックを操作して、並べ替えられた順序で数値を送信することができます。1M のデータを送信すると、TCP/IP はそれを 1500 バイトのパケットに分割し、ターゲットに順番にストリーミングします。各パケットにはシーケンス番号が与えられます。
これは手作業で行うことができます。RAM がいっぱいになる直前に、持っているものをソートしてリストをターゲットに送信できますが、各番号のシーケンスに穴を残します。次に、シーケンス内のこれらの穴を使用して、数字の 2 番目の 1/2 を同じ方法で処理します。
遠端のネットワーク スタックは、アプリケーションに渡す前に、結果のデータ ストリームを順番に組み立てます。
ネットワークを使用してマージソートを実行しています。これは完全なハックですが、以前にリストされた他のネットワーク ハックに触発されました。
ソートされた配列を表すには、最初の要素と隣接する要素間の差を格納するだけです。このようにして、最大 10^8 まで合計できる 10^6 要素のエンコードに関心があります。これをDとしましょう。Dの要素をエンコードするには、ハフマン コードを使用できます。ハフマン符号の辞書は外出先で作成でき、ソートされた配列に新しい項目が挿入されるたびに配列が更新されます (挿入ソート)。新しいアイテムのために辞書が変更された場合、新しいエンコーディングに一致するように配列全体を更新する必要があることに注意してください。
Dの各要素をエンコードするための平均ビット数は、一意の各要素の数が等しい場合に最大化されます。Dの要素d1、d2、...、dNがそれぞれF回出現するとします。その場合 (最悪の場合、入力シーケンスに 0 と 10^8 の両方がある)、
sum(1<= i <= N ) F . ディ= 10^8
どこ
sum(1<= i <= N ) F = 10^6、またはF =10^6/ Nで、正規化された頻度はp = F /10^=1/ Nになります。
平均ビット数は -log2(1/ P ) = log2( N ) になります。このような状況では、Nを最大化するケースを見つける必要があります。これは、0 から始まるdiの連続した数がある場合、つまりdi = i -1 の場合に発生します。したがって、
10^8= sum(1<= i <= N ) F . di = sum(1<= i <= N ) (10^6/ N ) (i-1) = (10^6/ N ) N ( N -1)/2
すなわち
N <= 201。この場合、平均ビット数は log2(201)=7.6511 です。これは、ソートされた配列を保存するために入力要素ごとに約 1 バイトが必要であることを意味します。これは、 Dが一般に 201 を超える要素を持つことができないという意味ではないことに注意してください。Dの要素が均一に分散されている場合、201 を超える一意の値を持つことはできないということです。
この種の問題に対する一般化された解決策は次のとおりです。
取ったアプローチは以下の通り。このアルゴリズムは、32 ビット ワードの単一バッファで動作します。次の手順をループで実行します。
最後の反復からの圧縮データで満たされたバッファーから始めます。バッファはこんな感じ
|compressed sorted|empty|
圧縮および非圧縮の両方で、このバッファーに格納できる数値の最大量を計算します。バッファーをこれら 2 つのセクションに分割します。圧縮データ用のスペースから始まり、非圧縮データで終わります。バッファは次のようになります
|compressed sorted|empty|empty|
圧縮されていないセクションに、並べ替える番号を入力します。バッファは次のようになります
|compressed sorted|empty|uncompressed unsorted|
インプレース ソートで新しい番号をソートします。バッファは次のようになります
|compressed sorted|empty|uncompressed sorted|
圧縮されたセクションの前の繰り返しから既に圧縮されているデータを右揃えにします。この時点で、バッファは分割されます
|empty|compressed sorted|uncompressed sorted|
圧縮されたセクションでストリーミング解凍-再圧縮を実行し、圧縮されていないセクションの並べ替えられたデータをマージします。古い圧縮セクションは、新しい圧縮セクションが大きくなるにつれて消費されます。バッファは次のようになります
|compressed sorted|empty|
この手順は、すべての番号がソートされるまで実行されます。
もちろん、このアルゴリズムは、実際に何が圧縮されるかを実際に知る前に、新しい並べ替えバッファーの最終的な圧縮サイズを計算できる場合にのみ機能します。次に、実際の問題を解決するのに十分な圧縮アルゴリズムが必要です。
使用されるアプローチでは、3 つのステップが使用されます。まず、アルゴリズムは常に並べ替えられたシーケンスを保存するため、代わりに連続するエントリ間の違いのみを保存できます。それぞれの差は [0, 99999999] の範囲にあります。
これらの違いは、単項ビットストリームとしてエンコードされます。このストリームの 1 は「アキュムレータに 1 を追加する」ことを意味し、A 0 は「アキュムレータをエントリとして発行し、リセットする」ことを意味します。したがって、差 N は N 個の 1 と 1 個の 0 で表されます。
すべての差の合計は、アルゴリズムがサポートする最大値に近づき、すべての差の数は、アルゴリズムに挿入された値の量に近づきます。これは、ストリームが最後に最大値 1 とカウント 0 を含むことを期待していることを意味します。これにより、ストリーム内の 0 と 1 の予想確率を計算できます。つまり、0count/(count+maxval)の確率は であり、1 の確率は ですmaxval/(count+maxval)。
これらの確率を使用して、このビットストリームの算術コーディング モデルを定義します。この算術コードは、この量の 1 と 0 を最適なスペースに正確にエンコードします。このモデルが中間ビットストリームに使用するスペースは、次のように計算できますbits = encoded * log2(1 + amount / maxval) + maxval * log2(1 + maxval / amount)。アルゴリズムに必要な合計スペースを計算するには、encodedamount に等しく設定します。
途方もない量の反復を必要としないようにするために、バッファに小さなオーバーヘッドを追加できます。アルゴリズムの最大の時間コストは、各サイクルの算術コーディングの圧縮と解凍であるため、これにより、少なくともこのオーバーヘッドに収まる数の量でアルゴリズムが動作することが保証されます。
それに加えて、ブックキーピング データを格納し、算術コーディング アルゴリズムの固定小数点近似のわずかな不正確さを処理するために、いくらかのオーバーヘッドが必要ですが、合計で、アルゴリズムは、格納できる追加のバッファーがあっても 1 MiB のスペースに収まります。 8000 個の数字、合計 1043916 バイトのスペース。
アルゴリズムの (小さな) オーバーヘッドを削減する以外に、より小さな結果を得ることは理論的に不可能なはずです。最終結果のエントロピーだけを含めるには、1011717 バイトが必要です。効率のために追加された余分なバッファを差し引くと、このアルゴリズムは最終結果 + オーバーヘッドを格納するために 1011916 バイトを使用しました。
入力ストリームを数回受信できる場合、これははるかに簡単になります (それに関する情報はありません。アイデアと時間パフォーマンスの問題です)。
次に、小数値を数えることができます。カウントされた値を使用すると、出力ストリームを簡単に作成できます。値をカウントして圧縮します。入力ストリームに何が含まれるかによって異なります。
入力ストリームを数回受信できれば、これははるかに簡単になります（それに関する情報、アイデア、および時間パフォーマンスの問題はありません）。次に、10進値を数えることができます。カウントされた値を使用すると、出力ストリームを簡単に作成できます。値を数えて圧縮します。これは、入力ストリームに何が含まれるかによって異なります。
秘訣は、整数のマルチセットであるアルゴリズムの状態を、"increment counter"="+" と "output counter"="!" の圧縮ストリームとして表現することです。文字。たとえば、セット {0,3,3,4} は、"!+++!!+!" の後に任意の数の "+" 文字が続く形式で表されます。マルチセットを変更するには、文字をストリーム アウトし、一度に圧縮解除される量を一定に保ち、その場で変更を加えてから、圧縮形式でストリーミングします。
詳細
最終セットには正確に 10^6 個の数字があることがわかっているため、最大で 10^6 個の "!" が存在します。文字。また、範囲のサイズが 10^8 であることもわかっています。つまり、最大 10^8 の "+" 文字があることを意味します。10^8 の "+" の間に 10^6 の "!" を配置できる方法の数は で(10^8 + 10^6) choose 10^6あり、特定の配置を指定すると~0.965 MiB ` のデータが必要になります。ぴったりフィットします。
割り当てを超えることなく、各キャラクターを独立して扱うことができます。「+」文字は「!」文字のちょうど 100 倍あります。これは、依存関係があることを忘れると、各文字が「+」である確率が 100:1 に単純化されます。100:101 のオッズは、1 文字あたり ~0.08 ビットに対応し、ほぼ同じ合計~0.965 MiBになります (依存関係を無視すると、この場合、わずか12 ビットのコストしかかかりません!)。
既知の事前確率で独立した文字を格納する最も簡単な手法は、ハフマン コーディングです。非現実的なほど大きなツリーが必要であることに注意してください (10 文字のブロックのハフマン ツリーのブロックあたりの平均コストは約 2.4 ビットで、合計で約 2.9 Mib になります。20 文字のブロックのハフマン ツリーのブロックあたりの平均コストは約 3 ビットで、合計で 1.8 MiB になります。おそらく 100 程度のサイズのブロックが必要になるでしょう。これは、これまでに存在したすべてのコンピューター機器が格納できるよりも多くのノードがツリー内にあることを意味します。 ）。ただし、ROM は技術的には問題に応じて「無料」であり、ツリーの規則性を利用する実用的なソリューションは本質的に同じように見えます。
擬似コード
これらの数値について何も知らない場合、次の制約によって制限されます。
これらの仮定が成り立つ場合、少なくとも 26,575,425 ビットのストレージ (3,321,929 バイト) が必要になるため、タスクを実行する方法はありません。
あなたのデータについて教えてください。
現在、1MB の RAM のみで 8 桁範囲の入力のすべての可能なケースをカバーする、実際のソリューションを目指しています。注: 作業は進行中です。明日も続きます。ソートされた int のデルタの算術コーディングを使用すると、1M のソートされた int の最悪のケースでは、エントリあたり約 7 ビットのコストがかかります (99999999/1000000 は 99 であり、log2(99) はほぼ 7 ビットであるため)。
しかし、7 ビットまたは 8 ビットにするには、1m の整数をソートする必要があります。シリーズが短いほどデルタが大きくなるため、要素あたりのビット数が多くなります。
私はできるだけ多くのデータを取り、(ほぼ) その場で圧縮することに取り組んでいます。250K に近い int の最初のバッチには、それぞれせいぜい約 9 ビットが必要です。したがって、結果は約 275KB かかります。残りの空きメモリで数回繰り返します。次に、それらの圧縮されたチャンクを解凍-マージ-インプレース-圧縮します。これはかなり難しいですが、可能です。おもう。
マージされたリストは、整数あたり 7 ビットの目標にどんどん近づいていきます。しかし、マージ ループを何回反復するかはわかりません。おそらく3。
しかし、算術コーディングの実装の不正確さにより、それが不可能になる可能性があります。この問題が発生する可能性があるとすれば、非常にタイトです。
ボランティアはいますか？
1 MB - 3 KB RAM = 2^23 - 3*2^13 ビット = 8388608 - 24576 = 8364032 ビットが利用可能です。
10^8 の範囲で 10^6 の数値が与えられます。これにより、平均ギャップは ~100 < 2^7 = 128 になります。
最初に、すべてのギャップが < 128 である場合に、数値がかなり均等に配置されるという単純な問題を考えてみましょう。これは簡単です。最初の数値と 7 ビットのギャップを保存するだけです。
(27 ビット) + 10^6 7 ビット ギャップ数 = 7000027 ビットが必要
繰り返される数字のギャップは 0 であることに注意してください。
しかし、ギャップが 127 より大きい場合はどうなるでしょうか。
OK、127 未満のギャップ サイズが直接表現されているとしましょう。ただし、127 のギャップ サイズの後に、実際のギャップ長の連続した 8 ビット エンコーディングが続きます。
10xxxxxx xxxxxxxx = 127 .. 16,383
110xxxxx xxxxxxxx xxxxxxxx = 16384 .. 2,097,151
等
この数値表現はそれ自体の長さを表すことに注意してください。これにより、次のギャップ番号がいつ始まるかがわかります。
小さなギャップが 127 未満であるため、これにはまだ 7000027 ビットが必要です。
最大 (10^8)/(2^7) = 781250 23 ビットのギャップ数が存在する可能性があり、余分な 16*781,250 = 12,500,000 ビットが必要になり、これは多すぎます。よりコンパクトでゆっくりと増加するギャップの表現が必要です。
ギャップの平均サイズは 100 なので、それらを [100, 99, 101, 98, 102, ..., 2, 198, 1, 199, 0, 200, 201, 202, ...] のように並べ替えて、これにインデックスを付けると、 「00」で区切られた数字を持つ、ゼロのペアのない密なバイナリ フィボナッチ ベース エンコーディング (たとえば、11011=8+5+2+1=16) を使用すると、ギャップ表現を十分に短く保つことができると思いますが、より多くの分析。
ここでは、ソートは二次的な問題です。他の人が言ったように、整数を格納するだけでは難しく、数値ごとに 27 ビットが必要になるため、すべての入力で機能するわけではありません。
これについての私の見解は次のとおりです。連続する (ソートされた) 整数の違いのみを保存します。それらはおそらく小さいからです。次に、入力数値ごとに 2 ビットを追加するなどの圧縮スキームを使用して、数値が格納されるビット数をエンコードします。何かのようなもの：
00 -> 5 bits
01 -> 11 bits
10 -> 19 bits
11 -> 27 bits
与えられたメモリの制約内で、かなりの数の可能な入力リストを格納できる必要があります。圧縮スキームを選択して最大数の入力で動作させる方法の計算は、私を超えています。
入力のドメイン固有の知識を活用して、これに基づいて十分に優れた整数圧縮スキームを見つけることができることを願っています。
ああ、それから、データを受け取るときに、その並べ替えられたリストに対して挿入並べ替えを行います。
番号の違いを順番に保存し、エンコーディングを使用してこれらのシーケンス番号を圧縮するだけです。2^23 ビットあります。それを 6 ビットのチャンクに分割し、最後のビットに、その数が別の 6 ビット (5 ビットと拡張チャンク) に拡張されているかどうかを示します。
したがって、000010 は 1、000100 は 2 です。000001100000 は 128 です。ここで、10,000,000 までの数列の違いを表す最悪のキャストを考えます。2^5 より大きい 10,000,000/2^5 差、2^10 より大きい 10,000,000/2^10 差、2^15 より大きい 10,000,000/2^15 差などがあります。
したがって、シーケンスを表すのに必要なビット数を追加します。1,000,000*6 + 切り上げ(10,000,000/2^5)*6+切り上げ(10,000,000/2^10)*6+切り上げ(10,000,000/2^15)*6+切り上げ(10,000,000/2^20)*4= 7935479。
2^24 = 8388608. 8388608 > 7935479 なので、簡単に十分なメモリを確保できるはずです。新しい数値を挿入するときに、where are の合計を格納するために、おそらくもう少しメモリが必要になるでしょう。次に、シーケンスを調べて、新しい番号を挿入する場所を見つけ、必要に応じて次の差を減らし、それ以降のすべてを右にシフトします。
ストリームを受信しながら、次の手順を実行します。
最初に妥当なチャンクサイズを設定します
擬似コードのアイデア:
ストリームを受信しながら、最初の 4 つの手順を続けます。最後のステップは、メモリを超えた場合に失敗するか、すべてのデータが収集されたら結果の出力を開始することです。あなたはそれらに到達します。
ROM サイズはカウントされないため、TCP バッファ以外に追加の RAM は必要ありません。大きな有限状態マシンを実装するだけです。各状態は、読み取られた複数の数値セットを表します。100 万個の数値を読み取った後、到達した状態に対応する数値を出力するだけです。
数値の範囲が限られている場合 (たとえば、mod 2 8 桁の数値のみ、または 10 個の異なる 8 桁の数値のみ)、最適化された並べ替えアルゴリズムを作成できます。しかし、考えられるすべての 8 桁の数字をソートしたい場合、これはメモリ量が少ないと不可能です。
最大99,999,999までカウントし、途中で1,000,000ストップを示す必要があります。したがって、1でカウンタをインクリメントし、0で数値を出力することを示すように解釈されるビットストリームを使用できます。ストリームの最初の8ビットが00110010の場合、これまでのところ0、0、2、2、3になります。
log(99,999,999 + 1,000,000) / log(2) = 26.59。あなたは2^28あなたの記憶にビットを持っています。あなたは半分を使う必要があるだけです！
入力ファイルを 2 回以上読み取ることができる場合 (問題のステートメントには、読み取れないとは書かれていません)、次のように動作するはずです。これについては、Benchley の著書「Programming Perls」で説明されています。各数値を 8 バイトで格納すると、1 メガバイトに 250,000 個の数値を格納できます。入力ファイルを 40 回パスするプログラムを使用します。最初のパスでは、0 から 249,999 までの任意の整数をメモリに読み込み、(最大で) 250,000 個の整数をソートして、出力ファイルに書き込みます。2 番目のパスでは整数が 250,000 から 499,999 にソートされ、40 番目のパスでは 9,750,000 から 9,999,999 にソートされます。
数値が均等に分散されている場合は、Countingsortを使用できます。各数値が配列内で繰り返される回数を維持する必要があります。使用可能なスペースは次のとおりです。1MB-3KB=1045504Bまたは8364032ビット数値あたりのビット数=8364032/1000000= 8したがって、各数値が最大2 ^ 8-1=255まで繰り返される回数を格納できます。 。このアプローチを使用すると、255回を超えて数値が繰り返される場合を処理するために使用できる、未使用の364032ビットが追加されます。たとえば、255という数字は255以上の繰り返しを示していると言えます。この場合、数字と繰り返しのシーケンスを格納する必要があります。以下に示すように、7745の特殊なケースを処理できます。
364032 /（ビットは各数値を表す必要があります+ 100万を表すために必要なビット）= 364032 /（27 + 20）= 7745
16進数に変換しようとしましたか？
前後でファイルサイズが大幅に削減されていることがわかります。次に、空きスペースで部分的に作業します。たぶん、再度 10 進数に変換し、次数、16 進数、別のチャンク、10 進数に変換、次数...
申し訳ありません..うまくいくかどうかわかりません
# for i in {1..10000};do echo $(od -N1 -An -i /dev/urandom) ; done > 10000numbers
# for i in $(cat 10000numbers ); do printf '%x\n' $i; done > 10000numbers_hex
# ls -lah total 100K
drwxr-xr-x 2 diego diego 4,0K oct 22 22:32 .
drwx------ 39 diego diego 12K oct 22 22:31 ..
-rw-r--r-- 1 diego diego 29K oct 22 22:33 10000numbers_hex
-rw-r--r-- 1 diego diego 35K oct 22 22:31 10000numbers