假设我有这样的 map :
var map = {"a" : 100, "b" : 200, "c": 700};
我想要一个由 "a"100 次、"b"200 次和 "c"700 次组成的数组:
map_array = [a, a, a, a, ... a, b, b, b, ... b, c, c, c, ... c]
简单的解决方案是循环频率时间并插入数组:
var map_array = []
for(key in map)
{
for(var i=1; i <= map[key] ; i++)
{
map_array.push(key)
}
}
但这显然需要时间来处理大数据,我们是否可以重新设计上述功能以使其更有效率?
最佳答案
在我看来,这里真正的问题是构造重复 "a"
的子数组。的, "b"
的,和 "c"
的。一旦你有了它们,你就可以 concat
它们来制作你的最终阵列。
所以,我们真正想要的是一个函数 f(x, n)
它创建了一个填充了 n
的数组x
的。
因此,作为标准测试平台,我将定义一对 clock
职能。第一个测量一些数组填充函数创建 500000 个数组所需的时间,每个数组包含 2187 "a"
的。第二个测量一些数组填充函数创建 500 个数组所需的时间,每个数组包含 1594323 "a"
的。我选择 3 的幂是因为我的一些算法是基于二进制的,我想避免任何巧合。无论如何,所有算法都适用于任何 n
.
var clock1=function(f)
{
var m,t;
m=500000;
t=Date.now();
while(m--)
{
f("a", 2187);
}
t=Date.now()-t;
return t;
};
var clock2=function(f)
{
var m,t;
m=500;
t=Date.now();
while(m--)
{
f("a", 1594323);
}
t=Date.now()-t;
return t;
};
我正在以严格模式运行纯 v8 的本地机器上运行此测试。以下是
f
的一些候选人:线性方法
正如亚历克斯已经建议的那样,您可以使用线性循环来做到这一点。只需定义一个数组并运行一个循环来执行
n
次,每次加一个 x
到我们的数组。var f=function(x,n)
{
var y;
y=Array(n);
while(n--)
{
y[n]=x;
}
return y;
};
我们可以使用计数变量进行优化,
n
避免拨打 push
或 y.length
,以及将数组预初始化为所需的长度。 (均由亚历克斯建议。)我的倒退 while
循环只是一个旧习惯,可能 boost performance slightly .此函数需要 2200 毫秒才能通过
clock1
和 90658 毫秒才能通过 clock2
.部分二进制方法
我们也可以尝试使用二进制连接来构建它。这个想法是你从一个单元素数组开始,然后,如果它的长度明显小于目标长度,你
concat
它与自身,有效地加倍。当它接近目标大小时,切换回一次添加一个元素,直到达到目标大小:var f=function(x,n)
{
var y,m;
y=[x];
m=1;
while(m<n)
{
if(m*2<=n)
{
y=y.concat(y);
m*=2;
}
else
{
y[m]=x;
m++;
}
}
return y;
};
在这里,
m
只是一个计数变量,用于跟踪 y 的大小。此函数需要 3630 毫秒才能通过
clock1
和 42591 毫秒才能通过 clock2
,对于小数组,它比线性方法慢 65%,但对于大数组快 112%。全二进制方法
然而,我们可以通过使用完整的二进制结构进一步提高性能。部分二进制方法会受到影响,因为它在接近其目标长度(平均大约 75% 的路径)时被迫切换到逐个元素的加法。我们可以解决这个问题:
首先,将目标大小转换为二进制并保存到数组中。现在,定义
y
成为单元素数组 z
成为一个空数组。然后,循环(向后)遍历二进制数组,对于每个元素 concat
ing y
与自己。在每次迭代中,如果各自的二进制位为1,则保存y
进入 z
.最后,concat
z
的所有元素一起。结果是您的完整数组。因此,为了填充长度为 700 的数组,它首先将 700 转换为二进制:
[1,0,1,0,1,1,1,1,0,0]
向后循环,它执行 9
concat
和 6 个元素相加,生成 z
看起来像这样:[0,0,4,8,16,32,128,512]
// I've written the lengths of the sub-arrays rather than the arrays themselves.
当它
concat
一切尽在 z
一起,它得到一个长度为 700 的数组,即我们的结果。var f=function(x,n)
{
var y,z,c;
c=0;
y=[x];
z=[];
while(n>0)
{
if(n%2)
{
z[c++]=y;
n--;
}
if(n===0)
{
break;
}
n/=2;
y=y.concat(y);
}
return z.concat.apply([],z);
};
为了优化,我在这里压缩了二进制转换步骤和循环。
z.concat.apply([],z)
使用了一点 apply
变平的魔法z
, 一个数组数组,变成一个数组。出于某种原因,这比连接到 z
更快在飞行中。第二个if
语句防止它加倍 y
计算完成后的最后一次。此函数需要 3157 毫秒才能通过
clock1
和 26809 毫秒通过 clock2
,对于小数组来说比部分二进制方法快 15%,对于大数组快 59%。对于小数组,它仍然比线性方法慢 44%。二进制字符串方法
concat
功能很奇怪。相对而言,要连接的数组越大,效率就越高。换句话说,组合两个长度为 100 的数组比使用 concat
组合四个长度为 50 的数组要快得多。 .结果,随着涉及的数组变大,concat
变得比 push
更有效率,或直接赋值。这是二进制方法比大型数组的线性方法更快的主要原因之一。不幸的是,concat
也受到影响,因为它每次都复制涉及的数组。因为数组是对象,所以这会变得非常昂贵。字符串没有数组那么复杂,所以也许使用它们可以避免这种消耗?我们可以简单地使用字符串加法(类似于串联)来构造我们的数组,而 split
结果字符串。基于字符串的完整二进制方法如下所示:
var f=function(x,n)
{
var y,z;
y=""+x;
z="";
while(n>0)
{
if(n%2)
{
z+=y;
n--;
}
if(n===0)
{
break;
}
y+=y;
n/=2;
}
return z.split("");
};
此函数需要 3484 毫秒才能通过
clock1
和 14534 毫秒通过 clock2
,使其在计算小数组时比基于数组的全二进制方法慢 10%,但对大数组快 85%。所以,总的来说,它是一个混合包。线性方法在较小的数组上获得非常好的性能并且非常简单。然而,二进制字符串方法在大型数组上快了 524%,实际上比二进制数组方法稍微简单一些。
希望这可以帮助!
关于Javascript在数组中添加相同的元素N次,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23237610/