0

データを圧縮形式 (本質的にはミニ DSL) で保存およびクエリするのに役立つライブラリが必要です。ここに、必要なもののサンプルを示します。

更新 1 - 上記のサンプルの数値は、ロジックを簡単に理解できるようにするために小さくされていることに注意してください。実際の数値はc# long型の容量によって制限されています。例: 1,18,28,29,39,18456789,18456790,18456792,184567896.

サンプル生データセット:1,2,3,8,11,12,13,14

凝縮されたサンプル データ セット: 1..3,8,11..14

持っていると絶対にいいのは、1,2,4,5,6,7,8,9,10として提示できること1..10-3です。

サンプル データ セットのクエリ:

クエリ 1 (範囲を取得): 1..5->1..3

クエリ 2 (値が存在するかどうかを確認) ?2->true

クエリ 3 (複数の範囲とスカラー値を取得): 1..5,11..12,14->1..3,11..12,14

私はそれをゼロから開発したくはなく、既存のものを使用することを強く望んでいます。

4

2 に答える 2

1

あなたが望むことを完全に実行する既製のライブラリを認識していませんが、必要かどうかはわかりません。

BitArray既存のクラスの使用を検討することをお勧めします。あなたの例が示唆するように、小さな整数のセットを圧縮することに興味がある場合BitArray、たとえば 256 ビットのシングルは、範囲内の任意の整数のセットを表すことができます[0..255]。もちろん、通常のセットに整数が 5 つしかない場合、このアプローチでは実際にストレージ要件が拡大します。セットに関する独自の知識から、そのような配列の適切なサイズを把握する必要があります。

データを整数のセットとして見ることもお勧めします。そのため、例1,2,3,8,11,12,13,14は a の対応するビットを設定することで表されますBitArray。クエリ操作は、テストBitArrayとデータの間の交差に縮小されますBitArray。

2 -> trueちなみに、変換する例2は、整数のセットを整数のセットにマップする関数のドメインにとどまる方がよいと思います。つまり、変換する必要があります2 -> 2。必要に応じて、ブール値を返す別のメソッドを記述します。

BitArrays整数をパックして整数にアンパックするコードを書く必要があると思いますBitArraysが、それは圧縮のコストの一部です。

于 2012-09-26T08:57:45.013 に答える
1

あなたの質問を読んで以来、私が数日間持っていたいくつかのアイデアがあります. それらのいずれかが実際にあなたのユースケースに当てはまるかどうかはわかりませんが、ここで何か役立つものを見つけていただければ幸いです.

データを圧縮して保存する

数値がディスク上で占めるスペースの量を減らすために実行できる手順:

  • 値が 1 ～ 10M の場合は、 alongを使用しないでくださいuint。(数値ごとに 4 バイト。)
  • 実際には、を使用しないでくださいuint。数字を 7 ビットから 1 バイトに格納し、残りのビットを使用して「この数字にはさらにバイトがあります」と言います。(1-127 は 1 バイト、128-~16k は 2 バイト、~16k-~2M は 3 バイト、~2M-~270M は 4 バイトに収まります。)

これにより、ストレージは数値ごとに 8 バイト (最初に s として格納していた場合long) から、たとえば平均 3 バイトに削減されます。また、より大きな数値が必要になった場合は、可変バイト ストレージでそれらを保持できます。

次に、数が常に増加しており、多くの実行が含まれている可能性があることがわかっている場合、それをさらに減らす方法をいくつか考えることができます。実際のデータで試してみることで、あなただけが知ることができる最適な方法です。

  • 実際の数値ごとに、2 つの数値を格納します。数値自体と、その後に続く数値の数です (例: 2,3,4,5,6=> 2,4)。たとえば、孤立した数値を保存する必要がある8,0ため、それらのストレージが増加しますが、データに多くの実行（特に長いもの）がある場合、平均してストレージが削減されるはずです。「単一のギャップ」をたとえば=>のように実行にさらに保存することもできます(小さすぎて次の実行の開始にはならないため、明確です) が、これにより処理がより複雑になり、多くのスペースを節約できないため、気にしません。1,2,3,5,6,71,6,44
  • または、数値自体を格納するのではなく、デルタを格納します (so 3,4,5,7,8,9=> 3,1,1,2,1,1。これにより、より大きな数値を格納するために使用されるバイト数が削減されます (例: 15000,15005(4 バイト) => 15000,5(3 バイト))。実行回数が多い (例: 大量の1バイト) 場合、適切に圧縮 (例: zip) されます。

コードでの扱い

ファイルをディスクから にストリーミングするいくつかのメソッドを作成しIEnumerable<uint>(またはulong、より大きな数になる場合)、上記から実装したものを処理しながら逆を行うことをお勧めします。

これを怠惰な方法で行う場合 -yield returnディスクから数値を読み取って計算するときに数値を返すために使用し、数値をメモリに保持して一度に返すのではなく、数値をディスクにストリーミングすると、メモリの使用量を抑えることができます。保存されたデータのサイズ。

(私は、 GZipStreamやその他の圧縮ストリームでさえ、すべてをメモリに入れずにデータをストリーミングできると思いますが、よくわかりません。 )

クエリ

2 つのビッグ データ セットを比較する場合Intersect、ソースの 1 つを完全にメモリに読み込む必要があるため、LINQ の方法を使用することはお勧めしません。ただし、両方のシーケンスが増加していることはわかっているので、各シーケンスの列挙子を保持するだけでよい同様のメソッドを作成できます。

ユーザー入力の小さな数値リストに対してデータ セットの 1 つをクエリする場合、Intersect現在実装されている LINQ のメソッドを喜んで使用できます。これは、完全にメモリ内にある2 番目のシーケンスのみが必要なためです。

于 2012-09-28T07:37:26.713 に答える