ansaurus

Question

Most efficient way to create a zero filled JavaScript array?

Answer 1

+3 A:

using object notation

var x = [];

zero filled? like...

var x = [0,0,0,0,0,0];

filled with 'undefined'...

var x = new Array(7);

obj notation with zeros

var x = [];
for (var i = 0; i < 10; i++) x[i] = 0;

As a side note, if you modify Array's prototype, both

var x = new Array();

and

var y = [];

will have those prototype modifications

At any rate, I wouldn't be overly concerned with the efficiency or speed of this operation, there are plenty of other things that you will likely be doing that are far more wasteful and expensive than instanciating an array of arbitrary length containing zeros.

Allen 2009-08-18 18:13:06

Err... there are no `null`s in this array - `var x = new Array(7);`

kangax 2009-08-18 18:25:02

right you are good sir, updated

Allen 2009-08-18 18:36:04

Answer 2

+2 A:

function makeArrayOf(value, length) {
  var arr = [], i = length;
  while (i--) {
    arr[i] = value;
  }
  return arr;
}

makeArrayOf(0, 5); // [0, 0, 0, 0, 0]

makeArrayOf('x', 3); // ['x', 'x', 'x']

Note that while is usually more efficient than for-in, forEach, etc.

kangax 2009-08-18 18:22:08

Isn't the `i` local variable extraneous? `length` is passed by value so you should be able to decrement it directly.

Sean Bright 2009-08-18 18:26:46

Of course. I only added `i` for convention/clarity.

kangax 2009-08-18 18:28:16

Answer 3

+6 A:

Pre-allocate, then backward fill:

function newFilledArray(len, val) {
    var rv = new Array(len);
    while (--len >= 0) {
        rv[len] = val;
    }
    return rv;
}

EDIT 2009/08/19: Matthew Crumley points out that counting down is markedly slower on Firefox than counting up, a result I can confirm -- it's the array part of it (looping down to zero is still faster than looping up to a limit in a var). Apparently adding the elements to the array in reverse order is a slow op on Firefox. In fact, the results vary quite a bit by JavaScript implementation, here's a quick and dirty test page (below) for browser implementations (very dirty, doesn't yield during tests, so provides minimal feedback and will run afoul of script time limits). I recommend refreshing between tests; FF (at least) slows down on repeated tests if you don't

The fairly complicated version that uses Array#concat is faster than a straight init on FF as of somewhere between 1,000 and 2,000 element arrays. On Chrome's V8 engine, though, straight init wins out every time...

Here's the test page:

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"&gt;
<html>
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8">
<title>Zero Init Test Page</title>
<style type='text/css'>
body {
    font-family:    sans-serif;
}
#log p {
    margin:     0;
    padding:    0;
}
.error {
    color:      red;
}
.winner {
    color:      green;
    font-weight:    bold;
}
</style>
<script type='text/javascript' src='prototype-1.6.0.3.js'></script>
<script type='text/javascript'>
var testdefs = {
    'downpre':  {
        total:  0,
        desc:   "Count down, pre-decrement",
        func:   makeWithCountDownPre
    },
    'downpost': {
        total:  0,
        desc:   "Count down, post-decrement",
        func:   makeWithCountDownPost
    },
    'up':       {
        total:  0,
        desc:   "Count up (normal)",
        func:   makeWithCountUp
    },
    'downandup':  {
        total:  0,
        desc:   "Count down (for loop) and up (for filling)",
        func:   makeWithCountDownArrayUp
    },
    'concat':   {
        total:  0,
        desc:   "Concat",
        func:   makeWithConcat
    }
};

document.observe('dom:loaded', function() {
    var markup, defname;

    markup = "";
    for (defname in testdefs) {
        markup +=
            "<div><input type='checkbox' id='chk_" + defname + "' checked>" +
            "<label for='chk_" + defname + "'>" + testdefs[defname].desc + "</label></div>";
    }
    $('checkboxes').update(markup);
    $('btnTest').observe('click', btnTestClick);
});

function epoch() {
    return (new Date()).getTime();
}

function btnTestClick() {

    // Clear log
    $('log').update('Testing...');

    // Show running
    $('btnTest').disabled = true;

    // Run after a pause while the browser updates display
    btnTestClickPart2.defer();
}
function btnTestClickPart2() {

    try {
        runTests();
    }
    catch (e) {
        log("Exception: " + e);
    }

    // Re-enable the button; we don't yheidl
    $('btnTest').disabled = false;
}

function runTests() {
    var start, time, counter, length, defname, def, results, a, invalid, lowest, s;

    // Get loops and length
    s = $F('txtLoops');
    runcount = parseInt(s);
    if (isNaN(runcount) || runcount <= 0) {
        log("Invalid loops value '" + s + "'");
        return;
    }
    s = $F('txtLength');
    length = parseInt(s);
    if (isNaN(length) || length <= 0) {
        log("Invalid length value '" + s + "'");
        return;
    }

    // Clear log
    $('log').update('');

    // Do it
    for (counter = 0; counter <= runcount; ++counter) {

        for (defname in testdefs) {
            def = testdefs[defname];
            if ($('chk_' + defname).checked) {
                start = epoch();
                a = def.func(length);
                time = epoch() - start;
                if (counter == 0) {
                    // Don't count (warm up), but do check the algorithm works
                    invalid = validateResult(a, length);
                    if (invalid) {
                        log("<span class='error'>FAILURE</span> with def " + defname + ": " + invalid);
                        return;
                    }
                }
                else {
                    // Count this one
                    log("#" + counter + ": " + def.desc + ": " + time + "ms");
                    def.total += time;
                }
            }
        }
    }

    for (defname in testdefs) {
        def = testdefs[defname];
        if ($('chk_' + defname).checked) {
            def.avg = def.total / runcount;
            if (typeof lowest != 'number' || lowest > def.avg) {
                lowest = def.avg;
            }
        }
    }

    results =
        "<p>Results:" +
        "<br>Length: " + length +
        "<br>Loops: " + runcount +
        "</p>";
    for (defname in testdefs) {
        def = testdefs[defname];
        if ($('chk_' + defname).checked) {
            results += "<p" + (lowest == def.avg ? " class='winner'" : "") + ">" + def.desc + ", average time: " + def.avg + "ms</p>";
        }
    }
    results += "<hr>";
    $('log').insert({top: results});
}

function validateResult(a, length) {
    var n;

    if (a.length != length) {
        return "Length is wrong";
    }
    for (n = length - 1; n >= 0; --n) {
        if (a[n] != 0) {
            return "Index " + n + " is not zero";
        }
    }
    return undefined;
}

function makeWithCountDownPre(len) {
    var a;

    a = new Array(len);
    while (--len >= 0) {
        a[len] = 0;
    }
    return a;
}

function makeWithCountDownPost(len) {
    var a;

    a = new Array(len);
    while (len-- > 0) {
        a[len] = 0;
    }
    return a;
}

function makeWithCountUp(len) {
    var a, i;

    a = new Array(len);
    for (i = 0; i < len; ++i) {
        a[i] = 0;
    }
    return a;
}

function makeWithCountDownArrayUp(len) {
    var a, i;

    a = new Array(len);
    i = 0;
    while (--len >= 0) {
        a[i++] = 0;
    }
    return a;
}

function makeWithConcat(len) {
    var a, rem, currlen;

    if (len == 0) {
        return [];
    }
    a = [0];
    currlen = 1;
    while (currlen < len) {
        rem = len - currlen;
        if (rem < currlen) {
            a = a.concat(a.slice(0, rem));
        }
        else {
            a = a.concat(a);
        }
        currlen = a.length;
    }
    return a;
}

function log(msg) {
    $('log').appendChild(new Element('p').update(msg));
}
</script>
</head>
<body><div>
<label for='txtLength'>Length:</label><input type='text' id='txtLength' value='10000'>
<br><label for='txtLoops'>Loops:</label><input type='text' id='txtLoops' value='10'>
<div id='checkboxes'></div>
<br><input type='button' id='btnTest' value='Test'>
<hr>
<div id='log'></div>
</div></body>
</html>

T.J. Crowder 2009-08-18 18:29:02

Not sure that backwards filling would matter here, given you are only accessing elements (not deleting them) and you've already pre-allocated. Am I wrong?

Triptych 2009-08-18 20:52:27

the point of the backwards fill is not particularly to do with the array, it's to do with the escape condition for the while - the falsey 0 terminates the loop very efficiently

annakata 2009-08-18 20:54:19

(though I've just noticed this code doesn't actually make use of that)

annakata 2009-08-18 20:56:26

@annakata, you can't make use of that here, because 0 is a valid index.

Triptych 2009-08-18 20:59:52

@triptych: not true, all it takes is the right order - see my post

annakata 2009-08-18 21:05:55

T.J. Crowder 2009-08-18 21:06:28

(or kangax's - same thing there)

annakata 2009-08-18 21:07:18

@TJ: comparing to a constant is likely to achieve an infinite loop - *something* must change in the condition :)

annakata 2009-08-18 21:08:30

@annakata: Ha, ha. Comparing a *variable* to a constant.

T.J. Crowder 2009-08-18 21:10:41

Counting down in Firefox is much slower than counting up. I have no idea why, but in my tests, it was 10-15 times slower.

Matthew Crumley 2009-08-18 23:37:06

@Matthew: Nice one, just proves you should always test your assumptions. I've replicated your result and updated the answer.

T.J. Crowder 2009-08-19 07:29:38

In my tests, for an array of 1,000,000 elements, this method takes roughly 700ms. Joshua's function takes about 55ms, and Matthew Crumley's: 30ms

nickf 2009-08-21 08:34:59

@nickf: **Which** method? There are five in this answer.

T.J. Crowder 2009-08-21 09:33:12

Answer 4

+2 A:

var str = "0000000...0000";
var arr = str.split("");

usage in expressions: arr[i]*1;

EDIT: if arr supposed to be used in integer expressions, then please don't mind the char value of '0'. You just use it as follows: a = a * arr[i] (assuming a has integer value).

Thevs 2009-08-18 20:45:02

Please add comments when downvoting

Thevs 2009-08-18 20:49:37

My downvote sorry. This is terse but not efficient, as you will be creating a string first then performing a string operation, which tend to be slow, and you would still need to then convert the resultant strings to ints, which is also slow.

Triptych 2009-08-18 20:50:43

BTW, the question didn't state by what kind of "zeros" that array must be filled. Regarding performance - I think it should be faster than all previous solutions. Remenber .join("") for string concatenation?

Thevs 2009-08-18 20:55:10

Thevs - you're welcome to profile and prove me wrong. I think it's a stretch to interpret 'zero' as "the string '0'". Nobody else did. Also, just because join is fast for string concatenation does not mean split is the fastest way to create an array.

Triptych 2009-08-18 20:58:58

Ok. Let's count just statements in previous solutions. Every statement or expression (like i-- or other assignment) takes a var from internal cache, calculates an expression assigns it and so on... In `split` case everything works within one function and operates on one variable, Yes, I realize that '0' is not 0, but it's a little overhead to add 0 to match the integer type (if it's _really_ needed).

Thevs 2009-08-18 21:05:34

@Thevs: If we can play around with the concept of "zero", I submit this is the most efficient: ``var a = new Array(len)``. undefined is falsey, and so a bit zero-like. (Whereas "0" is not falsey.) I had the impression the OP really wanted zeroes, though, not zero-like things.

T.J. Crowder 2009-08-18 21:12:36

OK. How about the problem that creating a 10k element array adds 10k to your source file?

Triptych 2009-08-18 21:12:36

I profiled with a string of 10000 zeros, looped 10000 times, at 700 ms. (Not sure though if it's getting optimized away). Initializing an array with 10000 zeroes could only be done 100 times in 900 ms. So if you don't mind stringy zeroes and a big, ugly string in the source, this actually appears quite fast. Again, assuming it's not just optimizing 9999 iterations away or something.

James M. 2009-08-18 21:13:48

I just benchmarked this - it's ~33% slower in a range of crude tests and it has the more serious problem of requiring a literal string of the right length.

annakata 2009-08-18 21:16:38

@James - what exact numeric method did you benchmark? I can't find any circumstance where this is faster (IE or FF)

annakata 2009-08-18 21:19:04

5 + "0" = "50".

Triptych 2009-08-18 21:30:35

Please remove comments when upvoting

mkoryak 2009-08-18 21:37:35

@Triptych: "0" + 5 = "05" === 5. BTW, Any expression with 0, except for division is of no sense.

Thevs 2009-08-18 22:16:53

@annakata, In FF3.5 I was comparing the while loops to splitting a string. I could not find a way to convert the results to Number at better than half the speed of the while loop. But Matthew Crumley's for loop blew them all out of the water (in the micro-benchmark, at least).

James M. 2009-08-18 22:23:34

I was looking for numeric 0 (not the string "0") and for a parametrized length. A solution like string splitting seems more useful if you want to save some code syntax space and have varying data rather than when it's just a constant.

dil 2009-08-18 23:56:20

@dil: What is the practical purpose of having 0 values instead '0' values?

Thevs 2009-08-19 06:21:17

@Thevs: The assumption was that since the zeros will be used for numeric math that it would be more space and time efficient to just initialize them as numbers.

dil 2009-08-19 19:20:25

Can you give an example for using zeros in math? ;)

Thevs 2009-08-19 21:29:56

Sorry, for using pre-assignend zeros.

Thevs 2009-08-19 21:31:36

There are lots of reasons. How about counters that start at zero. Or a partially initialized matrix. Don't get caught up on the zero part of it. A generalized solution that allows arbitrary array length filled with an arbitrary value is more useful than the special case of zeros.

dil 2009-08-21 19:13:36

@dip: It's Ok for all these things. But then you should edit your initial question to comply to all you told here.

Thevs 2009-08-22 08:32:02

@dip: To be more clear: I gave an exact answer to your exact question. And in this exact case my solution is faster.

Thevs 2009-08-22 08:40:13

Answer 5

+2 A:

I knew I had this proto'd somewhere :)

Array.prototype.init = function(x,n)
{
    if(typeof(n)=='undefined') { n = this.length; }
    while (n--) { this[n] = x; }
    return this;
}

var a = (new Array(5)).init(0);

var b = [].init(0,4);

Edit: tests

In response to Joshua and others methods I ran my own benchmarking, and I'm seeing completely different results to those reported.

Here's what I tested:

//my original method
Array.prototype.init = function(x,n)
{
    if(typeof(n)=='undefined') { n = this.length; }
    while (n--) { this[n] = x; }
    return this;
}

//now using push which I had previously thought to be slower than direct assignment
Array.prototype.init2 = function(x,n)
{
    if(typeof(n)=='undefined') { n = this.length; }
    while (n--) { this.push(x); }
    return this;
}

//joshua's method
function newFilledArray(len, val) {
    var a = [];
    while(len--){
     a.push(val);
    }
    return a;
}

//test m1 and m2 with short arrays many times 10K * 10

var a = new Date();
for(var i=0; i<10000; i++)
{
    var t1 = [].init(0,10);
}
var A = new Date();

var b = new Date();
for(var i=0; i<10000; i++)
{
    var t2 = [].init2(0,10);
}
var B = new Date();

//test m1 and m2 with long array created once 100K

var c = new Date();
var t3 = [].init(0,100000);
var C = new Date();

var d = new Date();
var t4 = [].init2(0,100000);
var D = new Date();

//test m3 with short array many times 10K * 10

var e = new Date();
for(var i=0; i<10000; i++)
{
    var t5 = newFilledArray(10,0);
}
var E = new Date();

//test m3 with long array created once 100K

var f = new Date();
var t6 = newFilledArray(100000, 0)
var F = new Date();

Results:

IE7 deltas:
dA=156
dB=359
dC=125
dD=375
dE=468
dF=412

FF3.5 deltas:
dA=6
dB=13
dC=63
dD=8
dE=12
dF=8

So by my reckoning push is indeed slower generally but performs better with longer arrays in FF but worse in IE which just sucks in general (quel surprise).

annakata 2009-08-18 21:05:23

I've just tested this out: the second method (`b = []...`) is 10-15% faster than the first, but it's more than 10 times slower than Joshua's answer.

nickf 2009-08-21 08:27:21

Answer 6

+4 A:

I've tested all combinations of pre-allocating/not pre-allocating, counting up/down, and for/while loops in IE 6/7/8, Firefox 3.5, Chrome, and Opera.

The functions below was consistently the fastest or extremely close in Firefox, Chrome, and IE8, and not much slower than the fastest in Opera and IE 6. It's also the simplest and clearest in my opinion. I've found several browsers where the while loop version is slightly faster, so I'm including it too for reference.

function newFilledArray(length, val) {
    var array = [];
    for (var i = 0; i < length; i++) {
        array[i] = val;
    }
    return array;
}

or

function newFilledArray(length, val) {
    var array = [];
    var i = 0;
    while (i < length) {
        array[i++] = val;
    }
    return array;
}

Matthew Crumley 2009-08-18 21:39:29

This is by far the fastest that I've seen so far.

James M. 2009-08-18 22:24:41

Answer 7

+1 A:

My fastest function would be:

function newFilledArray(len, val) {
    var a = [];
    while(len--){
        a.push(val);
    }
    return a;
}

var st = (new Date()).getTime();
newFilledArray(1000000, 0)
console.log((new Date()).getTime() - st); // returned 63, 65, 62 milliseconds

Using the native push and shift to add items to the array is much faster (about 10 times) than declaring the array scope and referencing each item to set it's value.

fyi: I consistently get faster times with the first loop, which is counting down, when running this in firebug (firefox extension).

var a = [];
var len = 1000000;
var st = (new Date()).getTime();
while(len){
    a.push(0);
    len -= 1;
}
console.log((new Date()).getTime() - st); // returned 863, 894, 875 milliseconds
st = (new Date()).getTime();
len = 1000000;
a = [];
for(var i = 0; i < len; i++){
    a.push(0);
}
console.log((new Date()).getTime() - st); // returned 1155, 1179, 1163 milliseconds

I'm interested to know what T.J. Crowder makes of that ? :-)

Joshua 2009-08-21 08:06:56

top effort!

nickf 2009-08-21 08:22:03

You can make it faster by changing it to `while (len--)`.. took my processing times from about 60ms to about 54ms

nickf 2009-08-21 08:23:34

thanks nickf. I amended "my fastest function". Kudos!

Joshua 2009-08-21 08:31:32

Matthew Crumbly's answer still actually beats this (30ms)!

nickf 2009-08-21 08:31:59

ansaurus

tags:

views:

answers:

Most efficient way to create a zero filled JavaScript array?

related questions