1

String高速検索が必要なものがたくさんあります。各文字列は22文字の長さで、最初の12文字（いわば「キー」）によってのみ検索され、文字列の完全なセットが定期的に再作成されます。それらはファイルからロードされ、ファイルが変更されると更新されます。使用可能なメモリが少なすぎるため、VPS上の他のサーバープロセスでもメモリが必要であり、さらに多くのメモリが必要です。

文字列を保存して検索するにはどうすればよいですか？

私の現在のアイデアは、（RAMを節約するために）それらを次々に（RAMを節約するために）格納し、より高速なルックアップのためにソートすることです（バイナリ検索または補間char[]検索を使用できるように、事前にソートしておくとルックアップが最も速くなると思います）。しかし、私はそれをどのようにコーディングすべきか正確にはわかりません-誰かが挑戦的なパズルの気分になっているなら：ここにあります...

ところで：レクリエーション/並べ替え中にしばらくの間メモリの制約を超えても大丈夫ですが、それほど長くはないはずです。

ありがとう！

アップデート

「詳細を知りたい」群衆の場合（Javaの詳細が間違っている場合は訂正してください）：ソースファイルには約320000エントリ（すべてANSIテキスト）が含まれていますが、本当に（WAY！）64MB未満にとどまりたいですRAMの使用量とデータは私のプログラムの一部にすぎません。メモリ内のJavaタイプのサイズに関する情報を次に示します。

私のVPSは32ビットOSなので、...

  • 1つbyte[]、すべて連結=12+長さバイト
  • 1つchar[]、すべて連結=12+長さ*2バイト
  • String= 32+長さ*2バイト（オブジェクトであり、char[]+ 3を持ちますint）

だから私は記憶に留めておかなければなりません：

  • すべてがに保存されている場合は最大7MBbyte[]
  • すべてがに保存されている場合は最大14MBchar[]
  • すべてがに保存されている場合は最大25MBString[]
  • > HashTable / Mapに保存されている場合は40MB以上（おそらく初期容量を微調整する必要があります）

HashTableは魔法ではありません-挿入に役立ちますが、原則として、hashCodeモジュラス容量がインデックスとして使用される非常に長い文字列の配列であり、データはインデックスの次の空き位置に格納され、線形の場合は検索されますルックアップで見つかりませんでした。ただし、ハッシュテーブルの場合、ルックアップ用に文字列自体と最初の12文字のサブ文字列が必要になります。私はそれを望んでいません（または私はここで何かを逃しますか？）、ごめんなさい人々...

4

3 に答える 3

1

HashTableは、この状況に適した実装のように聞こえます。

検索は一定時間で実行され、更新は線形時間で実行できます。

Javaデータ構造Big-O（警告PDF）

于 2012-08-10T19:19:05.480 に答える
1

私はおそらくそのためにキャッシュソリューションを使用するでしょう、グアバでさえそうするかもしれません。もちろん、それらをソートしてから、バイナリ検索します。残念ながら私にはそれをする時間がありません:(

于 2012-08-10T19:05:10.170 に答える
1

自分で解決策をコーディングしましたが、公開していない情報を使用できるため、投稿した質問とは少し異なります（次回はもっとうまくいきます、申し訳ありません）。

私はこれが解決されたので答えているだけですが、他の答えの1つはメモリの制約に実際には役立たなかったので（そして私の好みには少し足りなかったので）受け入れません。彼らはまだそれぞれ賛成票を獲得しました、難しい感情はなく、時間を割いてくれてありがとう！

私はなんとかすべての情報を2つのロングにプッシュすることができました（キーは最初のロングに完全に存在します）。最初の12文字はISINであり、数字と大文字のみを使用するため、長く圧縮できます。常に2つの大文字で始まり、他の文字から再構築できる数字で終わります。可能なすべての値の積は、3ビット強の余裕を残します。

ソースファイルのすべてのエントリをlong[]（最初にパックされたISIN、2番目の長さで他のもの）に保存し、2つの長さの最初の長さに基づいて並べ替えます。

キーでクエリを実行するときは、それをlongに変換し、バイナリ検索（おそらく、補間検索に変更します）を実行して、一致するインデックスを返します。値のさまざまな部分は、上記のインデックスによって取得できます。配列から2番目の長さを取得し、解凍して、要求されたデータを返します。

結果：RAM使用量はJettyを含めて約110MBから<50MBに減少し（ところで、以前はHashTableを使用していました）、ルックアップは非常に高速です。

于 2012-08-13T23:22:37.347 に答える