9

假设我有一个二维数组：vectors[x][y]，初始数组结构如下所示：

vectors = [    
 [0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0,]
]

经过一些计算，数组中的数据是随机的。将数组返回到初始状态的最快方法和最有效方法是什么？

我知道我可以硬编码上面的归零数组并再次设置向量等于它，但我也知道这样的算法：

for (var x = 0; x < vectors.length; x++) {
    for (var y = 0; y < vectors[x].length; y++) {
        vectors[x][y] = 0;
    }

}

是 O(x * y)。

那么哪种方法更好呢？有没有更好、更快/更有效的方法来解决这个问题？

对于将任意长度的多维数组归零的一般情况，这是最好的方法吗？（如果重要的话，我正在使用 JavaScript）

4

4 回答 4

3

这是我的两分钱：

我会保留原始阵列的干净副本以获得最快的性能。您可以保留引用的硬编码副本

var vectorsOrig = [    
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0]
];

或使用 slice 对初始数组进行动态干净克隆（（在您的情况下递归地进行深层复制）：

var clonedVectors = [0, 0, 0, 0, 0].slice(0);

无论如何，采用将矢量引用重置为原始副本的方法将比循环遍历和重置每个节点更快。如果您的旧向量数组对象不再被引用，JavaScript 将垃圾收集它。

话虽如此，问题就变成了每次都获得一个干净的副本。拥有一次硬编码实例将为您提供一个干净的副本，之后您必须克隆它。您也不想通过与重置选项类似的 for 循环进行动态生成。我的建议是编写一个克隆函数，它只返回一个新的硬编码或初始化数组：

function newVector() {
    return [    
     [0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0]
    ];
}
var vector = newVector();
vector[1][2] = 11;
console.dir(vector);
vector = newVector();  // your old array will be garbage-collected if no longer referenced by any other reference
console.dir(vector);

理想情况下，最好对各种方法进行基准测试。

编辑 感谢 Vega 的输入，我修改了他的测试以测试三种方法。在 Chrome 和 IE9 中，这个解决方案似乎是最快的，在 FF (15.0.1) 中手动迭代似乎更快（FF 中的内存分配/管理可能更慢）。http://jsperf.com/array-zero-test/2

于 2012-11-07T19:06:13.627 回答
1

So far, it sounds like we have 2 possible choices.

  1. Overwrite the whole thing with zeroes. (Your solution)

  2. Keep a record of all modified elements and only reset those ones. record[0].x = 3; record[0].y = 5; and so on However, you'll still need to loop once through the record. To explain it further, I mean that each time an element in the array is set to a value, you should record that element's placement in the array. Then, using a loop, you can visit each element and set it to 0. So, if you had a sparse array, it would be more efficient.

Depending on the implementation, I can see why you would want #2 instead of #1...but if you seriously have a large enough matrix that you need to worry about analyzing the algorithm, you might consider doing some kind of server pre-processing.

于 2012-11-07T18:41:17.703 回答
0

另一种看待问题的不同方法是使用线性数组并在进行更新时从 x、y 索引计算线性索引。

然后初始化只是一个for时间为 O(x+y) 的循环

于 2012-11-07T18:50:09.907 回答
-1

我会冒险说为所有元素分配相同值的最快方法是调用 Array.map()。

但是，这里有一个问题。请注意，这将在本机实现该方法的浏览器上具有令人难以置信的快速性能，并且在其他浏览器中将具有通常的性能。另请注意， .map() 在某些旧浏览器中不可用，因此您需要使用 Underscore.js 或任何其他提供该方法的库。

于 2012-11-07T18:38:20.953 回答