私には特別なニーズがあり、最も重要な懸念事項は次のとおりです。
- インメモリ
- 非常に低いメモリフットプリント
- 速度
これが私の「問題」です。メモリ内に、非常にまばらなビット配列を大量に格納する必要があります。これらのビットセットは「追加のみ」であり、主に交差に使用されます。巨大とは、200 000 ビット配列という意味です。
各ビットセットの範囲は [0...16 000 000] です。
取得した実際のデータを含む「のみ」10 673 ビット配列を使用して事前テストを実行したところ、次の結果が得られました。
1% of the bit arrays ( 106 bit arrays) Hamming weight: at most 1 bit set
5% of the bit arrays ( 534 bit arrays) Hamming weight: at most 4 bits set
10% of the bit arrays ( 1068 bit arrays) Hamming weight: at most 8 bits set
15% of the bit arrays ( 1603 bit arrays) Hamming weight: at most 12 bits set
20% of the bit arrays ( 2137 bit arrays) Hamming weight: at most 17 bits set
25% of the bit arrays ( 2671 bit arrays) Hamming weight: at most 22 bits set
30% of the bit arrays ( 3206 bit arrays) Hamming weight: at most 28 bits set
35% of the bit arrays ( 3740 bit arrays) Hamming weight: at most 35 bits set
40% of the bit arrays ( 4274 bit arrays) Hamming weight: at most 44 bits set
45% of the bit arrays ( 4809 bit arrays) Hamming weight: at most 55 bits set
50% of the bit arrays ( 5343 bit arrays) Hamming weight: at most 67 bits set
55% of the bit arrays ( 5877 bit arrays) Hamming weight: at most 83 bits set
60% of the bit arrays ( 6412 bit arrays) Hamming weight: at most 103 bits set
65% of the bit arrays ( 6946 bit arrays) Hamming weight: at most 128 bits set
70% of the bit arrays ( 7480 bit arrays) Hamming weight: at most 161 bits set
75% of the bit arrays ( 8015 bit arrays) Hamming weight: at most 206 bits set
80% of the bit arrays ( 8549 bit arrays) Hamming weight: at most 275 bits set
85% of the bit arrays ( 9083 bit arrays) Hamming weight: at most 395 bits set
90% of the bit arrays ( 9618 bit arrays) Hamming weight: at most 640 bits set
95% of the bit arrays (10152 bit arrays) Hamming weight: at most 1453 bits set
96% of the bit arrays (10259 bit arrays) Hamming weight: at most 1843 bits set
97% of the bit arrays (10366 bit arrays) Hamming weight: at most 2601 bits set
98% of the bit arrays (10473 bit arrays) Hamming weight: at most 3544 bits set
99% of the bit arrays (10580 bit arrays) Hamming weight: at most 4992 bits set
100% of the bit arrays (10687 bit arrays) Hamming weight: at most 53153 bits set
関連する数値を見ると、明らかに圧縮されたビット配列を使用する必要がありますが、それは問題ではありません。ビット配列が「追加のみ」であることを考えると、扱いやすいままです。
オンになっているビット配列のビットは、グループ化されていますが、完全ではありません。そのため、同じ領域でいくつかのビットがオンになる傾向があります (ただし、通常は連続してオンになるわけではないため、オンになっているビットには RLE が適していません)。
私の質問は、どのような圧縮を使用するのですか?
最初のアプローチをここに置くべきか、それとも自分の質問への回答に置くべきかはわかりません。
基本的に、非常に愚かなエンコーディングを使用した「最悪のケース」のシナリオを想像しました。
1 ビット: オンの場合、次の 5 ビットは「スキップ」を計算するために必要なビット数を決定します。オフの場合、最適化: 次の 5 ビットは、文字どおり (つまり、「オン」または「オフ」) に取りすぎるビット数を決定します。 '、スキップなし) [これは、他の表現よりも効率的であると判断された場合にのみ切り替えられるため、開始時には常に最適化されます (サイズに関して)]
5 ビット: 次のビットがオンになる前にスキップできるビット数
x ビット: スキップ
例を次に示します。ビット配列には 3 ビット セットがあり、最初のビットは 3 098 137、2 番目のビットは 3 098 141、3 番目のビットは 3 098 143 です。
+-- now we won't skip
|
| +-- 3 because we need 3 bits to store "6" (from 3 098 138 to 3 098 143)
| | +--- 3 098 141 is on
22 3 098 137 | 3 | +- 3 098 143 is on
1 10110 1011110100011000011001 0 00011 000101 etc.
最初のビットは、ビットをスキップすることを示しています。次の 5 ビット (常に 5) は、スキップするビット数を伝えるために必要なビット数を示します。 22 ビットは、3 098 137 にスキップするように指示します。1 ビットオフは、ビットをスキップしないことを伝えます。次の 5 ビット (常に 5) は、伝えます。 「そのまま」読み取るビット数 6 ビット: オフ、オフ、オフ、オン、オフ、オン 3 098 141 および 3 098 143 がオンなどを意味します。
これらのビット配列の驚くべきスパース性を見ると、これは非常にサイズ効率が良いようです。
そのため、そのエンコーディングを使用して、サンプル データを取得し、「最悪の場合」のシナリオを計算しました (まだアルゴリズムを書いていないので、最初にここからいくつかの入力を取得したいと思います)。また、5 ビットが常に最大値 (24 ビット) に設定されますが、これはもちろん起こりません。
私は、「最悪の最悪」のケースが何であるかについて、非常に大まかな概算を得るためにそれを行いました.
とても嬉しい驚きでした：
Worst case scenario:
108 913 290 bits needed for the 10 687 very sparse bit arrays
12.9 MB (13 295 KB)
データは実際のデータであり、すべてのデータが類似しているため、さらに悪いことに、200,000 ビットの配列を約 240 MB に格納できることがわかっています。これは問題ありません。
実際のエンコーディングはそれよりもはるかに少ないと確信していますが、まだ実際に書いていないので、（非常に簡単に）「最悪のケース」しか計算できないため、そのケースのみを示します。
これをよりサイズ効率的にする方法に関するヒント/アイデア（これらは非常にまばらなビット配列であり、数十万個あり、メモリ内にある必要があり、「追加のみ」になることを覚えておいてください） ?
「追加のみ」のケースについて
基本的に、私は1つの成長する「広がり」（範囲ですが、「広がり」は私が理解している実際の用語です）と、いくつかのビットセットを持つ多くのビット配列を持っています。範囲がたとえば 0 から 1 000 000 になると、すべてのビット配列は 0 から 1 000 000 になります。範囲が 1 000 001 まで大きくなると、すべてのビット配列も 1 ビットずつ大きくなります。ただし、これらのビット配列のほとんどは末尾に「0」が追加され、ビット配列の約 4 ～ 8 には末尾に「1」が追加されます。ただし、どのビット配列に 0 または 1 が追加されるかを事前に予測することはできません。
したがって、すべて同じサイズで、すべて非常にまばらで (ビットセットの < 0.5%)、範囲の拡大に伴ってすべて「成長」しているビット配列がたくさんあります (したがって、それらはすべて常に成長しています)。同じレートで）。
ジュディの配列は素晴らしいです。しかし、私は数年前にそれらについて読みましたが、そのことは「私の頭の上」にありました。Judy 配列は C のみの 20KLOC ライブラリであり、私はそれを再実装するつもりはありません。しかし、彼らは素晴らしいです。
したがって、これらすべてを比較的単純なままにしておきたいと思いますが、これは、非常にまばらなビット配列の特別な「追加のみ」のプロパティを見てそれほど大げさではありません。