Javascript在数组中添加相同的元素N次

Question

假设我有这样的 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)
    }
}

但这显然需要时间来处理大数据，我们是否可以重新设计上述功能以使其更有效率？

Answer 1

在我看来，这里真正的问题是构造重复 "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%，实际上比二进制数组方法稍微简单一些。

希望这可以帮助!