2

何千もの整数の配列を反復処理するAndroidアプリケーションがあり、それらを使用して計算を行うために、整数のペア（IDと呼びます）にアクセスするためのキー値としてそれらを使用します。できるだけ速く実行する必要があり、最終的には、アプリケーションにとって重要な結果を返します。

これらの番号にすばやくアクセスするためにHashMapをメモリにロードしようとしましたが、OOM例外が発生しました。また、これらのIDをRandomAccessFileに書き込んで、ファイルのオフセットを別のHashMapに保存しようとしましたが、遅すぎました。また、オフセットのみを格納する新しいHashMapは、依然として大きなメモリを占有しています。

今私はSQLiteを検討していますが、それがもっと速くなるかどうかはわかりません。それを助けることができる構造やライブラリはありますか？

編集：キーの数は2000万を超えていますが、アクセスする必要があるのは数千にすぎません。ユーザー入力によって変化するため、事前にアクセスするものがわかりません。

4

3 に答える 3

4

Troveを使用して、プリミティブをプリミティブ（値のペアのsを格納する）TIntLongHashMapにマップできます。これにより、プレーンバニラのオブジェクトオーバーヘッドが節約され、ラッパータイプを使用する必要があります。intlongintMap

編集

更新では2,000万を超えるマッピングがあると記載されているため、ハッシュマップよりもスペース効率の高い構造が存在する可能性があります。キーをバケットに分割するアプローチと、サブキーの圧縮を組み合わせると、最も効率的なハッシュマップの実装よりもメモリを半分節約できる可能性があります。

于 2012-05-15T21:11:47.823 に答える
1

SQLiteは、インデックスを使用する組み込みリレーショナルデータベースです。RandomAccessFileを使用するよりもはるかに高速だと思います。あなたはそれを試してみることができます。

于 2012-05-15T21:24:26.813 に答える
1

私の提案は、バケット内のキーを再配置することです-つまり、キーの分布を（多かれ少なかれ）識別し、キーの各範囲に対応するファイルを作成します（すべてのファイルには、次の整数と同じ数の整数が含まれている必要があります）メモリに入ることができ、それ以上はできません）次に、キーを検索するときは、ファイル全体をメモリに読み込んで探します。

たとえば、キーの分布が均一であると仮定して、0〜500kのキー値に対応する500kの値、500k〜1milのキーに対応する500kの値などを格納します。

編集：あなたがこのアプローチを試したが、それでも遅くなった場合、私はまだ私のsleavesにいくつかのトリックを持っています：

  1. まず、すべてのバケット間で除算が実際にほぼ等しいことを確認します。
  2. より多くのバケットを作成して、バケットを小さくしてみてください。
  3. 範囲によるバケットへの正しい分割についての考え方は、キーを検索するときに、対応する範囲バケットに移動し、そのキーがコレクション内にあるか、コレクション全体に含まれていないことです。したがって、別のバケットを同時に読み取ることには意味がありません。
  4. I \ Oで同時実行が機能するかどうかわからないので、これを行ったことはありませんが、ファイル全体を2つのスレッドで上から下に、もう1つを下から上に、それらが出会うまで読み取ると役立つ場合があります。（またはそのようなもの）
  5. バケット全体をメモリに読み込み、3〜4個の配列リストに分割し、3〜4個の作業スレッドを実行して各配列のキーを検索します。検索は、その時点ではるかに速く終了する必要があります。
于 2012-05-15T21:31:39.437 に答える