10

次のコード例を見てください。

var myObject = {};
var i = 100;

while (i--) {
    myObject["foo"+i] = new Foo(i);
}

console.log(myObject["foo42"].bar());

少し質問があります。

主要なエンジン（IE、Mozilla、Chrome、Safari）は、キーと値のペアを格納するためにどのような種類のデータ構造を使用しますか？ある種の二分探索木であることを望みますが、リンクリストを使用する可能性があると思います（反復が挿入順に行われるため）。

彼らが検索ツリーを使用する場合、それは自己バランスですか？上記のコードで従来の検索ツリーを使用すると、不均衡なツリーが作成されるため、バランスの取れたツリーのO（log n）ではなく、検索のO（n）の最悪のシナリオが発生します。

データ構造からキーを効率的に取得する必要があるライブラリを作成するため、これを求めているだけです。独自のまたは既存の赤黒木を実装することはできますが、ネイティブオブジェクトのプロパティを使用する方がよいでしょう。十分に効率的です。

4

1 に答える 1

21

この質問は、いくつかの理由で答えにくいです。まず、最新のブラウザーはすべて、実行中にコードを大幅かつ動的に最適化するため、プロパティにアクセスするために選択されるアルゴリズムは、同じコードでも異なる可能性があります。次に、各エンジンは異なるアルゴリズムとヒューリスティックを使用して、使用するアクセス アルゴリズムを決定します。第三に、ECMA 仕様は、結果がどのように達成されるかではなく、結果がどうあるべきかを規定しているため、エンジンはこの分野で革新する自由が多くあります。

とはいえ、あなたの例を考えると、私がよく知っているすべてのエンジンは、何らかの形式のハッシュテーブルを使用して、に関連付けられた値を取得しfoo42ますmyobject. 連想配列のようなオブジェクトを使用する場合、JavaScript エンジンはハッシュ テーブルを優先する傾向があります。私が認識しているものは、文字列プロパティにツリーを使用していません。ハッシュ テーブルは、最悪の場合は O(N)、最良の場合は O(1) であり、キー ジェネレーターが適切であれば、O(N) よりも O(1) に近づく傾向があります。各エンジンには、O(N) を実行するために使用できるパターンがありますが、それはエンジンごとに異なります。バランスの取れたツリーは、最悪の場合 O(log N) を保証しますが、バランスの取れたツリーを変更しながらバランスを維持することは O(log N) ではなく、文字列キーの場合、ハッシュ テーブルは O(log N) よりも優れていることが多く、O(1) です。更新する (必要があると判断したら、

ただし、数値プロパティは特別です。範囲内のギャップがほとんどまたはまったくない整数数値プロパティを使用してオブジェクトにアクセスする場合、つまり、オブジェクトを配列のように使用する場合、値は O(1) アクセスでメモリの線形ブロックに格納される傾向があります。アクセスにギャップがある場合でも、エンジンはおそらく疎配列アクセスに移行し、最悪の場合は O(log N) になります。

識別子によるプロパティへのアクセスも特殊です。のようにプロパティにアクセスすると、

myObject.foo42

このコードを頻繁に実行し (つまり、この速度が重要です)、同じまたは類似のオブジェクトを使用すると、1 つまたは 2 つのマシン命令に最適化される可能性があります。オブジェクトが類似する理由もエンジンごとに異なりますが、同じリテラルまたは関数で構成されている場合、類似として扱われる可能性が高くなります。

JavaScript ベンチマークでまったくうまく機能するエンジンは、すべてのオブジェクトに同じアルゴリズムを使用しません。それらはすべて、オブジェクトがどのように使用されているかを動的に判断し、それに応じてアクセス アルゴリズムを調整しようとする必要があります。

于 2012-08-22T07:42:57.660 に答える