1

データイベントのストリームがN個あり、それらを1つに結合して、いくつかの順序付け（たとえば、タイムスタンプ）を使用するとします。EventStream次のように定義されているとしましょう：

class EventStream{

    Event peek();

    Event next();
}

ここで、 N個のイベントストリームを取得し、それらを1つのストリームにラップして、順序付けを強制します。ただし、単純にすべてのストリームを反復処理してそれらを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を使用して、各イベントストリームから1つのイベントを保存します。

一番上next()のイベントをヒープからポップアウトします（最も古い時間の値）。

次に、イベントが取得されたのと同じEventStreamから1つのイベントをプッシュします。

したがって、MinHeapの各EventStreamには1つのイベントしかありません。

MinHeapのイベントとともにEventStreamへの参照を保存する必要があります。

このnext()実装では、O（log n）を使用します。ここで、「n」はEventStreamの数です。

注：EventStreamがイベントをソートしていることが期待されます。Next（）は、常に最も古いイベントを返します。

于 2012-11-16T12:04:10.493 に答える
1

あなたのアプローチは大丈夫です。Nが大きくない限り、問題ありません。

Nが非常に大きい場合は、各ストリームの最初のイベントを、その元のストリームに関連付けられた並べ替えられたコレクションに格納できます。この並べ替えられたコレクションからアイテムを削除するたびに、ストリームから次のイベントを追加します。から来た。

于 2012-11-16T11:55:24.587 に答える