26

次のコードを試しました (Google Chrome と nodejs で同様の結果が表示されます):

var t = new Array(200000); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 27839.499ms
undefined

次のテストも実行しました。

var t = []; console.time('wtf'); for (var i = 0; i < 400000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 449.948ms
undefined
var t = []; console.time('wtf'); for (var i = 0; i < 400000; ++i) {t.push(undefined);} console.timeEnd('wtf');
wtf: 406.710ms
undefined

しかし、Firefox では、最初のバリアントですべて問題ないように見えます。

>>> var t = new Array(200000); console.time('wtf'); ...{t.push(Math.random());} console.timeEnd('wtf');
wtf: 602ms

V8 ではどうなりますか?

UPD *魔法のようにパフォーマンスを低下させる*

var t = new Array(99999); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 220.936ms
undefined
var t = new Array(100000); t[99999] = 1; console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 1731.641ms
undefined
var t = new Array(100001); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 1703.336ms
undefined
var t = new Array(180000); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 1725.107ms
undefined
var t = new Array(181000); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 27587.669ms
undefined
4

2 に答える 2

59

事前に割り当てる場合は、使用しないでください.push。ハッシュ テーブルに基づくスパース配列が作成されるためです。C 配列によってサポートされる最大 99999 要素までのスパース配列を事前に割り当てることができます。その後、それはハッシュテーブルになります。

2 番目の配列では、0 から始まる連続した方法で要素を追加しているため、ハッシュ テーブルではなく、実際の C 配列によってサポートされます。

大まかに：

配列のインデックスが 0 から長さ 1 までうまく行き、穴がなければ、高速な C 配列で表すことができます。配列に穴がある場合、はるかに遅いハッシュ テーブルで表されます。例外は、サイズが 100000 未満の配列を事前に割り当てた場合、配列に穴があっても、C 配列によってバックアップされる可能性があることです。

var a = new Array(N); 

//If N < 100000, this will not make the array a hashtable:
a[50000] = "sparse";

var b = [] //Or new Array(N), with N >= 100000
//B will be backed by hash table
b[50000] = "Sparse";
//b.push("Sparse"), roughly same as above if you used new Array with N > 0
于 2013-06-06T12:25:24.683 に答える