合并 2 个排序时间序列算法

本文关键字：时间序列 算法 排序 合并 | 更新日期: 2023-09-27 18:33:07

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

我喜欢设计一种合并算法，它允许我去掉包含相对于其他 BlockingCollection 中相同比较元素的最低值的长成员变量的柱线。

例如，如果 BlockingCollection1 中第一个柱线 (bar1( 中包含的长整型值低于 BlockingCollection2

中第一个柱线 (bar2( 中包含的长整型值，则 Take(( 从 BlockingCollection1 和 Add(( 到 MasterBlockingCollection，实质上最终会得到按每个柱线的长成员变量的值排序的合并的柱线对象流。

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

我

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

多谢

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

合并 2 个排序时间序列算法

这是 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; }
    }
相关文章：