合并多个事件流

假设我有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

这不正是我在我的答案中建议的吗？ –

合并多个事件流

回答

相关问题