c# - Merge 2排序时间序列算法

Question

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

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

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

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

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

非常感谢

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

Answer 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; }
    }