performance - <、>、などの実数演算子に基づく高速検索データ構造

Question

HashMap のようなデータ構造は、キーの等価性に基づいてデータを取得します。

比較結果に基づいてデータを取得したい場合、どのデータ構造を使用すればよいですか?

Answer 1

一般に、バランスの取れた二分木を使用する必要があります。C++ では、 で取得できますstd::map。Java では TreeMap と呼ばれます。残念ながら、Python の標準ライブラリには何もありません。

特殊なケースでは、スプレイ ツリーや単純なリンク リストなどの他の構造の方が適している場合があります。それはあなたのニーズに依存します。

Answer 2

すでに回答されているように、バランスの取れたツリーが良いです。

ただし、挿入の速度やメモリ要件については何も言及していません。ソートされた配列は、検索 (バイナリ検索) が非常に高速ですが、挿入が遅くなる可能性があります。

文字列を使用したインデックス作成について話していると思います。最速のルックアップはディクショナリです (私のベンチマークでは、C++ マップの 2 倍の速さです) が、ストレージが重いです。

ディクショナリを使用すると、各ノードは (ノードへの) ポインタの配列を持ちます。可能な文字列文字ごとに 1 つです。挿入するには、文字列内の各文字をウォークスルーし、その文字のノードを追加し (まだ存在しない場合)、そのノードまでトラバースして、文字列の末尾に到達するまで続行します。次に、そのノードにデータを保存します。このデータ構造には、部分的に完全なキーがある場合に、単語補完リストを作成するオプションを提供するという追加のボーナスがあります。