Слияние 2 алгоритм отсортированных временных рядов

Question

У меня есть 2 временных ряда, содержащих объекты Bar, каждый объект Bar содержит переменную-член типа long и каждый временной ряд хранится в пределах своего собственного BlockingCollection. Временной ряд сортируется в порядке возрастания длинных значений.

Мне нравится разрабатывать алгоритм слияния, который позволяет мне отбирать панель, содержащую длинную переменную-член наименьшего значения относительно того же элемента сравнения в другом BlockingCollection.

Пример, если длинное значение, содержащееся в первом столбце (bar1) в BlockingCollection1, меньше, чем длинное значение, содержащееся в первой строке (bar2) в BlockingCollection2, затем Take() из BlockingCollection1 и Add() в MasterBlockingCollection , по сути, заканчивается объединенным потоком объектов Bar, отсортированным по значению переменной длинной переменной каждого бара.

Мне нравится позже расширять до n BlockingCollections, а не только 2. Я играл с массивами, которые содержат длинные значения, чтобы упростить отображение, но я думаю, что массивы более удобны при работе с указателями, относящимися к этому конкретному целевому алгоритму.

Интересно, может ли кто-нибудь указать мне на реализацию Linq и прокомментировать, насколько это дорого стоит такой подход. Я спрашиваю, потому что пропускная способность имеет важное значение, поскольку в коллекции собраны сотни миллионов объектов Bar. Если у кого-то есть более умная идея, чем использование Linq, это будет очень приветствоваться. Некоторое время назад я наткнулся на некоторые алгоритмы слияния идей в DrDobbs, но больше не могу найти статью. В случае, если это не очевидно теперь, таргетировать C# (.Net4.0)

Большое спасибо

Edit: Я забыл упомянуть о том, что процесс объединения должен произойти в то же время, чем рабочих, добавьте новые элементы в blockingcollections (работает на разных задачах)

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