8

多くの同様の質問を読んだ後：

まだ質問があります。文字列の大きな配列 (数千) があり、多くの検索を行う必要があるとします (つまり、特定の文字列がこの配列に含まれているかどうかを何度も確認します)。Node.js でこれを行う最も効率的な方法は何ですか?

A. 文字列の配列を並べ替えてから、バイナリ検索を使用しますか? また：

B. 文字列をオブジェクトのキーに変換し、「in」演算子を使用する

?

A の複雑さは O(log N) であることがわかっています。ここで、N は文字列の数です。

しかし、B の複雑さはわかりません。

Javascript オブジェクトがハッシュ テーブルとして実装されている場合、B の複雑さは平均で O(1) であり、A よりも優れています。ただし、Javascript オブジェクトが本当にハッシュ テーブルとして実装されているかどうかはわかりません。 !

4

2 に答える 2

2

文字列の固定された大きな配列については、何らかの形式の基数検索を使用することをお勧めしますまた、このパッケージ のさまざまなデータ構造とアルゴリズム (AVL ツリー、キュー/ヒープなど) を見てください。

JS オブジェクトを文字列のストレージとして使用すると、そのオブジェクトが「ハッシュ モード」になると確信しています。実装によっては、これは O(log n) から O(1) 時間になる可能性があります。いくつかのjsperfベンチマークを見て、並べ替えられた配列でのプロパティ ルックアップとバイナリ検索を比較してください。

実際には、特にブラウザーでコードを使用しない場合は、この機能を redis や memcached などにオフロードします。

于 2013-06-13T01:21:38.473 に答える