合併多個事件流

假設我有N數據流事件，我想將它們合併爲一個，使用一些用於排序（例如時間戳）。比方說，EventStream被定義爲：合併多個事件流

class EventStream{ 

    Event peek(); 

    Event next(); 
}

現在我想借ň事件流，將它們包裝在一個流，這將強制排序。但是，我不想簡單地遍歷所有流並將它們添加到priorityQueue中 - 我不希望所有事件都在內存中，因爲我將快速耗盡堆空間。我想要一個動態的方法，其中每個next()後面的組合流會找出下一個事件應該是什麼。我可以每次掃描N流，並找出下一個值是什麼，但有沒有更好的方法？

來源

2012-11-16 Bober02

聽起來就像你想要一個排序的堆而不對其進行排序。 – Shark

您可以避免緩存所有內容，並且只通過在頭上窺視來對流進行太多查找，並且只在需要時才這樣做。我建議你寫一個MergedEventStream類似於此：

public class MergedEventStream implements EventStream { 

    private ArrayList<EventStream> merged = new ArrayList<EventStream>(); 
    private int nextIndex = -1; 

    public MergedEventStream(Collection<EventStream> toMerge) { 
     merged.addAll(toMerge); 
     findNext(); 
    } 

    public Event peek() { 
     if (nextIndex == -1 && findNext() == false) { 
      throw new NoSuchElementException(); 
     } else { 
      Event e = merged.get(nextIndex).peek(); 
      return e; 
     } 
    } 

    public Event peek() { 
     if (nextIndex == -1 && findNext() == false) { 
      throw new NoSuchElementException(); 
     } else { 
      Event e = merged.get(nextIndex).next(); 
      findNext(); 
      return e; 
     } 
    } 

    /** 
    * iterates over merged, and for each stream with an available event, 
    * adds it to a sorted TreeMap<Event, Integer> (sorting by any event field; integer 
    * is stream index in arrayList) 
    * if set is not empty, returns 'true', and sets nextIndex to the stream index 
    * otherwise, returns 'false', and sets nextIndex to -1 
    */ 
    private boolean findNext() { 
     // ... 
    } 
}

您可以通過保持樹形圖作爲一個實例屬性，只刷新那些你從提取物物流提高效率一些。

來源

2012-11-16 11:58:16 tucuxi

你的方法很好。除非N很大，否則應該沒問題。

如果N非常大，則可以將每個流的第一個事件存儲在已排序的集合中，與它來自的流關聯，並且每次從此排序的集合中刪除一個項目時，都會添加下一個從它來自的流。

來源

2012-11-16 11:55:24

＃2與我建議的相同 - 你擊敗了我的拳擊 – tucuxi

使用MinHeap存儲每個事件流中的一個事件。

在next()從堆中彈出頂部事件（具有最早時間的值）。

然後從事件從其中檢索的同一個EventStream中推入一個事件。

所以MinHeap中每個EventStream只會有一個事件。

您將不需要在MinHeap中存儲對EventStream的引用。

這個next()實現將使用O（log n）其中'n'是EventStreams的數量。

注意：預計EventStream已排序事件。 Next（）總是返回最早的事件。

來源

2012-11-16 12:04:10 user1829495

這不正是我在我的答案中建議的嗎？ –

合併多個事件流

回答

相關問題