16

Ruby では、文字列が配列 ( ) に含まれているかどうかを調べるのに.include? x非常に時間がかかります。その配列をセットに変更すると、BAM、非常に高速なルックアップになります。

セットがない JavaScript では、配列ルックアップ ( .indexOf(x) >= 0) も非常に遅くなりますが、スクリプトでこれらのルックアップを 10,000 回実行する必要があります。

私の Ruby バージョン (セットあり) は0.125数秒で実行され、私の JavaScript バージョン (NodeJS 内) は29!

Rubyに近いJavascriptの速度を得ることができる配列ルックアップを実行するためのセットライブラリまたはより良い方法はありますか?

編集：混乱を解消するために「オブジェクト」を「文字列」に変更しました

4

2 に答える 2

18

まず第一に、JavaScript で利用できるデータ構造について、根本的な混乱があります。

TL;DR

  • 短いプロトタイプ継承チェーンを持つオブジェクトのキー検索を最速にしたい場合は、 を使用しますin。

  • 同じことが必要であるが、広範な継承チェーンを持つオブジェクトの場合は、使用しますObject.prototype.hasOwnProperty

  • 最速の値ルックアップが必要な場合は、 for を使用Array.prototype.indexOfしArrayます。

  • ハッシュ テーブルの値を検索するための組み込み関数はありません。もちろん、独自のものを作成することもできますが、既に提供しているライブラリが多数あります。たとえば、Underscore は 1 つを提供します (これを と呼びますindexOf)。

JavaScript には配列がありません

基本的に、JavaScript にはハッシュ テーブルしかありません。標準関数は、キーが文字列キーに加えて整数であるハッシュ テーブル (これらを整数 hash-tablesまたはint-hash-tablesArrayと呼びます) を構築します。これらは配列と同様に機能しますが、特定の点で異なります。短所と長所があります。たとえば、int-hash-table から要素を削除するのは O(1) 操作ですが、配列から要素を削除するのは O(n) 操作です (残りの要素を新しい配列にコピーする必要があるため)。これが、JavaScript の関数が非常に高速である理由です。欠点は、実装の複雑さです。Array.prototype.splice

そのため、JavaScript のコンテキストで言うとArray、int-hash-table として理解され、それに関連するすべての漸近的な複雑さが生じます。これは、int-hash-table 内で文字列値を検索する場合、O(n) 操作になることを意味します。それを行うための標準関数があります: Array.prototype.indexOf. ただし、キーを探したい場合は、と の2 つの関数がinありObject.prototype.hasOwnPropertyます。

やや直感に反する：

[1, 2, 3].hasOwnProperty(0); // true
0 in [1, 2, 3]; // true

この 2 つの違いについては、さらに説明する必要があります。これは、JavaScript のすべてのものはオブジェクトであり、オブジェクトのような機能を備えているという事実に関連しています。そのような機能の 1 つはprototype、オブジェクトとそのプロトタイプの間のリンクです。これは、オブジェクトのプロパティを含むハッシュ テーブルの階層構造です。

  • inオブジェクトの直接のハッシュ テーブルを検索し、このオブジェクトのプロトタイプのハッシュ テーブルを再帰的に検索します。

  • 一方Object.prototype.hasOwnProperty、直接のハッシュテーブルのみを調べます。もっと速いはずだと思うかもしれませんが、結論に飛びつくのを待ってください。

JavaScript は動的な性質を持っているため、すべての関数呼び出しは動的であり、フェイル セーフなコード実行を確実にするために、環境は細心の注意を払う必要があります。これは、JavaScript 関数呼び出しが非常に高価であることを意味します。したがって、理論的には逆になるはずですが、通過する方が通過Object.prototype.hasOwnPropertyするよりもはるかに費用がかかる可能性があります。inただし、十分な高さの継承ツリーと十分な継承プロパティがあれば、最終的にObject.prototype.hasOwnPropertyは引き継がれます。

より良い直感を得るためのいくつかの例:

>>> var array = [1, 2, 3];
undefined
>>> 3 in array;
false
>>> array.hasOwnProperty(3);
false
>>> 3 in array;
false
>>> array.__proto__ = [1, 2, 3, 4];
[1, 2, 3, 4]
>>> 3 in array;
true
>>> array.hasOwnProperty(3);
false
于 2013-10-20T12:26:04.403 に答える
7

コメントの @nnnnnn から:

次のように、配列をオブジェクトに変換します。

object = {}
array.forEach(function(string) { // Not cross-browser compatible, it's just an example
  object[string] = 1;
}

次に、次のようなルックアップを実行します。

if (string in object) {
于 2013-10-20T10:12:18.440 に答える