1

假设我有N个数据事件流,我想将它们组合成一个,使用一些排序(例如时间戳)。假设EventStream定义为:

class EventStream{

    Event peek();

    Event next();
}

现在我想采用N个事件流,将它们包装在一个流中,这将强制排序。但是,我不想简单地遍历所有流并将它们添加到一个priorityQueue- 我不希望内存中的所有事件,因为我会很快耗尽堆空间。我想要一种动态方法,其中每个之后的组合流next()计算出下一个事件应该是什么。我可以每次扫描N个流并找出下一个值是什么,但是有更好的方法吗?

4

3 回答 3

2

您可以避免缓存所有内容并通过只查看它们的头部来对流进行过多的查找,并且仅在需要时才这样做。我建议你写一个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() {
        // ...
    }
}

您可以通过将 TreeMap 保留为实例属性并仅刷新您从中提取的那些流来提高效率。

于 2012-11-16T11:58:16.187 回答
2

使用 MinHeap 存储每个事件流中的一个事件。

next()堆中弹出顶部事件(最旧时间的值)。

然后从检索事件的同一 EventStream 中推送一个事件。

所以MinHeap中的每个EventStream只会有一个Event。

您需要将 EventStream 的引用与事件一起存储在 MinHeap 中。

next()实现将使用 O(log n),其中“n”是 EventStream 的数量。

注意:预计 EventStream 已经对事件进行了排序。Next() 总是返回最旧的事件。

于 2012-11-16T12:04:10.493 回答
1

你的方法很好。除非 N 很大,否则应该没问题。

如果 N 真的很大,你可以将每个流的第一个事件存储在一个排序集合中,与它来自的流相关联,每次你从这个排序集合中删除一个项目时,你都会从它的流中添加下一个来自。

于 2012-11-16T11:55:24.587 回答