検索時間をObjectよりも遅く設定しますか？

Question

私は、挿入/追加と参照の点でSetの実装がObject（Google Chromeで実行）より高速であるという確信を確かめることにしました。私の結果はやや混乱していた。

x = {}; 
y = new Set(); 

console.time('Insert into Object'); 
for (var i = 0; i < 1000000; i++) { 
    x[i] = 0; 
} 
console.timeEnd('Insert into Object'); 

console.time('Insert into Set'); 
for (i = 0; i < 1000000; i++) { 
    y.add(i); 
} 
console.timeEnd('Insert into Set'); 

var t = 0; 

console.time('Retrieve from Object'); 
for (i = 0; i < 1000000; i++) { 
    t = x[i]; 
} 
console.timeEnd('Retrieve from Object'); 

console.time('Retrieve from Set'); 
for (i = 0; i < 1000000; i++) { 
    t = y.has(i); 
} 
console.timeEnd('Retrieve from Set'); 

VM19742:9 Insert into Object: 1341.777ms 
VM19742:15 Insert into Set: 1473.025ms 
VM19742:23 Retrieve from Object: 1469.717ms 
VM19742:29 Retrieve from Set: 1666.430ms 

ご覧のとおり、このセットはオブジェクトよりも少し悪い結果でした。これは、基本的な実装が値を格納する余分のオーバーヘッドなしでオブジェクトと同じになると思ったので私を混乱させます。これはなぜ誰にも特別な洞察力がありますか？

Answer 1

質問に対処するには、値を保存する必要があるかどうかを確認するために既存の値をチェックするよりも、値を保存する方が遅くなると思われるのはなぜですか？

私はコードを変更して配列も含めました。

x = {}; 
y = new Set(); 
z = []; 

console.time('Insert into Object'); 
for (var i = 0; i < 1000000; i++) { 
    x[i] = 0; 
} 
console.timeEnd('Insert into Object'); 

console.time('Insert into Set'); 
for (i = 0; i < 1000000; i++) { 
    y.add(i); 
} 
console.timeEnd('Insert into Set'); 

console.time('Insert into Array'); 
for (i = 0; i < 1000000; i++) { 
    z[i] = 0; 
} 
console.timeEnd('Insert into Array'); 

var t = 0; 

console.time('Retrieve from Object'); 
for (i = 0; i < 1000000; i++) { 
    t = x[i]; 
} 
console.timeEnd('Retrieve from Object'); 

console.time('Retrieve from Set'); 
for (i = 0; i < 1000000; i++) { 
    t = y.has(i); 
} 
console.timeEnd('Retrieve from Set'); 

console.time('Retrieve from Array'); 
for (i = 0; i < 1000000; i++) { 
    t = z[i]; 
} 
console.timeEnd('Retrieve from Array'); 

console.log(t); 

通常、一つはnは数ある超えない O（N）を（であるべきである集合内の既存の値を確認しながらオブジェクトに格納することは、O（1）時間複雑であることを期待しますセット内のアイテム）、セットが大きくなるにつれてセットが遅くなることが予想されるはずです。このパフォーマンスはインプリメンテーションごとに異なる場合もあります。つまり、異なるJavaScriptランタイムが異なる動作をする可能性があります。

、実際に

は、それは我々が見まさにそれだ。（私のマシンで実行されている）

（あなたのコード）

Insert into Object: 67.558ms 
Insert into Set: 259.841ms 
Insert into Array: 64.297ms 
Retrieve from Object: 19.337ms 
Retrieve from Set: 149.968ms 
Retrieve from Array: 3.981ms 

しかし、我々はあなたの挿入テストを変更した場合、継続的に同じ値を再度追加私たちに物事のカップルを告げる

Insert into Object: 19.103ms 
Insert into Set: 40.645ms 
Insert into Array: 16.384ms 
Retrieve from Object: 40.116ms 
Retrieve from Set: 30.672ms 
Retrieve from Array: 70.050ms 

：私たちはこれを見...

。第1に、異なるタイプは、コレクションのサイズに対して異なった感受性を持ちます。第2に、存在しないキーを配列またはオブジェクトから取り出すことは、（少なくともこの特定の実装では）同じ値のセットをチェックするよりも遅くなります。

最後の注意として

私はそれは我々がの反復（または約ための第二の下でも取る事の相対的なパフォーマンスについて議論していることをここで注意することが重要だと思う秒、およびあなたのテストで半分）。それは既にかなり速いです。これを将来読んでいる人にとっては、意味的に必要なデータ構造を選択することを忘れないでください。これら3つのうちのどれかは、パフォーマンスの観点からは完全に良い選択です。プログラムを最も良くするものをとお選びください。

Answer 2

テストケースに多少の瑕疵があります。

1. 整数キーを一貫して使用するため、オブジェクトはおそらく配列に対して最適化されます。
2. オブジェクト内のルックアップは、より適切にはx.hasOwnProperty(key)またはx[key]!==undefinedを使用します。