3

私が解決しなければならない問題は、IPアドレスプレフィックスとそれに関連付けられたデータをツリーに入力して、後でクエリできるようにする必要があることです。私はファイルからこれらのアドレスを読み取っていますが、ファイルには1,600万ものレコードが含まれている可能性があり、ファイルに重複がある可能性があり、それらも保存する必要があります。

独自の二分探索木を作成しましたがTreeMap、Javaでは赤黒木を使用して実装されていることを学びましたが、TreeMap重複を含めることはできません。

クエリにO(logn)時間がかかります。
データ構造はRamにある必要があるため、1600万ノードをどのように格納するかもわかりません。

質問したかったのですが、グアバのようなライブラリを使用してIpsをマルチマップに挿入するのは、パフォーマンスに大きな影響を与えるでしょうか?それとも、これを行うためのより良い方法はありますか?

4

1 に答える 1

3

テストされ、文書化され、適切に保守されている組み込みライブラリを使用することは、通常、良い習慣です。
また、グアバについてさらに学ぶのに役立ちます。「たった1つのことのために」それを使い始めると、あなたはおそらくあなたの人生を少し楽にするためにあなたが使うことができるはるかに多くのものがあることに気付くでしょう。

また、別の方法として、マルチマップのカスタム実装としてでTreeMap<Key,List<MyClass>>はなくを使用することもできます。TreeMap<Key,MyClass>


メモリに関しては、データを可能な限り最小化するように努める必要があります(効率的なデータ構造を使用し、「無駄」の必要はありません。Stringたとえば、IPを保存するために、より安価な代替手段があり、それらを活用します。

また、OSは、仮想メモリを使用することで、RAMよりも多くのメモリを提供できることに注意してください(実際には64ビットマシンの場合、十分すぎる可能性があります)。ただし、ディスク専用のDS( B +ツリーなど)よりも効率が低下する可能性があります。


代替案:
-の代替案としてTreeMap、他のデータ構造に興味があるかもしれません(それぞれに長所と短所があります):

  • ハッシュテーブル-javaのように実装されHashMapます。その場合、タイプはになりますHashMap<Key,List<Value>>。平均的なケースのクエリを許可しますが、最悪のケースO(1)に減衰する可能性があります。O(n)また、効率的な範囲クエリは許可されません。
  • トライまたはそのよりスペース効率の良いバージョン-基数木O(1)各キーへのアクセスを許可しますが、通常、他のキーよりもスペース効率が低くなります。このアプローチではMap、DSとのインターフェイスを実装し、タイプは次のようになります。Map<Key,List<Value>>
  • B +ツリー。これはディスク用にはるかに最適化されています。データが大きすぎてRAMに収まらない場合は、結局のところ。
于 2012-12-11T19:26:29.210 に答える