通過ID快速查找索引

我有數百萬個對象，每個對象都有一個唯一的ID號。使每個對象簡單化包含名稱通過ID快速查找索引

它們的對象被添加到數組中。

進入這個數組我添加和刪除對象。

爲了刪除對象我有id，然後需要在數組中找到索引並將其拼接出來。

在我的情況下，我有分配的對象，可以有刪除操作的分配。所以萬一我有1000刪除。並且所有這些對象id都存儲在數組的末尾，比我將遍歷所有100萬個對象直到找到它們。

添加後在對象中存儲索引是不好的，因爲每一個刪除我需要更新刪除之後存儲的所有對象的索引。例如，移除第一個1000會導致更新其餘的1M-1000項目索引。

我的問題是，什麼是我的問題的最佳解決方案？

- UPDATE -

例如：我的扁平陣列看起來像這樣添加1M對象

後[OBJ1，OBJ2，OBJ3，.... obj1000000]

我想要現在刪除對象obj1000000。爲了找到這個對象插入到我需要運行所有數組（或直到我找到該項目）並比較當前項目ID與我的obj1000000 ID，並找到時從循環中分離出來。然後通過索引刪除項目。

如果我將每個對象的索引存儲在對象本身中，然後將其添加到數組中，我將不得不在刪除對象索引後更新剩餘的對象索引。

例如：obj1將包含屬性index=0,obj2將會有index=1等等。要刪除obj5我只是得到它的屬性index這是4並將其刪除。但現在obj6其中有index=5是不正確的。應該是4。而obj7應該是5等等。所以更新必須完成。

我的SmartArray包含一個以某種大小創建的TypedArray。如果需要，我會花費它。當推送被調用時。我只是設置的值中的最後一項this._array[this.length++] = value;（檢查過程中，如果展開數組）

SmartArray.prototype.getArray = function() { 
    return this._array.subarray(0, this.length); 
} 

SmartArray.prototype.splice = function (index, removeCount) { 

    if (index + removeCount < this.length) { 
     var sub = this._array.subarray(index + removeCount, this.length); 
     this._array.set(sub, index); 
    } else { 
     removeCount = this.length - index; 
    } 

    this.length -= removeCount; 
}

這是工作非常快，subarray不創建一個新的陣列。 set工作速度也很快。

來源

2015-11-08 Raziza O

你爲什麼要使用數組？拼接數組與線性搜索數組一樣昂貴。 – Bergi

我正在使用web gl進行繪圖，而這需要平面陣列。我開發了一個智能類型的數組，實際上並不是每次拼接創建新的數組......並且工作正常。瓶頸是搜索要刪除的索引 –

'splice'確實不會創建新的數組，但它確實需要在刪除的項目之後重新排列所有索引...或者您是否使用稀疏數組？請向我們展示您的智能類型數組實現。 – Bergi

此問題的標準解決方案是

平衡（二進制）樹，
哈希表。

它們平均每個搜索/插入/刪除分別執行O（Log（N））和O（1）操作。

兩者都可以在數組中實現。你會通過網絡搜索找到它們的許多版本。

來源

2015-11-08 16:31:12

你的意思是說，每一個刪除我會索引所有的樹再次？因爲當刪除正在完成時，我需要更新樹的值更改樹 –

沒有理由不使用JavaScript中提供的內置數據結構。 – Pointy

@RazizaO：你應該閱讀二叉樹和散列表，看看它們是如何工作的。 –

通過ID快速查找索引

回答

相關問題