javascript - sort - js array remove




創建零填充JavaScript數組的最有效方法? (20)

在JavaScript中創建任意長度零填充數組的最有效方法是什麼?


ES6 solution:

[...new Array(5)].map(x => 0); // [0, 0, 0, 0, 0]

用預先計算的值填充數組的優雅方式

以下是另一種使用ES6的方法,目前尚未提及任何人:

> Array.from(Array(3), () => 0)
< [0, 0, 0]

它通過傳遞一個map函數作為Array.from的第二個參數。

在上面的例子中,第一個參數分配一個由3個位置組成的數組,其值為undefined ,然後lambda函數將它們中的每一個映射到值0

雖然Array(len).fill(0)更短,但如果你需要通過Array(len).fill(0)一些計算來填充數組,那麼它不起作用(我知道這個問題沒有要求它,但很多人最終在這裡尋找這個)

例如,如果您需要一個包含10個隨機數的數組:

> Array.from(Array(10), () => Math.floor(10 * Math.random()))
< [3, 6, 8, 1, 9, 3, 0, 6, 7, 1]

它比相應的更簡潔(優雅):

const numbers = Array(10);
for (let i = 0; i < numbers.length; i++) {
    numbers[i] = Math.round(10 * Math.random());
}

該方法還可以用於通過利用回調中提供的索引參數來生成數字序列:

> Array.from(Array(10), (d, i) => i)
< [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

獎勵答案:使用String repeat()填充數組

由於這個答案引起了很大的關注,我也想展示這個很酷的技巧。 儘管不如我的主要答案有用,但會引入仍然不是很有名,但非常有用的String repeat()方法。 訣竅是:

> "?".repeat(10).split("").map(() => Math.floor(10 * Math.random()))
< [5, 6, 3, 5, 0, 8, 2, 7, 4, 1]

很酷,嗯? repeat()是一種非常有用的方法來創建一個字符串,該字符串是原始字符串的重複次數。 之後, split()為我們創建一個數組,然後map()將它們轉換為我們想要的值。 分步驟分解:

> "?".repeat(10)
< "??????????"

> "?".repeat(10).split("")
< ["?", "?", "?", "?", "?", "?", "?", "?", "?", "?"]

> "?".repeat(10).split("").map(() => Math.floor(10 * Math.random()))
< [5, 6, 3, 5, 0, 8, 2, 7, 4, 1]

2013年8月更新,2015年2月更新:2009年以下的答案與JavaScript的通用Array類型有關。 它不涉及ES2015中定義的新類型數組[現在可在許多瀏覽器中使用],如Int32Array等。 另請注意,ES2015為Arrays類型數組添加了fill方法,這可能是填充它們的最有效方法。

另外,它可以對您創建陣列的一些實現產生很大的影響。 特別是,Chrome的V8引擎嘗試使用高效的連續內存陣列(如果它認為可行),僅在必要時才轉移到基於對象的陣列。

對於大多數語言,它將被預分配,然後是零填充,如下所示:

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

但是 ,JavaScript數組並不是真正的數組 ,它們就像所有其他JavaScript對像一樣是鍵/值映射,所以不需要“預先分配”(設置長度不會分配多個要填充的時隙),也不需要有什麼理由相信,當實現可以優化他們對按鍵的處理時,倒數到零的好處(這只是為了快速地在循環中進行比較)並沒有通過以相反順序添加按鍵來抵消與理論上的數組相關,您通常會按順序執行它們。

事實上,Matthew Crumley指出Firefox的倒數明顯比倒數慢,我可以肯定的結果是它的數組部分(循環到零仍然比循環到var的限制更快)。 顯然按相反的順序向陣列中添加元素對Firefox來說是一個緩慢的操作。 實際上,JavaScript實現的結果差異很大(這並不令人驚訝)。 這裡是瀏覽器實現的一個快速和骯髒的測試頁面(非常臟,在測試過程中不會產生,所以提供最少的反饋並且會違反腳本時間限制)。 我建議在測試之間刷新; 如果你不這樣做,FF(至少)會在重複測試中變慢。

使用Array#concat的相當複雜的版本比FF上的直接init更快,因為它介於1,000和2,000個元素數組之間。 然而,在Chrome的V8引擎中,每次都會獲得直接啟動

這裡是測試頁面( 實時復制 ):

<!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>

ECMAScript2016 ,大數組就有一個明確的選擇。

由於這個答案仍然顯示在谷歌搜索的頂部附近,這裡是2017年的答案。

這裡有一個目前的jsbench和幾十種流行的方法,其中包括許多到目前為止提出的這個問題。 如果您發現更好的方法,請添加,分叉和分享。

我想說明的是,沒有真正的最有效的方法來創建任意長度的零填充數組。 您可以針對速度進行優化,或者為了清晰度和可維護性進行優化 - 根據項目的需求,可以將其視為更高效的選擇。

在進行速度優化時,您需要:使用文字語法創建數組; 設置長度,初始化迭代變量,並使用while循環遍歷數組。 這是一個例子。

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

另一種可能的實現是:

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

但是我強烈建議不要在實踐中使用第二種植入方式,因為它不太清晰,並且不允許您在數組變量上維護塊範圍。

這些比用for循環填充要快得多,比標準方法快大約90%

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

但這種填充方法仍然是較小陣列的最有效選擇,因為它的清晰度,簡潔性和可維護性。 性能差異可能不會殺了你,除非你製作了大量長度為數千或更多的數組。

其他一些重要注意事項。 大多數風格指南建議您在使用ES6或更高版本時不會在沒有特殊原因的情況下使用var 。 對於不會被重新定義的變量使用const ,並let變量發生變化。 MDNAirbnb的風格指南是了解更多最佳實踐信息的好地方。 這些問題與語法無關,但重要的是,在搜索這些新舊答案時,新接觸JS的人知道這些新標準。


I just use :

var arr = [10];
for (var i=0; i<=arr.length;arr[i] = i, i++);

It might be worth pointing out, that Array.prototype.fill had been added as part of the ECMAScript 6 (Harmony) proposal . I would rather go with the polyfill written below, before considering other options mentioned on the thread.

if (!Array.prototype.fill) {
  Array.prototype.fill = function(value) {

    // Steps 1-2.
    if (this == null) {
      throw new TypeError('this is null or not defined');
    }

    var O = Object(this);

    // Steps 3-5.
    var len = O.length >>> 0;

    // Steps 6-7.
    var start = arguments[1];
    var relativeStart = start >> 0;

    // Step 8.
    var k = relativeStart < 0 ?
      Math.max(len + relativeStart, 0) :
      Math.min(relativeStart, len);

    // Steps 9-10.
    var end = arguments[2];
    var relativeEnd = end === undefined ?
      len : end >> 0;

    // Step 11.
    var final = relativeEnd < 0 ?
      Math.max(len + relativeEnd, 0) :
      Math.min(relativeEnd, len);

    // Step 12.
    while (k < final) {
      O[k] = value;
      k++;
    }

    // Step 13.
    return O;
  };
}

The fastest way to do that is with forEach =)

(we keep backward compatibility for IE < 9)

var fillArray = Array.prototype.forEach
    ? function(arr, n) {
         arr.forEach(function(_, index) { arr[index] = n; });
         return arr;
      }
    : function(arr, n) {
         var len = arr.length;
         arr.length = 0;
         while(len--) arr.push(n);
         return arr;
      };

// test
fillArray([1,2,3], 'X'); // => ['X', 'X', 'X']

There's always the phpjs solution, which you can find here:

http://phpjs.org/functions/array_fill/

I can't speak for the project (creating a library of javascript functions that mirrors the greater functionality of php) as a whole, but the few functions that I've personally pulled from there have worked like a champ.


使用對象符號

var x = [];

零填充? 喜歡...

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

充滿'未定義'...

var x = new Array(7);

帶零點的obj符號

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

作為一個側面說明,如果你修改Array的原型,兩者都可以

var x = new Array();

var y = [];

將有這些原型修改

無論如何,我不會過分關心這個操作的效率和速度,還有很多其他的東西你可能會做,比包含零的任意長度的數組更加浪費和昂貴。


在我的Chrome測試中,此concat版本的速度更快(2013-03-21)。 對於10,000,000個元素,大約200ms,對於直接初始化大約為675。

function filledArray(len, value) {
    if (len <= 0) return [];
    var result = [value];
    while (result.length < len/2) {
        result = result.concat(result);
    }
    return result.concat(result.slice(0, len-result.length));
}

獎勵:如果你想用字符串填充你的數組,這是一個簡潔的方法來做到這一點(儘管不如concat快):

function filledArrayString(len, value) {
    return new Array(len+1).join(value).split('');
}

如果您需要在代碼執行過程中創建多個不同長度的零填充數組,我發現實現此目的的最快方法是使用本主題中提到的方法之一創建一個零數組,你知道它永遠不會被超過,然後根據需要切片該數組。

例如(使用上面選擇的函數初始化數組),創建一個長度為maxLength的零填充數組,作為需要零數組的代碼可見的變量:

var zero = newFilledArray(maxLength, 0);

現在,每當你需要一個長度為零的數組時,切分這個數組requiredLength < maxLength

zero.slice(0, requiredLength);

我在執行代碼的過程中創建了數以千計的零填充數組,這極大地加快了這個過程。


已經提到的ES 6填充方法很好地處理了這一點。 迄今為止,大多數現代桌面瀏覽器已經支持所需的Array原型方法(Chromium,FF,Edge和Safari)[ 1 ]。 您可以查看Array.prototype.fill詳細信息。 一個簡單的用法示例是

a = new Array(10).fill(0);

鑑於目前的瀏覽器支持,你應該謹慎使用這一點,除非你確定你的觀眾使用現代桌面瀏覽器。


我正在測試TJ Crowder的出色答案,並提出了基於concat解決方案的遞歸合併,該解決方案在Chrome中的測試(我沒有測試其他瀏覽器)中勝過任何測試。

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;
},

使用makeRec(29)調用該方法。


我沒有反對:

Array.apply(null, Array(5)).map(Number.prototype.valueOf,0);
new Array(5+1).join('0').split('').map(parseFloat);

由Zertosh建議,但在一個新的ES6數組擴展中允許你使用fill方法進行本地化。 現在IE邊緣,Chrome和FF支持它,但檢查兼容性表

new Array(3).fill(0)會給你[0, 0, 0] 。 您可以使用任何值填充數組,例如new Array(5).fill('abc') (即使是對象和其他數組)。

最重要的是,你可以用fill來修改以前的數組:

arr = [1, 2, 3, 4, 5, 6]
arr.fill(9, 3, 5)  # what to fill, start, end

它給你: [1, 2, 3, 9, 9, 6]


我知道我有這個原型的地方:)

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

編輯:測試

為了回應約書亞和其他人的方法,我運行了自己的基準測試,而且我看到的結果與那些報告完全不同。

以下是我測試的內容:

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

結果:

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


我通常使用Uint8Array (而且速度驚人)。 例如,創建一個1M元素的零填充向量:

  var zeroFilled = [].slice.apply(new Uint8Array(1000000))

我是Linux用戶,並且一直為我工作,但一旦使用Mac的朋友擁有一些非零元素。 我以為他的機器出現故障,但仍然是我們發現修復它的最安全的方式:

  var zeroFilled = [].slice.apply(new Uint8Array(new Array(1000000)) 

編輯

Chrome 25.0.1364.160

  1. 弗雷德里克戈特利布 - 6.43
  2. 薩姆巴納姆 - 4.83
  3. Eli - 3.68
  4. 約書亞2.91
  5. Mathew Crumley - 2.67
  6. bduran - 2.55
  7. 艾倫賴斯 - 2.11
  8. kangax - 0.68
  9. TJ。 Crowder - 0.67
  10. zertosh - 錯誤

Firefox 20.0

  1. 艾倫賴斯 - 1.85
  2. 約書亞 - 1.82
  3. Mathew Crumley - 1.79
  4. bduran - 1.37
  5. 弗雷德里克戈特利布 - 0.67
  6. 薩姆巴納姆 - 0.63
  7. Eli - 0.59
  8. kagax - 0.13
  9. TJ。 Crowder - 0.13
  10. zertosh - 錯誤

缺少最重要的測試(至少對我來說):Node.js之一。 我懷疑它接近Chrome基準。


那麼new Array(51).join('0').split('')


雖然這是一個古老的線索,但我想把2美分添加到它。 不知道這是多麼慢/快,但它是一個快速的班輪。 這是我做的事情:

如果我想預先填寫一個數字:

Array.apply(null, Array(5)).map(Number.prototype.valueOf,0);
// [0, 0, 0, 0, 0]

如果我想預填一個字符串:

Array.apply(null, Array(3)).map(String.prototype.valueOf,"hi")
// ["hi", "hi", "hi"]

其他答案提示:

new Array(5+1).join('0').split('')
// ["0", "0", "0", "0", "0"]

但如果你想要0(數字)而不是“0”(字符串中的零),你可以這樣做:

new Array(5+1).join('0').split('').map(parseFloat)
// [0, 0, 0, 0, 0]

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

請注意, while通常比for-inforEach等效率更高。


function zeroFilledArray(size) {
    return new Array(size + 1).join('0').split('');
}




arrays