一個數組的高效插入/刪除算法

Question

我訂閱了一個數據饋送，並且使用INSERT/DELETE消息中的索引值創建和維護一個結構。我想問一下組裝的cognoscenti是否知道任何能夠以有效的方式處理零碎更新的算法 - 通常批量更新包含兩到六個這樣的消息。

該陣列的估計大小約爲1000個元素。

批量更新以按索引排序的消息列表到達，該列表規定在給定索引處插入或刪除項目。我希望陣容中的大部分流失比起始時期更接近開始。

在我看來，通過一些基本的處理過程，我可以確定受批次影響的範圍和整體大小 - 增量，因此只需移動一次未受影響的尾部。

同樣，我可以在第一個元素之前和最後一個元素之後保留一定量的可用空間，以儘可能減少複製量。

其他的優化包括：識別更新，如下列：

DELETE 10, INSERT 10 - effectively a replace which requires no copying 
INSERT 10, DELETE 11 - as above 
DELETE 10, DELETE 10, DELETE 10 - bulk deletion can be optimised into one copy operation 
INSERT 11, INSERT 12, INSERT 13 - bulk insertion can be optimised into one copy operation 

等。

但是，我很擔心執行識別步驟的開銷 - 它帶有前瞻性和追溯性，這可能比單純執行復制要花費更多的時間。

考慮到數組的預期大小，樹結構看起來很重：一些基本的性能測試表明，二進制或自平衡樹（在本例中是紅黑樹列表實現）僅在開始顯示性能優勢後纔開始顯示15K - 20K元素：在較小尺寸下，陣列副本顯着更快。我應該補充一點，我在這個實現中使用了Java。

任何提示，提示或建議將受到歡迎。

乾杯

邁克

Answer 1

最簡單的是通過更新，運行和陣列複製到新陣列，同時在應用更新。

1000不是那麼大，可能不值得進一步優化。

爲了讓您的生活更輕鬆更好地使用ArrayList。

Answer 2

除了對單個更新進行排序（如您已經提到過的）以嘗試並鞏固事物，我不知道我會打擾很多。坦率地說，1000個元素在大範圍的事物中沒有任何東西。我有一個擁有25M元素的系統，使用簡單的批量複製，而且（對於我們的目的而言）遠遠超過了足夠快的速度。所以，我不會把「成熟優化」放在帽子上，但是我可能會首先在書架上瞥一眼它。

Answer 3

使用鏈接列表（java.util.LinkedList）可能是需要研究的內容。在特定索引處獲取元素當然很昂貴，但它可能比執行陣列副本更好。

Answer 4

總是衡量代碼清晰度與優化。如果現在沒有性能問題，只要確保代碼清晰即可。如果未來出現性能問題，那麼您就會知道它的確切性質。現在做好準備是猜測中的一項練習。

如果您需要操縱很多，鏈接列表可能值得。

對於簡單清晰的代碼，但是，我會使用Apache的百科全書收集utils的一個原始數組或一個ArrayList否則：

myArray = ArrayUtils.add(myArray, insertionIndex, newItem); 

OR

ArrayList<> mylist = new ArrayList<>(Arrays.asList(myArray)); 
myList.add(insertionIndex, newItem); 

Answer 5

還有就是要實現數據結構非常簡單，名爲「笛卡爾樹」或「Treaps」，它允許在數組上進行O（log N）分割，連接，插入和刪除（還有更多的事情）。

2-3棵樹也非常易於實現（我的實現稍微複雜一點的設施在第一次編譯後只有1個錯誤）並符合您的目的。

Answer 6

如果空間不是一個限制，並且你不會有重複，去設置數據結構，特別是Java的HashSet。這種數據結構的強大之處在於插入和刪除操作在O（1）時間完成，如果性能是'''標準，這將最適合您。另外，除了快速檢索外，每當你談到數組時，你都會遇到許多可能發生的陣列副本的嚴重侷限，這不僅會佔用空間（用於陣列增長），而且效率也會很差每個插入/刪除可能需要O（n）次。

Answer 7

一般來說，如果您按照索引順序列出了所做的更改，則可以構建一個僅複製事件一次的簡單循環。下面是一些僞代碼：

array items; 
array changes; // contains a structure with index, type, an optional data members 
array out; // empty, possibly with ensureCapacity(items.length) 
int c = 0, delta = 0; 
// c is the current change 
//delta tracks how indexing has changed by previous operations 
for (i = 0; i < items.length; i++) { 
    if c < changes.length { 
     curchange = changes[c] 
     if (i + delta) == curchange.index { 
      c++; 
      if (curchange.type == INSERT) { 
       out.add(curchange.data) 
       delta--; 
      } else { 
       delta++; 
       continue; // skip copying i 
      } 
     } 
    } 
    out.add(items[i]) 
} 
for (; c < changes.length; c++) { // handle trailing inserts 
    assert(c.index == out.length && c.type == INSERT) 
    out.add(c.data); 
} 

通過輸入陣列運行一次，並建立與所作的全部修改輸出數組。

請注意，這不處理在同一位置的多個插入。它會使代碼更加精細，但這並不難。

但是，它會一直運行整個陣列，每批一次。一個稍微強硬的變化是暫時保持一定的變化，並用兩個索引變量在原地進行變更;那麼，如果您點擊更改列表的末尾，則可能會提前跳出循環，而不會觸摸列表的其餘部分。

Answer 8

如果這確實是您的數據集的外觀，您可能會考慮使用集合進行重複跟蹤（如HashMap）。該數組將是您的有序列表，每個活動按順序列出，並且您的集合將是該數組的索引。

例如：

 
class EventQueue 
{ 
    Vector eventQueue; 
    HashMap eventMap; 

    public synchronized Event getNextEvent() 
    { 
     Event event = eventQueue.remove(0); 
     eventMap.remove(event.getId()); // this would be 10 from 'INSERT 10' 
             // in the sample from the OP 
    } 

    public synchronized addEvent(Event e) 
    { 
    if(eventMap.containsKey(e.getId()) 
    { 
     // replace events that already exist 
     int idx = eventMap.get(e.getId()); 
     eventQueue.removeElementAt(idx); 
     eventQueue.add(idx, e); 
    } else { 
     // add new events 
     eventQueue.add(e); 
     eventMap.add(e.getId(), eventQueue.size()); // may be off by one... 
    } 
    } 

    public boolean isReady() 
    { 
    return eventQueue.size() > 0; 
    } 
} 

class FeedListener extends Thread { 
EventQueue queue; 
EventFeed feed; 
... 
public void run() 
{ 
    while(running) { 
     sleep(sleepTime); 
     if(feed.isEventReady()) { 
     queue.addEvent(feed.getEvent()); 
     } 
    } 
} 
} 

abstract class EventHandler extends Thread { 
EventQueue queue; 
... 
public void run() 
{ 
    while(running) 
    { 
    sleep(sleepTime); 
    if(queue.isReady()) 
    { 
     Event event = queue.getNextEvent(); 
     handleEvent(event); 
    } 
    } 
} 

public abstract void handleEvent(Event event); 
}