1

Java で列指向のデータ ストレージ エンジンを実装しようとしています。動的に成長する配列に連続したメモリ割り当てを実装する方法が他にあるかどうか知りたいと思いました。

HashMaps は、拡張/サイズ変更時に連続したメモリ ブロックを割り当てることができません。


より大きなサイズの新しい固定配列を作成し、古い固定配列からこの新しい配列に値をコピーすることによっても、連続性を実現する唯一のオプションのように見えますが、これは for ex と比較すると非常に遅いです。現在のサイズが 100 万の列 (固定配列) に既に 100 万のレコードがあり、1000001 の位置に新しい値を挿入する必要がある場合、jvm はサイズ 1000001 の新しい配列を作成し、すべての値を新しい配列にコピーする必要があります。より大きなサイズの配列 (1 つの値を挿入するためだけ) と連続性を維持します。


ArrayList は、上で説明したように内部的に同じように機能します (新しい配列の割り当て + 古い値のコピーなど)。そのため、スレッド セーフのための同期のオーバーヘッドが追加されたベクトルとして。


そのため、初期化中に巨大な固定配列を作成して大量の連続メモリを割り当てる別の方法は、大量の未使用メモリが発生するため、実行可能な解決策ではありません。


より良いオプションが利用可能な場合は助けてください。たとえば。（Javaで達成できる場合）現在の固定配列の最後の要素のアドレスを知り、使用可能な場合は次の連続する利用可能なブロックを何らかの方法でチェックするようなものですか？もしそうなら、それを使用して新しい値を格納し、配列インデックスを更新してこの新しい変更に対応し、O(1) 時間の読み取りアクセスを維持しますか?


ありがとう。

4

2 に答える 2

0

ハックはたくさんありますが、Java のArrayListものは、拡張可能な配列の最も効率的な既存の組み合わせの 1 つです。

固定長の配列を作成し、それらをリストに接続することができます (したがって、拡張には追加の配列を添付するだけでよく、それをコピーする必要はありません)。ただし、データ構造が大きくなると予想される場合は、完全にリストとして実装することをお勧めします。

連結される配列のサイズを 2 倍にすることで、これを拡張できます。したがって、それぞれのサイズなどを持つ配列のリストを作成します50, 100, 200, 400。配列 (および位置) は次のように計算できます。

int x = 55; // position

int position = (int)Math.floor(Math.log(1 + x / 50) / Math.log(2));
int arrayposition = x - (Math.pow(2, position) * 50);

大きなデータ値の場合でも、これはかなり高速なデータ構造になります (O(n)データの取得と拡張の最悪の場合の値は ですO(1)) 。

于 2013-08-11T21:41:35.850 に答える
0

これを「手動で」実行しようとしている場合、一般的な手法は、配列を増やす必要があるたびに配列のサイズを 2 倍にすることです。したがって、あなたの例では、配列のサイズを 200 万に変更できます。これはコストがかかりますが、長い間再度サイズ変更する必要がないことを意味します。

これにより、償却された定数時間で配列の挿入が可能になりますが、100 万行をコピーするような高価な操作を時々行うのは望ましくない場合があるため、特定のニーズに対応するためにこのアイデアを変更する必要がある場合があります。動的配列の実装の詳細については、http://en.wikipedia.org/wiki/Dynamic_arrayを参照してください。

于 2013-08-11T21:46:38.987 に答える