在陣列之間高效地傳輸元素

我有幾個JavaScript數組，每個數組都包含一個指向對象的指針列表。當一個對象滿足某個條件時，它的指針必須從當前包含的數組中移除並放入一個不同的數組中。在陣列之間高效地傳輸元素

我目前的（天真的）解決方案是splice out退出陣列元素和concat將它們加入他們正在進入的數組。這是一個緩慢的方法，似乎隨着時間的推移將內存碎片化。

任何人都可以提供建議（一般或JS特定）在更好的方式來做到這一點？

示範代碼：

// Definitions 
TestObject = function() { 
    this.shouldSwitch = function() { 
     return(Math.random() > 0.9); 
    } 
} 

A = []; 
B = []; 

while(A.length < 500) { 
    A.push(new TestObject()); 
} 

// Transfer loop 
doTransfers = function() { 
    var A_pending = []; 
    var B_pending = []; 
    for(var i = 0; i < A.length; i++) { 
     if(A[i].shouldSwitch()) { 
      B_pending.push(A[i]); 
      A.splice(i,1); 
      i--; 
     } 
    } 
    for(var i = 0; i < B.length; i++) { 
     if(B[i].shouldSwitch()) { 
      A_pending.push(B[i]); 
      B.splice(i,1); 
      i--; 
     } 
    } 

    A = A.concat(A_pending); 
    B = B.concat(B_pending); 
} 

setInterval(doTransfers,10);

謝謝！

來源

2015-05-27 Mollusq

是的，你絕對不應該在循環中使用'splice'。但是，既然你正在創建新的數組，你可以簡單地不刪除它，而是馬上推到新的'* _pending'。 – Bergi

splice對循環中的性能是非常有害的。但是你似乎無論如何都不需要輸入數組上的突變 - 你正在創建新的並覆蓋以前的值。

只是做

function doTransfers() { 
    var A_pending = []; 
    var B2_pending = []; 
    for (var i = 0; i < A.length; i++) { 
     if (A[i].shouldSwitch()) 
      B_pending.push(A[i]); 
     else 
      A_pending.push(A[i]); 
    } 
    var B1_pending = []; 
    for (var i = 0; i < B.length; i++) { 
     if (B[i].shouldSwitch()) 
      A_pending.push(B[i]); 
     else 
      B1_pending.push(B[i]); 
    } 

    A = A_pending; 
    B = B1_pending.concat(B2_pending); 
}

來源

2015-05-27 21:59:13 Bergi

我明白了！應該已經意識到我已經在'concat'步驟重新編寫了'A'和'B'。重複使用'push'還是基於傳入條目的計數預先分配'A_pending'和'B * _pending'通常會更好？ – Mollusq

你可以嘗試，儘管不是所有的JS引擎都會在設置'.length'屬性時進行預分配。陣列的增長速度相當快。 – Bergi

對於一個獨立於語言的一種解決這個問題，當你把從一個連續的序列（陣列）單元到另一個，它不是附加元素的背後新的陣列將會變得瓶頸（時間複雜度恆定），這將是從現有容器中移除元素（線性時間複雜度）。

這樣你就可以得到最大的好處是，可以替代陣列的中部，仍然使用了緩存友好的，連續的數組表示一個固定時間操作刪除的是線性時間的操作。

要做到這一點最簡單的方法之一是簡單地創建兩個新的數組而不是一個：一個新的數組追加你想要保留的元素和一個新的數組來追加你想傳輸的元素。當你完成後，你可以用舊數組替換你想要保留（不傳送）的新數組元素。

在這種情況下，我們從與分期常量時間插入到一個新的回容器的中間交換線性時間的清除。而插入到容器的端部仍具有O（N），用於重新分配的最壞情況下的複雜性，它發生不頻繁足夠並且仍然一般比用於具有的O（N）的平均複雜度，每次操作支付好得多你通過不斷地從中間移除單個元素。

另一種方式來解決這個問題，可以更有效，特別是對某些情況下，像真正的小數組，因爲它僅創建1個新陣，是這樣的：

...當你把一個元素，第一附加的副本（可能只是一個淺複製）到新的容器。然後，在與從舊容器的背面的元件舊的容器該索引處覆蓋元件。現在簡單地彈出舊容器後面的元素。所以我們有一個推動，一個任務和一個流行。

在這種情況下，我們正在通過一個賦值（存儲/移動指令）和容器後部的常量時間彈出（通常是基本算術）從容器的中間線性時間移除，。如果舊數組中的元素的順序可能會稍微混亂一些，這可以非常好地工作，並且通常是一種被忽視的解決方案，用於將線性時間從數組中間移除爲一個具有恆定時間複雜度的解決方案數組的後面。

來源

2015-05-27 23:29:50

我會給這兩個嘗試。感謝徹底的迴應！ – Mollusq

在陣列之間高效地傳輸元素

回答

相關問題