1

我有 2 个包含 Bar 对象的时间序列，每个 Bar 对象都包含一个 long 类型的成员变量，每个时间序列都存储在它自己的 BlockingCollection 中。时间序列按 long 值的升序排序。

我喜欢设计一种合并算法，它允许我删除包含相对于另一个 BlockingCollection 中相同比较元素的最低值的 long 成员变量的 Bar。

例如，如果 BlockingCollection1 中第一个 Bar (bar1) 中包含的 long 值低于 BlockingCollection2 中第一个 Bar (bar2) 中包含的 long 值，则从 BlockingCollection1 和 Add() 中的 Take() 到 MasterBlockingCollection，基本上结束使用按每个 Bar 的 long 成员变量的值排序的 Bar 对象的合并流。

我想稍后扩展到 n BlockingCollections，而不仅仅是 2。我使用了保存长值的数组以使映射更容易，但我认为在使用与此特定目标算法有关的指针时数组更方便。

我想知道是否有人可以向我指出 Linq 实现并评论这种方法的计算成本有多大。我问是因为吞吐量很重要，因为有数亿个 Bar 对象流过集合。如果有人有比使用 Linq 更聪明的想法，那将非常受欢迎。前段时间我在 DrDobbs 遇到了一些重新合并算法的想法，但再也找不到这篇文章了。如果现在还不明显，我以 C# (.Net4.0) 为目标

非常感谢

编辑：我忘了提到合并过程应该与将新项目添加到阻塞集合中的工作人员同时发生（在不同的任务上运行）

4

1 回答 1

1

这是合并的一个实现。它应该在 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 回答