JavaScript配列内の要素を見つける効果的な方法

StackOverflow https://stackoverflow.com/questions/642046

質問

タイトル付きの配列を使用しています。各タイトルインデックスは、指定されたタイトルのhtmlを含むデータベースのIDに対応します。

タイトルの1つを含む文字列があるとしましょう。

title = "why-birds-fly";
titles[] // an array which contains all the titles

文字列＆quot; title＆quot;を使用するには対応するIDを取得するには：

for (i = 0; i < titles.length-1; i++) {
  if (titles[i] == title)
    return i+1;
}

私が使用できる別の方法は、タイトルの正反対のタイトル配列とともに連想配列を作成することです。つまり、文字列をインデックスとして使用し、数値を返します。

titles_id {blah:0,why-birds-fly:1,blah2:2}

次に、次の方法でIDにアクセスできます。

return titles_id[title]+1;

CPU、メモリなどを考慮して最も効果的なものは何ですか？

また、私のロジックがすべて間違っているかどうかを教えてください。

ありがとう ウィレム

役に立ちましたか？

解決

線形検索アプローチには、O（n）の複雑さがあり、最悪の場合は連想配列アプローチのケースはおそらくO（log n）です（JSエンジンがハッシュを使用していて衝突が発生していない場合は、 best ケースはO（1）です）。 JSエンジンが通常連想配列/オブジェクトをどのように実装するかに依存しますが、必ずO（n）を破ります。

したがって、2番目のアプローチは高速になりますが、もちろんより多くのメモリを使用します。これは非常に典型的なトレードオフであり、速度は向上しますが、使用するメモリは増加します。その取引を行うかどうかを決定できます。

他のヒント

保存する必要があるキーと値のペアの数を考慮することも重要です。 50未満（実装に依存）の場合、ハッシュ値の計算と衝突の解決のコストのために、線形検索の実行はハッシュテーブルルックアップの実行と同じくらい効率的です。例外は、Google chrome v8 JavaScriptエンジンは、オブジェクトのプロパティの直接ルックアップを実行できるようにするすべてのオブジェクトの一種のキャッシュバージョンを保持するため、ハッシュクラスとしてのObjectクラスの使用は高速になる可能性がありますが、このキャッシュバージョンを作成するコストが、小さなリストのメリットを上回るかどうかはわかりません。

最初のメソッドで配列のindexOf関数を使用できます。

以下はMozilla Developerからの情報です。 https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference： Objects：Array：indexOf

indexOfはECMA-262標準のJavaScript拡張機能です。そのため、標準の他の実装には存在しない場合があります。これを回避するには、スクリプトの先頭に次のコードを挿入して、ネイティブにサポートしていないECMA-262実装でindexOfを使用できるようにします。このアルゴリズムは、FirefoxとSpiderMonkeyで使用されているものとまったく同じです。

if (!Array.prototype.indexOf)
{
  Array.prototype.indexOf = function(elt /*, from*/)
  {
    var len = this.length >>> 0;

    var from = Number(arguments[1]) || 0;
    from = (from < 0)
         ? Math.ceil(from)
         : Math.floor(from);
    if (from < 0)
      from += len;

    for (; from < len; from++)
    {
      if (from in this &&
          this[from] === elt)
        return from;
    }
    return -1;
   };
}

Javascript配列では、タイトル「quot; why-birds-fly」」などの値を使用できます。インデックス用。

例：   var title =＆quot; why-birds-fly＆quot ;;

var TitleArray [] = new Array（）;

TitleArray [title] = id;

その後、タイトルでIDに直接アクセスできます：

Return TitleArray [title];

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top