ここで言う疎配列とは要素が飛び飛びに埋め込まれた配列の事。例えば以下のような配列
a=[,1,,22,,,,333,,,,,,,,55555]
疎配列の使い所さんと言えばhash表。このような配列の要素をもれなく読みあさる速度を検証するのが今回の企画。for inとforEachで対決して頂く。
for(let n=9,a=256;n--;a+=a)for(let b=32;b;b>>=1){
let A=[],t=0,u,c=0;
for(;t<a;t+=b)A[t]=0,c++;//埋め込み
t=performance.now();
for(let c=32,d;c--;)for(d in A);
t=performance.now()-t;
u=performance.now();
for(let c=32,d;c--;)A.forEach((a,b)=>a);
u=performance.now()-u;
console.log("size",a,"interval",b-1,"items",c,"time",t,u)
}
以下の表に示す間隔とは、要素同士の隙間。0というのはもはや疎配列ではない…と突っ込みたくなるが気にしてはいけない。所要時間の単位はms、Browserはchrome。
御覧の通り概ねforEachが優勢(Firefoxも同様)。しかしなぜか配列長が32768、65536、間隔が31の時のforEachがべらぼうに遅い。ちなみに65536を超えてからも間隔が31以上だとforEachは急激に遅くなる
| 配列長 | 間隔 | 要素数 | for in | forEach |
|---|---|---|---|---|
| 256 | 31 | 8 | 0.199 | 0.100 |
| 256 | 15 | 16 | 0 | 0.200 |
| 256 | 7 | 32 | 0.200 | 0 |
| 256 | 3 | 64 | 0.100 | 0.099 |
| 256 | 1 | 128 | 0.299 | 0.100 |
| 256 | 0 | 256 | 0.5 | 0.299 |
| 512 | 31 | 16 | 0.200 | 0 |
| 512 | 15 | 32 | 0.200 | 0.099 |
| 512 | 7 | 64 | 0.200 | 0.099 |
| 512 | 3 | 128 | 0.900 | 0.299 |
| 512 | 1 | 256 | 0.599 | 0.299 |
| 512 | 0 | 512 | 1.100 | 0.099 |
| 1024 | 31 | 32 | 0.299 | 0 |
| 1024 | 15 | 64 | 1.200 | 0.099 |
| 1024 | 7 | 128 | 0.399 | 0 |
| 1024 | 3 | 256 | 0.600 | 0.099 |
| 1024 | 1 | 512 | 1 | 0.300 |
| 1024 | 0 | 1024 | 1.899 | 0.100 |
| 2048 | 31 | 64 | 0.599 | 0.200 |
| 2048 | 15 | 128 | 1.100 | 0.199 |
| 2048 | 7 | 256 | 0.700 | 0.299 |
| 2048 | 3 | 512 | 1.100 | 0.299 |
| 2048 | 1 | 1024 | 2.200 | 0.200 |
| 2048 | 0 | 2048 | 3.900 | 0.399 |
| 4096 | 31 | 128 | 0.700 | 0.400 |
| 4096 | 15 | 256 | 1.299 | 0.400 |
| 4096 | 7 | 512 | 1.299 | 0.5 |
| 4096 | 3 | 1024 | 2.600 | 0.399 |
| 4096 | 1 | 2048 | 3.900 | 0.400 |
| 4096 | 0 | 4096 | 7.5 | 0.700 |
| 8192 | 31 | 256 | 1.699 | 0.200 |
| 8192 | 15 | 512 | 2.200 | 0.099 |
| 8192 | 7 | 1024 | 2.900 | 0.099 |
| 8192 | 3 | 2048 | 4.600 | 0.200 |
| 8192 | 1 | 4096 | 7.299 | 0.200 |
| 8192 | 0 | 8192 | 14 | 0.200 |
| 16384 | 31 | 512 | 3.700 | 0.200 |
| 16384 | 15 | 1024 | 4.799 | 0.299 |
| 16384 | 7 | 2048 | 6.099 | 0.299 |
| 16384 | 3 | 4096 | 9.100 | 0.299 |
| 16384 | 1 | 8192 | 14.899 | 0.5 |
| 16384 | 0 | 16384 | 28.200 | 0.299 |
| 32768 | 31 | 1024 | 10.100 | 68.599 |
| 32768 | 15 | 2048 | 17.400 | 9.799 |
| 32768 | 7 | 4096 | 25 | 10.199 |
| 32768 | 3 | 8192 | 52.700 | 13 |
| 32768 | 1 | 16384 | 83.100 | 20.5 |
| 32768 | 0 | 32768 | 160.799 | 30.5 |
| 65536 | 31 | 2048 | 20.799 | 142.399 |
| 65536 | 15 | 4096 | 29.299 | 17.100 |
| 65536 | 7 | 8192 | 65.900 | 19.099 |
| 65536 | 3 | 16384 | 77.099 | 23.799 |
| 65536 | 1 | 32768 | 156.5 | 35.5 |
| 65536 | 0 | 65536 | 296.400 | 49.200 |
for ofは疎部まで読みあさり、mapは無駄な複製処理を行いますが、ついでなので検証
for(let n=9,a=256;n--;a+=a)for(let b=32;b;b>>=1){
let A=[],t=0,u,v,w,c=0;
for(;t<a;t+=b)A[t]=0,c++;//埋め込み
t=performance.now();
for(let c=32,d;c--;)for(d in A);
t=performance.now()-t;
u=performance.now();
for(let c=32,d;c--;)A.forEach((a,b)=>a);
u=performance.now()-u;
v=performance.now();
for(let c=32,d;c--;)A.map((a,b)=>a);
v=performance.now()-v;
w=performance.now();
for(let c=32,d;c--;)for(d of A);
w=performance.now()-w;
console.log("size",a,"interval",b-1,"items",c,"time",t,u,v,w)
}
| 配列長 | 間隔 | 要素数 | for in | forEach | map | for of |
|---|---|---|---|---|---|---|
| 256 | 31 | 8 | 0 | 0.200 | 0.099 | 0.800 |
| 256 | 15 | 16 | 0.099 | 0.200 | 0.099 | 0.900 |
| 256 | 7 | 32 | 0.099 | 0.100 | 0.099 | 0.799 |
| 256 | 3 | 64 | 0.199 | 0.200 | 0.100 | 1.799 |
| 256 | 1 | 128 | 1.5 | 0.200 | 0.199 | 1 |
| 256 | 0 | 256 | 0.600 | 0.399 | 0.300 | 0.899 |
| 512 | 31 | 16 | 0.200 | 0.200 | 0.299 | 1.799 |
| 512 | 15 | 32 | 0.700 | 0.099 | 0.300 | 1.399 |
| 512 | 7 | 64 | 0.299 | 0.200 | 0.200 | 1.700 |
| 512 | 3 | 128 | 0.299 | 0.300 | 0.299 | 1.799 |
| 512 | 1 | 256 | 0.599 | 0.400 | 0.400 | 1.799 |
| 512 | 0 | 512 | 1.099 | 0.799 | 0.700 | 1.700 |
| 1024 | 31 | 32 | 0.200 | 0.299 | 0.400 | 1.799 |
| 1024 | 15 | 64 | 0.199 | 0.400 | 1.799 | 1.299 |
| 1024 | 7 | 128 | 0.800 | 0.399 | 0.400 | 4.200 |
| 1024 | 3 | 256 | 0.699 | 0.5 | 1 | 1.300 |
| 1024 | 1 | 512 | 1 | 0.599 | 0.800 | 1.299 |
| 1024 | 0 | 1024 | 2 | 0.899 | 0.900 | 1.400 |
| 2048 | 31 | 64 | 0.5 | 0.599 | 0.700 | 3.899 |
| 2048 | 15 | 128 | 0.5 | 0.599 | 0.700 | 3 |
| 2048 | 7 | 256 | 0.799 | 0.5 | 0.799 | 3 |
| 2048 | 3 | 512 | 1.399 | 0.700 | 0.900 | 4.700 |
| 2048 | 1 | 1024 | 2.400 | 0.900 | 1.199 | 2.700 |
| 2048 | 0 | 2048 | 4.299 | 1.900 | 2 | 2.5 |
| 4096 | 31 | 128 | 0.799 | 1 | 1.399 | 4.300 |
| 4096 | 15 | 256 | 1 | 0 | 0.799 | 0.100 |
| 4096 | 7 | 512 | 1.399 | 0.100 | 0.899 | 0.200 |
| 4096 | 3 | 1024 | 2.299 | 0 | 0.799 | 0 |
| 4096 | 1 | 2048 | 3.700 | 0.099 | 0.800 | 0.099 |
| 4096 | 0 | 4096 | 7.099 | 0.100 | 0.599 | 0.200 |
| 8192 | 31 | 256 | 1.899 | 0.200 | 1.400 | 0.200 |
| 8192 | 15 | 512 | 2.200 | 0.099 | 1.400 | 0.299 |
| 8192 | 7 | 1024 | 2.700 | 0.200 | 1.399 | 0.200 |
| 8192 | 3 | 2048 | 4.700 | 0.200 | 1.299 | 0.299 |
| 8192 | 1 | 4096 | 7.5 | 0.200 | 1.5 | 0.199 |
| 8192 | 0 | 8192 | 14.5 | 0.299 | 1.5 | 0.299 |
| 16384 | 31 | 512 | 3.399 | 0.400 | 2.799 | 0.400 |
| 16384 | 15 | 1024 | 5 | 0.199 | 2.900 | 0.5 |
| 16384 | 7 | 2048 | 6.5 | 0.300 | 2.599 | 0.400 |
| 16384 | 3 | 4096 | 8.700 | 0.299 | 2.5 | 0.5 |
| 16384 | 1 | 8192 | 15.900 | 0.299 | 3 | 0.399 |
| 16384 | 0 | 16384 | 30 | 0.200 | 3.599 | 0.799 |
| 32768 | 31 | 1024 | 10.199 | 76.5 | 72.800 | 82.899 |
| 32768 | 15 | 2048 | 14.5 | 8.600 | 11.5 | 50.200 |
| 32768 | 7 | 4096 | 25.200 | 9.700 | 12.299 | 40.900 |
| 32768 | 3 | 8192 | 46.700 | 11.699 | 15.400 | 36.599 |
| 32768 | 1 | 16384 | 88.5 | 17.5 | 25.400 | 37.299 |
| 32768 | 0 | 32768 | 157.799 | 28.700 | 40.5 | 35.899 |
| 65536 | 31 | 2048 | 21.799 | 142.200 | 151.299 | 151.200 |
| 65536 | 15 | 4096 | 28.299 | 16.5 | 29.399 | 92.900 |
| 65536 | 7 | 8192 | 59.200 | 19.399 | 31.299 | 76.300 |
| 65536 | 3 | 16384 | 79.299 | 25 | 39 | 75.200 |
| 65536 | 1 | 32768 | 156.599 | 34.200 | 50.200 | 70.700 |
| 65536 | 0 | 65536 | 292.700 | 51.799 | 74.400 | 66.099 |