JavaScript的鏈表曹景偉垃圾收集

Question

我實現以下鏈接列表數據結構在JavaScript：

class Node { 
    constructor(data, list) { 
    this.data = data; 
    this.list = list; 
    this.prev = null; 
    this.next = null; 
    } 

    remove() { 
    if (this.prev) { 
     this.prev.next = this.next; 
    } else { 
     this.list.start = this.next; 
    } 

    if (this.next) { 
     this.next.prev = this.prev; 
    } else { 
     this.list.end = this.prev; 
    } 

    this.next = null; 
    this.prev = null; 
    this.list.length -= 1; 
    } 
} 

class LinkedList { 
    constructor() { 
    this.end = null; 
    this.start = null; 
    this.length = 0; 
    } 

    append(data) { 
    const node = new Node(data, this); 

    if (!this.start) { 
     this.start = node; 
    } 

    if (this.end) { 
     node.prev = this.end; 
     this.end.next = node; 
    } 

    this.end = node; 
    this.length += 1; 

    return data; 
    } 

    remove() { 
    if (this.end) { 
     return this.end.remove(); 
    } 
    } 

    *[Symbol.iterator]() { 
    let current = this.start; 
    while (current) { 
     yield current; 
     current = current.next; 
    } 
    } 
} 

module.exports = LinkedList; 

我用它像這樣更新的動畫列表：

static update(timeDelta) { 
    for (let node of this.animations) { 
    const animation = node.data; 

    if (animation.animating) { 
     animation.update(timeDelta); 
    } else { 
     node.remove(); 
    } 
    } 
} 

的node.remove()線在我的比賽中造成非常明顯的滯後。我懷疑這是觸發垃圾收集。相反，如果我註釋掉node.remove()這一行並允許鏈表永久增長，那麼遊戲運行平穩。

不斷添加和刪除動畫。我加了一些記錄在動畫update功能：

start iterating linked list 
removing 
ms elapsed: 0.45499999999992724 
end iterating 
start iterating linked list 
removing 
ms elapsed: 0.455000000000382 
end iterating 
start iterating linked list 
removing 
ms elapsed: 0.13000000000010914 
end iterating 
start iterating linked list 
(13) updating 
ms elapsed: 2.200000000000273 
end iterating 

你可以看到鏈表是每秒迭代多次與被刪除偶爾節點。

如何在不引起性能下降的情況下從我的列表中實現O（1）刪除？

Answer 1

node.remove()線會在我的遊戲中引起非常明顯的延遲。我懷疑這是觸發垃圾收集。

沒有。滯後來自事實，即每個update調用只更新很少的動畫。

你的問題是舊的和着名的「迭代過程中刪除」問題。在你的情況下，它不會觸發罕見的邊緣錯誤，它只是停止迭代：

while (current) { 
    yield current; 
    // after yielding, in the `update` function, we have 
    // node = current 
    // and most importantly 
    // node.remove() 
    // which assigns (with `this` being `node`) 
    // this.next = null; 
    // then the iteration is resumed 
    current = current.next; 
} 

糟糕。簡單的解決辦法就是緩存屈服前的下一個節點進行迭代：

let next = this.start; 
while (next) { 
    const current = next; 
    next = current.next; 
    yield current; 
} 

（或類似的東西），但當然還是下一個節點被刪除失敗。一個更好的辦法可能是從節點的remove方法省略線

this.next = null; 
this.prev = null; 

，使引用刪除期間保持不變。這不會影響GC。

---

另一種解決方案是完全放棄鏈表 - 這是過度設計的，除非你經常添加/列表中間除去外面的迭代節點。迭代過程中過濾掉老動畫是簡單，它是可以做到一個很好的舊（內存效率？）Array，甚至就地：

function filter(array, callback) { 
    var i=0, j=0; 
    while (j < array.length) { 
     if (callback(array[j])) 
      array[i++] = array[j++]; 
     else 
      array[i] = array[j++]; 
    } 
    array.length = i; 
} 
function update(timeDelta) { 
    filter(animations, animation => { 
     var keep = animation.animating; 
     if (keep) animation.update(timeDelta); 
     return keep; 
    }); 
} 

（你也許可以通過不重新分配時，以優化filteri===j）