4

Java では、プログラムのある時点で、int[]メモリ内で数ギガバイトの配列を処理する必要があります。それらはソートされ、ファイル行を表す自然数( 1, 2, 3, 4、...、最大) のみを含みます。nNumbernはファイル内の行数であり、最大にすることができます100000。したがって、配列は、ファイル内のすべての行のセットの単なるサブセットです。計算できるように、そのようなサブセットは何百万もあり、それらのいくつかを持つことは非常に重要です。これらのサブセット内のデータ分布 (ここでは配列と呼びましょう) に関しては、完全にランダムです。つまり、長い配列は50000数字で発生し、小さな配列は数字のみで発生し1500ます。また、各配列には、[3, 10, 11, 12, 13, 14, 15, 135, 136, ...]またはのような予測不可能なシーケンスが含まれています[2, 3, 746, 7889, 7892, 80000,...]。

圧縮/解凍する配列がたくさんあるので、実行ごとに費やされる時間の点で最速のソリューションを見つけたいと思います。したがって、オーバーヘッドは可能な限り最小限に抑える必要があります。

どのライブラリをお勧めしますか?

4

3 に答える 3

3

データを無損失で前処理して、圧縮を改善できます。最初の値はそのままにします。後続の各値は、それと前の値の差から 1 を引いた値にします。そのような違いは負ではないことが保証されています。次に、バイト シーケンスを使用して、各整数を可変長整数としてコーディングします。たとえば、デコードする場合、0..127 は 1 バイトです。その最初のバイトの上位ビットが設定されている場合 (128..255)、整数の下位 7 ビットとして下位 7 ビットを取得し、次のバイトを取得します。上位ビットが 0 の場合はバイト全体を次の上位 8 ビットとして使用し、上位ビットが 1 の場合は下位 7 ビットのみを使用します。上位ビットがゼロ (整数の終わりを意味する) のバイトに到達するまで続行します。

これで、整数を一連のバイトとしてエンコードしました。これは、元の各整数をそれぞれ 4 バイトまたは 8 バイトとしてエンコードするよりもかなり短い可能性があります。さらに、一連のバイトで機能する標準の圧縮手法を適用できるようになり、それによってある程度の利益が期待できる可能性があります。たとえば、一連の連続した行番号が一般的である場合、高度に圧縮可能なゼロバイトの文字列が得られます。

圧縮の程度を犠牲にして圧縮と解凍の最大速度については、lz4を見てください。それほど高速なものが必要ない場合は、圧縮レベルで圧縮速度と効果を選択できるzlibを見てください。

あなたの例では、10000 から 1500 をランダムに選択すると、約 1720 バイトが非圧縮、1600 バイトが圧縮されます。100000 から 50000 をランダムに選択すると、50000 バイトが非圧縮、18600 バイトが圧縮されます。圧縮は、最速の zlib 圧縮レベル 1 で行われました。

行番号の半分が使用される後者のケースでは、圧縮されていない 12500 バイトになるビット配列を使用する方が効率的であることに注意してください。その場合、ビット マップがランダムに見えるため (半分のビットが設定され、半分が設定されていない)、データを圧縮することはできません。多かれ少なかれ、たとえば 25000 や 75000 では、どちらも約 10500 バイトまで圧縮可能なビットマップになります。

圧縮されたビットマップは、行番号が約 12500 以上の場合は小さくなりますが、圧縮された差分可変整数は、行番号が約 12500 未満の場合は小さくなります。そのカットオフは、2 つのアプローチの非圧縮サイズがほぼ同じ 12500 バイトになるポイントです。

于 2013-04-24T05:06:54.137 に答える
1

Googleのsnappyのポートであるsnappy-javaをお勧めします

于 2013-04-23T18:54:50.050 に答える
0

多分これもあなたを助けることができます： Javaで整数の配列を圧縮する

配列に対して多くの計算を行う必要がありますか?それとも読み取り専用ですか?

編集：

//If the space is more important than performance this might work:
//Not this might be totally stupid for some cases
// First element should be false since its the 0 ;)
boolean[] numbers = { false, true, true, true, false, false, true };

for (int i = 0; i <= numbers.length - 1; i++) {
    if (numbers[i]) {
    // or do some calculations on/with a copy of i
    System.out.println(i);
    }
}

ブール型の arry は各情報を格納するために 1 バイトを使用するため (+オーバーヘッド)、これは最大 100'000 エントリを意味します: 100'000 バイト = 各配列に対して ~97kb

于 2013-04-23T18:52:09.867 に答える