2

私のプロジェクトでは、文字列のトークンを含む assets フォルダーから 600KB のファイルを読み込もうとしています。

これらのトークンは、o(1) または一定の時間に利用可能/検索/含む必要があります。

私は始めましたHashSet-しかし、それは文字列データを10MBに爆破します-メモリ不足の問題を引き起こします

次に、に切り替えましたArrayList-しかし、それも6MBに吹き飛ばされます。

私はプリミティブを使用しようとしStringましたが、それをビルドすると、メソッドStringBufferに固有の問題がappend発生し、メモリ不足の問題が発生します。

したがって、私の主な懸念はまだこのデータにあります。

  • 元は 600KB であるため、コレクションでは 1 ～ 2MB 以内に十分に収まる必要があります。
  • ルックアップは、できれば O(1) 以内にする必要があります

私を助けることができる良い Java コレクション (他のライブラリからでも) はありますか?

4

2 に答える 2

0

これらのトークンをメモリ内で 1 ～ 2Mbで表現し、O(1)ルックアップをサポートすることは非常に困難です。標準のコレクション型でこれを行うことはできません。また、サードパーティの Java ライブラリでこれを行うことも知りません。( S-SpaceプロジェクトにはTrieSet実装がありますが、コードを調べたところ、スペースまたはパフォーマンスの要件を満たしていないと確信しています ...)

文字列内の文字が ASCII であると仮定すると、それらを String オブジェクトに変換するとすぐにサイズが 2 倍になり ( byte-> char)、文字列ごとに 32 バイトのオーバーヘッドを追加する必要があります。次に、文字列を に入れるHashSetと、セット内のエントリごとに約 32 バイトが追加で必要になります。

ArrayList<String>エントリごとのオーバーヘッドは 4 バイトですが、ルックアップは...O(N)またはO(logN)、リストの順序を維持してバイナリ検索を使用する場合です。いずれにせよ、メモリの予算をまだ超えています。

予算内に収まるようにするには、メモリ使用量が最適化されたカスタム ハッシュ テーブル データ構造を使用し、文字データを単一のバイト配列としてメモリに保持する必要があります。

これは仮想的な実装です。

  1. int[]をハッシュ配列に割り当てます。サイズは、トークン数の約半分から 5 分の 1 の素数にする必要があります。
  2. byte[]トークンのファイルを保持するのに十分な大きさを割り当てます。
  3. ハッシュ配列の各スロットについて:
    • ファイルをバイト単位でスキャンして、ハッシュコードがスロットにマップされているすべてのトークンを探します。
    • 各トークンをバイト配列にコピーし、その後にターミネータ バイトを続けます。
    • トークンが見つかった場合は、最初のトークンの開始のバイト配列オフセットをハッシュ配列スロットに書き込みます...そうでない場合は、に設定し-1ます。
  4. ルックアップを行うには:
    • テスト文字列をバイトに変換し、
    • テスト文字列のバイトを (上記と同じハッシュ アルゴリズムを使用して) ハッシュし、それをハッシュ スロットにマップします。
    • ハッシュ スロットのオフセットから開始して、テスト文字列のバイトを のバイトと比較しますbyte[]。一致するか、次のハッシュ配列要素のオフセットに到達するまで繰り返します。

ご覧のとおり、入力するプロセスにはbyte[]、入力ファイルを複数回スキャンすることが含まれます。ただし、これは事前に行うことができ、必要な順序でバイトを含むように入力ファイルを更新することができます。

スペースの使用量は、文字列データのバイトごとに 1 バイト + 文字列ごとに 1 バイトのオーバーヘッド + プライマリ ハッシュ配列のスロットごとに 4 バイト (+ 雑多なO(1)オーバーヘッド) になります。ルックアップはO(1)平均的ですが、定数はハッシュ配列のサイズによって異なります。(大きければ大きいほど良いです。)

上記の設計の大きな欠点は次のとおりです。

  • データ構造の作成にはコストがかかります
  • スペースまたは時間効率の良い方法でデータ構造を更新することはできません
  • セットを反復する場合は、一連の String オブジェクトを作成してエントリを表すか、バイト配列とオフセットを公開する必要があります。
于 2012-12-02T15:18:12.187 に答える
0

面白い問題ですね！このようなストレージには、通常、util パッケージの HashMap クラスを使用します。あなたの問題は、Android デバイスのメモリ空間に簡単に収まらない可能性があるため、別の方法を提案します。

通常、Android デバイスのストレージには、通常はかなり高速な SD カードなどのソリッド ステートが使用されます。そのため、必要になるまで、ディスク上のほとんどのデータをアセット フォルダーに残しておきましょう。最も頻繁に使用される結果をキャッシュするクラスを構築でき、データの変更も合理的です。これがうまくいかない場合は、android SDK で利用可能な sqlite などのデータ管理機能を使用できます。

文字列の使用を避けることができる場合は、多くの場合、より良いオプションです。文字列は、操作に非常にコストがかかる場合があります。別のデータ型 (または char または byte 配列) を使用すると、おそらくコードがもう少し複雑になりますが、メモリに関してはより効率的になります。

于 2012-12-03T04:19:14.000 に答える