Most efficient way to create a zero filled JavaScr

2018-12-31 12:45发布

What is the most efficient way to create an arbitrary length zero filled array in JavaScript?

30条回答
深知你不懂我心
2楼-- · 2018-12-31 13:11

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;
}
查看更多
君临天下
3楼-- · 2018-12-31 13:12

If you use ES6, you can use Array.from() like this:

Array.from({ length: 3 }, () => 0);
//[0, 0, 0]

Has the same result as

Array.from({ length: 3 }).map(() => 0)
//[0, 0, 0]

Because

Array.from({ length: 3 })
//[undefined, undefined, undefined]
查看更多
十年一品温如言
4楼-- · 2018-12-31 13:13

I was testing out the great answer by T.J. Crowder, and came up with a recursive merge based on the concat solution that outperforms any in his tests in Chrome (i didn't test other browsers).

function makeRec(len, acc) {
    if (acc == null) acc = [];
    if (len <= 1) return acc;
    var b = makeRec(len >> 1, [0]);
    b = b.concat(b);
    if (len & 1) b = b.concat([0]);
    return b;
},

call the method with makeRec(29).

查看更多
与风俱净
5楼-- · 2018-12-31 13:14

Note added August 2013, updated February 2015: The answer below from 2009 relates to JavaScript's generic Array type. It doesn't relate to the newer typed arrays defined in ES2015 [and available now in many browsers], like Int32Array and such. Also note that ES2015 adds a fill method to both Arrays and typed arrays, which is likely to be the most efficient way to fill them...

Also, it can make a big difference to some implementations how you create the array. Chrome's V8 engine, in particular, tries to use a highly-efficient, contiguous-memory array if it thinks it can, shifting to the object-based array only when necessary.


With most languages, it would be pre-allocate, then zero-fill, like this:

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

But, JavaScript arrays aren't really arrays, they're key/value maps just like all other JavaScript objects, so there's no "pre-allocate" to do (setting the length doesn't allocate that many slots to fill), nor is there any reason to believe that the benefit of counting down to zero (which is just to make the comparison in the loop fast) isn't outweighed by adding the keys in reverse order when the implementation may well have optimized their handling of the keys related to arrays on the theory you'll generally do them in order.

In fact, Matthew Crumley pointed 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 (which isn't all that surprising). 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 (live copy):

<!DOCTYPE html>
<html>
<head>
<meta 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>
查看更多
ら面具成の殇う
6楼-- · 2018-12-31 13:14

As of ECMAScript2016, there is one clear choice for large arrays.

Since this answer still shows up near the top on google searches, here's an answer for 2017.

Here's a current jsbench with a few dozen popular methods, including many proposed up to now on this question. If you find a better method please add, fork and share.

I want to note that there is no true most efficient way to create an arbitrary length zero filled array. You can optimize for speed, or for clarity and maintainability - either can be considered the more efficient choice depending on the needs of the project.

When optimizing for speed, you want to: create the array using literal syntax; set the length, initialize iterating variable, and iterate through the array using a while loop. Here's an example.

const arr = [];
arr.length = 120000;
let i = 0;
while (i < 120000) {
  arr[i] = 0;
  i++;
}

Another possible implementation would be:

(arr = []).length = n;
let i = 0;
while (i < n) {
    arr[i] = 0;
    i++;
}

But I strongly discourage using this second implantation in practice as it's less clear and doesn't allow you to maintain block scoping on your array variable.

These are significantly faster than filling with a for loop, and about 90% faster than the standard method of

const arr = Array(n).fill(0);

But this fill method is still the most efficient choice for smaller arrays due to it's clarity, conciseness and maintainability. The performance difference likely won't kill you unless you're making a lot of arrays with lengths on the order of thousands or more.

A few other important notes. Most style guides recommend you no longer use varwithout a very special reason when using ES6 or later. Use const for variables that won't be redefined and let for variables that will. The MDN and Airbnb's Style Guide are great places to go for more information on best practices. The questions wasn't about syntax, but it's important that people new to JS know about these new standards when searching through these reams of old and new answers.

查看更多
查无此人
7楼-- · 2018-12-31 13:17

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

查看更多
登录 后发表回答