Fastest way to reset a multidimensional array?

Question

Say I have a two-dimensional array: vectors[x][y] , and the original structure of the array looks like this:

 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,] ] 

After some calculations, the data in the array is randomized. What is the fastest way and the most efficient way to return an array to its original state?

I know that I could just recode the above null array and set the vectors again, but I also know that an algorithm such as:

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

- O (x * y).

So which is better? And is there a better, even faster / more efficient way to solve this problem?

And for the general case of zeroing a multidimensional array of any length, what is the best way? (I work in JavaScript, if that matters)

Answer 1

Here are my two cents:

I would keep a clean copy of the original array for maximum performance. You can either save the reference copy

 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] ]; 

or make a dynamic clean clone of the original array using a slice ((recursively in your case for a deep copy):

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

Regardless, the approach of dropping a vector link to the original copy will be faster than looping and resetting each node . If your old vector array object is no longer referenced, JavaScript will garbage collect it.

With that said, the question is to get a clean copy every time. Once the hard-coded instance gives you one clean copy, and you have to clone it after that. You also don't want to dynamically generate using the same loops as a reset option. My advice is to write a clone function that simply returns a new hard or initialized array:

 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); 

Ideally, it is best to compare different approaches.

EDIT Thanks to Vega, I modified his test to test three approaches. In Chrome and IE9, this solution seems to be the fastest, in FF (15.0.1) manual iteration seems to be faster (perhaps memory allocation / control is slower in FF). http://jsperf.com/array-zero-test/2

Answer 2

So far, it looks like we have 2 possible options.

• Rewrite everything with zeros. (Your decision)

• Keep a record of all modified elements and only reset those. record[0].x = 3; record[0].y = 5; etc. However, you still need to scroll once through the recording. To explain this further, I mean that every time an element in an array is set to a value, you must write this placement of the element in the array. Then, using a loop, you can visit each element and set it to 0. Thus, if you had a sparse array, it would be more efficient.

Depending on the implementation, I can understand why you will need # 2 instead of # 1 ... but if you seriously have a sufficiently large matrix that you need to worry about analyzing the algorithm, you might consider doing something like server preprocessing.

Answer 3

If I were you, I would have an empty array and whenever I reset the value, I just replaced the variable with an empty one. It will only cost you one more empty array if you have a lot to do with restarting and initializing.

Update

Perhaps this will help you with this:

 var empty = function() { 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 vectors = new empty(); for (var i = 0; i < 10; i++) { for (var x = 0; x < vectors.length; x++) for (var y = 0; y < vectors[x].length; y++) vectors[x][y] = x * y + 2; // Some values just for changing the array. vectors = new empty(); } 

Greetings.

Answer 4

I will take the risk and say that the fastest way to assign the same value to all elements is to call Array.map ().

But there is a catch. Please note that this will have incredibly fast performance in browsers that originally implemented this method and will only have normal performance in other browsers. Also note that .map () is not available in some older browsers, so you need to use Underscore.js or any other library that provides this method.

Answer 5

Another other way to deal with the problem is to use a linear array and calculate the linear index from the x, y indices when performing your updates.

Initialization is just one for loop with O (x + y) time