100 ^ 100ものBigIntegerエントリなど、適切なハードウェアがあれば、理論的に処理できる配列またはリストを作成しようとしています。配列または標準リストを使用する場合の問題は、Integer.MAX_VALUEの数のエントリしか保持できないことです。この制限をどのように回避しますか？まったく新しいクラス/インターフェース？リストのラッパー？完全に別のデータ型？
7 に答える
4
22次元のJava配列には、理論上、データを保持するのに十分なスペースがあります。
ただし、宇宙全体の原子数は10 ^ 78と推定されていることに注意してください（ドイツ語で参照）。
したがって、実装を開始する前に、宇宙のすべての原子に10^23バイトを格納する方法を考える必要があります...
編集
一般に、O（1）でのアクセスをサポートする大規模なデータ構造が必要な場合は、多次元配列を作成できます。
2次元配列配列[Integer.MAX_VALUE][Integer.MAX_VALUE]は、約4.6x10^18の値を保持できます。各値aiは、array [ai mod Integer.MAX_VALUE] [aidivInteger.MAX_VALUE]でアドレス指定できます。そしてもちろん、これは高次元の配列でも機能します。
于 2009-07-09T17:27:39.173 に答える
4
100^100 = 10^200。BigInteger のメモリ フットプリントが 28 バイト (7 つintのフィールドがある) であると仮定すると、2.8 * 10^201 バイトまたは 2.8 * 10^192 ギガバイトになります。適切なハードウェアはなく、今後もありません :-)
于 2009-07-09T17:16:31.333 に答える
1
より大きな値を可能にする新しいインターフェイスタイプを作成します。おそらく、最大サイズとインデックスパラメータにlongを使用しています。
于 2009-07-09T17:27:59.187 に答える
0
いくつかの理由で、あなたはあなた自身のコレクションを作ることを考えていると思います。まず、リストインターフェイスはintの長さを想定しています。理論的にはリストの実装を0にしないように強制することもできますが、これにより潜在的な容量が2倍になりますが、それでも危険です。
もう1つの理由は、メモリに完全に保存されていないものを調べている可能性があるため、キャッシュ、インデックス作成、反復処理などには外部リソースの依存関係があり、インデックスによる取得またはイテレータの両方ではなく、両方が必要な場合があります。
これは大規模な分散コンピューティングの問題のように聞こえますが、Javaコレクションが対処するように設計されたものではありません。
ただし、このような大きなインデックスが必要な場合（非常に長い行に少数のポイントをプロットしているため）、マップに裏打ちされたカスタムインターフェイス（BigIntegerキーとリストの内容を表す値を含む）で何が得られるかがわかります。あなたが欲しい。リストのような動作が本当に必要な場合、マップの実装では挿入順序を個別に追跡する必要がある場合があります。
于 2009-07-09T17:33:46.540 に答える
0
2 つの 32 ビット整数から 64 ビット整数、または 4 つの 32 ビット整数から 128 ビット整数、または十分な整数から実際に必要な任意のサイズを効果的に取得できます。
実証するために、2 つの 32 ビット int で 64 ビット int を表す最も単純なケースを考えてみましょう。
擬似コード:
int64 c = Get64BitInt(int32 a, int32 b)
{
c = 2^32*a + b
}
整数配列を使用して数値を格納する大きな整数を保持する新しいクラスを定義できます。独自の算術メソッドを作成する必要がありますが、それほど負担にはなりません。
于 2009-07-09T17:25:57.990 に答える
0
最初に頭に浮かぶのは、インデックスArrayListをサポートし、複数の の配列を持つ新しい型を作成することです。次に、get/set/etc メソッドを実装して、2^32 より大きいインデックスにアクセスすると、配列内の次のインデックスにアクセスできるようにします。使用する配列を決定するには、インデックスを でハッシュします。longArrayListArrayList(2^32 - 1) mod index
サイズの制約の問題に対処するには、一部の配列をディスクにシリアル化する必要があります。ただし、HPC を使用している場合、これはそれほど問題にはなりません。私がアクセスできる共有メモリ システムでは、ノードごとに 256 GB のメモリを使用できます。そのリストを反復するのにどれくらいの時間がかかるかは別の問題ですが、天体物理学者はそのスケールに近いことをしていると思います.
リストのサイズが大きすぎて作業できないように見えるため (他の投稿者が言っているように)、作業可能なサイズに縮小する必要があります。
于 2009-07-09T17:16:33.733 に答える
0
リンクされたリストを使用できます...しかし、戻る前に死ぬでしょうlist.get(list.size()-1):-)
ところで、大量のデータを処理できるFastutilコレクション ライブラリを見てください。
于 2009-07-09T17:19:03.167 に答える