2

私がやろうとしていること：

RAMに非常に多くのデータを保存したい。アクセスを高速化し、メモリ フットプリントを削減するには、構造体値の配列を使用する必要があります。

MyStruct[] myStructArray = new MyStruct[10000000000];

ここで、MyStruct に 1、2、3、または 4 バイトの符号なし整数値を格納したいと考えています。ただし、可能な限り少ないメモリ量のみを使用する必要があります。値を1バイト格納すると、1バイトのみを使用する必要があります。

これをクラスで実装することもできますが、64 ビット システムではオブジェクトへのポインターに 8 バイトが必要になるため、ここでは不適切です。したがって、すべての配列エントリに対して 4 バイトだけを格納する方がよいでしょう。しかし、必要なときに1/2/3バイトのみを保存/使用したいです。そのため、いくつかの派手なクラスを使用できません。

また、値の特別な順序が必要なため、1 バイトの 1 つの配列、2 バイトの 1 つの配列なども使用できません。また、値が非常に混在しているため、他の配列に切り替えるときに追加の参照を保存しても役に立ちません。

1 バイト、約 60% の時間で 2 バイト、約 25% の時間で 3 バイトのみを格納する必要があるにもかかわらず、4 バイト uint の配列を格納する唯一の方法は何ですか?

4

4 に答える 4

6

これは不可能です。CLR は次の式をどのように処理しますか?

myStructArray[100000]

要素が可変サイズの場合、CLR は 100000 番目の要素のアドレスを認識できません。したがって、配列要素は常に固定サイズです。

アクセスが必要ない場合はO(1)、上に可変長要素を実装してbyte[]、自分で配列を検索できます。

リストを 1000 個のサブリストに分割して、個別にパックすることができます。そうすればO(n/2000)、平均して検索パフォーマンスが得られます。多分それは実際には十分です。

O(n/2)「パックされた」配列は平均的にしか検索できません。しかし、部分配列のサイズが 1/1000 の場合、それは になりO(n/2000)ます。O(1)それらはすべて同じサイズになるため、部分配列を選択できます。

また、部分配列の数を調整して、個々のサイズが約 1k 要素になるようにすることもできます。その時点で、配列オブジェクトとそれへの参照のオーバーヘッドはなくなります。これにより、O(1000/2 + 1)ルックアップのパフォーマンスが大幅に向上すると思いますO(n/2)。これは一定時間のルックアップです(大きな定数を使用)。

于 2012-07-07T22:31:09.020 に答える
2

追加の CPU 時間を犠牲にして、1 つの格納された値ごとに追加の 2 ビットまたは 4 ビットを浪費しても構わないと思っている場合は、必要な値に近づけることができます。

byte を使用して、 collectionbyte[]と組み合わせることができます。byte[] では、1、2、3、または 4 バイトを順番に格納し、BitArray ではバイナリ形式 (2 ビットのペア) で表すか、ビットを値 1 にして、新しいバイト セットが開始されたことを示します (または終了しましたが、どのように実装しても) データ配列に含まれます。BitArray

ただし、メモリ内で次のようなものを取得できます。

byte[]   --> [byte][byte][byte][byte][byte][byte][byte]...
BitArray --> 1001101...

つまり、バイト配列に 3 バイト、1 バイト、2 バイトなどの値が格納されています。

または、bitarray をバイナリ ペアとしてエンコードして、さらに小さくすることもできます。これは、実際のデータ バイトあたり 1.0625 から 1.25 バイトの間のどこかを拡大することを意味します。

MyStructこれで十分かどうかは、実際のデータ (あなたの ) によって異なります。これらのバイトが実際に対応する構造体の値を区別する必要がある場合は、 で追加のビットを無駄にする可能性がありますBitArray。

O(1) 要件を更新します。

たとえば 1000 のように、N 要素ごとに 1 つのインデックスを格納する別のインデックス構造を使用します。

indexStore[234241/1000]

これにより、要素 234000 のインデックスが得られます。BitArray 内の数百の要素を調べて、要素 234241 の正確なインデックスを計算するだけです。

O(const) はこの方法で達成されます。const はメイン インデックスの密度で制御できます。もちろん、時間とスペースを交換します。

于 2012-07-07T22:34:43.147 に答える
1

あなたはそれをすることはできません。

データがソートされておらず、それについて何も言えなければ、やりたいことができません。

簡単なシナリオ:

array[3]

何らかのメモリアドレスを指す必要があります。array[0]しかし、 -の次元をどのように知ることができますかarray[2]? その情報を O(1) 形式で保存するには、最初に保存したいよりも多くのメモリを浪費するだけです。

あなたは既成概念にとらわれずに考えています。それは素晴らしいことです。しかし、私の推測では、これはあなたが抜け出そうとしている間違った箱です。データが本当にランダムで、すべての配列メンバーに直接アクセスしたい場合は、数値ごとに必要な MAXIMUM 幅を使用する必要があります。ごめん。

保存する必要がある長さの数値が 32 ビットよりも小さいという、同様の状況が 1 つあります。しかし、それらはすべて固定幅だったので、カスタムコンテナと少しシフトすることで解決できました。

望み：

http://www.dcc.uchile.cl/~gnavarro/ps/spire09.3.pdf

多分あなたはそれを読むことができ、数字ごとに8、16、24、32ビットだけでなく、任意の数字サイズを持つことができるでしょう...

于 2012-07-07T23:16:30.587 に答える
0

私は、PkZip プログラムのような短い単語エンコーディングのいくつかの変種を見始めるところです。

またはRLEエンコーディング。

または、データの使用法をよりよく理解するようにしてください。同様に、これらがすべてベクトルか何かである場合、許可されない特定の組み合わせがあります。たとえば、-1、-1、-1 は、グラフ化可能な範囲外のデータを示すため、財務グラフ作成アプリケーションにとって基本的に意味がありません。データに関するいくつかの奇妙な点を見つけることができれば、さまざまなニーズに合わせてさまざまな構造を持つことで、サイズを縮小できる可能性があります。

于 2012-07-07T23:47:47.863 に答える