1

Bar オブジェクトを含む 2 つの時系列があり、各 Bar オブジェクトには long 型のメンバー変数が含まれ、各時系列は独自の BlockingCollection に格納されます。時系列は long 値の昇順でソートされます。

私は、他の BlockingCollection の同じ比較要素に対して最も低い値の long メンバー変数を含む Bar を取り除くことができるマージ アルゴリズムを考案したいと考えています。

たとえば、BlockingCollection1 の最初のバー (bar1) に含まれる long 値が、BlockingCollection2 の最初のバー (bar2) に含まれる long 値よりも小さい場合、BlockingCollection1 から Take() を取得し、MasterBlockingCollection に Add() を取得すると、基本的には各 Bar の long メンバー変数の値でソートされた Bar オブジェクトのマージされたストリームを使用します。

後で 2 だけでなく n 個の BlockingCollection に拡張するのが好きです。長い値を保持する配列をいじってマッピングを簡単にしましたが、この特定のターゲット アルゴリズムに関連するポインターを操作する場合は配列の方が便利だと思います。

誰かが私に Linq の実装を指摘して、そのようなアプローチがどれほど計算コストがかかるかについてコメントできるかどうか疑問に思っています。コレクションには何億もの Bar オブジェクトが流れているため、スループットが重要であるため、質問しています。誰かが Linq を使用するよりも賢いアイデアを持っていれば、それは大歓迎です。しばらく前に DrDobbs でアルゴリズムを再マージするアイデアに出くわしましたが、もう記事を見つけることができません。今のところ明らかでない場合に備えて、C# (.Net4.0) をターゲットにしています。

どうもありがとう

編集：マージプロセスは、ブロッキングコレクションに新しいアイテムを追加するワーカー（異なるタスクで実行される）と同時に発生するはずであることを忘れていました

4

1 に答える 1

1

これが Merge の実​​装です。O(cN) 時間で実行する必要があります。ここで、c はコレクションの数です。これはあなたが探しているものですか？

    public static BlockingCollection<Bar> Merge(IEnumerable<BlockingCollection<Bar>> collections)
    {
        BlockingCollection<Bar> masterCollection = new BlockingCollection<Bar>();
        LinkedList<BarWrapper> orderedLows = new LinkedList<BarWrapper>();

        foreach (var c in collections)
            OrderedInsert(new BarWrapper { Value = c.Take(), Source = c }, orderedLows);

        while (orderedLows.Any())
        {
            BarWrapper currentLow = orderedLows.First.Value;
            orderedLows.RemoveFirst();

            BlockingCollection<Bar> collection = currentLow.Source;

            if (collection.Any())
                OrderedInsert(new BarWrapper { Value = collection.Take(), Source = collection }, orderedLows);

            masterCollection.Add(currentLow.Value);
        }
        return masterCollection;
    }

    private static void OrderedInsert(BarWrapper bar, LinkedList<BarWrapper> orderedLows)
    {
        if (!orderedLows.Any())
        {
            orderedLows.AddFirst(bar);
            return;
        }

        var iterator = orderedLows.First;
        while (iterator != null && iterator.Value.Value.LongValue < bar.Value.LongValue)
            iterator = iterator.Next;

        if (iterator == null)
            orderedLows.AddLast(bar);
        else
            orderedLows.AddBefore(iterator, bar);
    }

    class BarWrapper
    {
        public Bar Value { get; set; }
        public BlockingCollection<Bar> Source { get; set; }
    }

    class Bar
    {
        public Bar(long l)
        {
            this.LongValue = l;
        }
        public long LongValue { get; set; }
    }
于 2012-05-03T15:17:44.743 に答える