Самый эффективный алгоритм объединения отсортированных IEnumerable <T>

Question

У меня есть несколько огромных отсортированных перечислимых последовательностей, которые я хочу объединить . Списки тезисов обрабатываются как IEnumerable, но уже отсортированы . Поскольку входные списки отсортированы, должна быть возможность объединить их за одну поездку, ничего не сортируя заново.

Я бы хотел сохранить поведение отложенного выполнения.

Я пытался написать наивный алгоритм, который делает это (см. Ниже). Тем не менее, это выглядит довольно некрасиво, и я уверен, что это можно оптимизировать. Может существовать более академичный алгоритм ...

IEnumerable<T> MergeOrderedLists<T, TOrder>(IEnumerable<IEnumerable<T>> orderedlists, 
                                            Func<T, TOrder> orderBy)
{
    var enumerators = orderedlists.ToDictionary(l => l.GetEnumerator(), l => default(T));
    IEnumerator<T> tag = null;

    var firstRun = true;
    while (true)
    {
        var toRemove = new List<IEnumerator<T>>();
        var toAdd = new List<KeyValuePair<IEnumerator<T>, T>>();
        foreach (var pair in enumerators.Where(pair => firstRun || tag == pair.Key))
        {
            if (pair.Key.MoveNext())
                toAdd.Add(pair);
            else
                toRemove.Add(pair.Key);
        }

        foreach (var enumerator in toRemove)
            enumerators.Remove(enumerator);

        foreach (var pair in toAdd)
            enumerators[pair.Key] = pair.Key.Current;

        if (enumerators.Count == 0)
            yield break;

        var min = enumerators.OrderBy(t => orderBy(t.Value)).FirstOrDefault();
        tag = min.Key;
        yield return min.Value;

        firstRun = false;
    }
}

Метод можно использовать так:

// Person lists are already sorted by age
MergeOrderedLists(orderedList, p => p.Age);

при условии, что где-то существует следующий класс Person:

    public class Person
    {
        public int Age { get; set; }
    }

Дубликаты должны быть сохранены, нас не волнует их порядок в новой последовательности. Вы видите какую-то очевидную оптимизацию, которую я мог бы использовать?

Answer 1

Каждый объединяемый список должен быть уже отсортирован. Этот метод найдет равные элементы в порядке их списков. Например, если элементы Ti == Tj, и они соответственно из списка i и списка j (i

public static IEnumerable<T> Merge<T, TOrder>(this IEnumerable<IEnumerable<T>> TEnumerable_2, Func<T, TOrder> orderFunc, IComparer<TOrder> cmp=null)
{
    if (cmp == null)
    {
        cmp = Comparer<TOrder>.Default;
    }

    List<IEnumerator<T>> TEnumeratorLt = TEnumerable_2
       .Select(l => l.GetEnumerator())
       .Where(e => e.MoveNext())
       .ToList();

    while (TEnumeratorLt.Count > 0)
    {
        int intMinIndex;
        IEnumerator<T> TSmallest = TEnumeratorLt.GetMin(TElement => orderFunc(TElement.Current), out intMinIndex, cmp);
        yield return TSmallest.Current;

        if (TSmallest.MoveNext() == false)
        {
            TEnumeratorLt.RemoveAt(intMinIndex);
        }
    }
}

/// <summary>
/// Get the first min item in an IEnumerable, and return the index of it by minIndex
/// </summary>
public static T GetMin<T, TOrder>(this IEnumerable<T> self, Func<T, TOrder> orderFunc, out int minIndex, IComparer<TOrder> cmp = null)
{
    if (self == null) throw new ArgumentNullException("self");            

    IEnumerator<T> selfEnumerator = self.GetEnumerator();
    if (!selfEnumerator.MoveNext()) throw new ArgumentException("List is empty.", "self");

    if (cmp == null) cmp = Comparer<TOrder>.Default;

    T min = selfEnumerator.Current;
    minIndex = 0;
    int intCount = 1;
    while (selfEnumerator.MoveNext ())
    {
        if (cmp.Compare(orderFunc(selfEnumerator.Current), orderFunc(min)) < 0)
        {
            min = selfEnumerator.Current;
            minIndex = intCount;
        }
        intCount++;
    }

    return min;
}

Answer 2

Попытка улучшить ответ @ 100d * @ cdiggins . Эта реализация работает правильно, если два элемента, которые сравниваются как равные, содержатся в двух разных последовательностях (т.е. не имеют недостатка, упомянутого @ChadHenderson).

Алгоритм описан в Википедии , сложность O ( m log n ), где n - число списки объединяются, а m - сумма длин списков.

OrderedBag<T> из Wintellect.PowerCollections используется вместо очереди приоритетов на основе кучи, но это не меняет сложности.

public static IEnumerable<T> Merge<T>(
   IEnumerable<IEnumerable<T>> listOfLists,
   Func<T, T, int> comparison = null)
{
   IComparer<T> cmp = comparison != null
      ? Comparer<T>.Create(new Comparison<T>(comparison))
      : Comparer<T>.Default;
   List<IEnumerator<T>> es = listOfLists
      .Select(l => l.GetEnumerator())
      .Where(e => e.MoveNext())
      .ToList();
   var bag = new OrderedBag<IEnumerator<T>>(
      (e1, e2) => cmp.Compare(e1.Current, e2.Current));
   es.ForEach(e => bag.Add(e));
   while (bag.Count > 0)
   {
      IEnumerator<T> e = bag.RemoveFirst();
      yield return e.Current;
      if (e.MoveNext())
      {
         bag.Add(e);
      }
   }
}

Answer 3

Этим вечером мне задали этот вопрос как вопрос для собеседования, и за 20 минут или около того мне не дали хорошего ответа. Поэтому я заставил себя написать алгоритм без каких-либо поисков. Ограничением было то, что входные данные были уже отсортированы. Вот мой код:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Merger
{
  class Program
  {
    static void Main(string[] args)
    {
      int[] a = { 1, 3, 6, 102, 105, 230 };
      int[] b = { 101, 103, 112, 155, 231 };

      var mm = new MergeMania();

      foreach(var val in mm.Merge<int>(a, b))
      {
        Console.WriteLine(val);
      }
      Console.ReadLine();
    }
  }

  public class MergeMania
  {
    public IEnumerable<T> Merge<T>(params IEnumerable<T>[] sortedSources) 
      where T : IComparable
    {
      if (sortedSources == null || sortedSources.Length == 0) 
        throw new ArgumentNullException("sortedSources");

      //1. fetch enumerators for each sourc
      var enums = (from n in sortedSources 
             select n.GetEnumerator()).ToArray();

      //2. fetch enumerators that have at least one value
      var enumsWithValues = (from n in enums 
                   where n.MoveNext() 
                   select n).ToArray();
      if (enumsWithValues.Length == 0) yield break; //nothing to iterate over

      //3. sort by current value in List<IEnumerator<T>>
      var enumsByCurrent = (from n in enumsWithValues 
                  orderby n.Current 
                  select n).ToList();
      //4. loop through
      while (true)
      {
        //yield up the lowest value
        yield return enumsByCurrent[0].Current;

        //move the pointer on the enumerator with that lowest value
        if (!enumsByCurrent[0].MoveNext())
        {
          //remove the first item in the list
          enumsByCurrent.RemoveAt(0);

          //check for empty
          if (enumsByCurrent.Count == 0) break; //we're done
        }
        enumsByCurrent = enumsByCurrent.OrderBy(x => x.Current).ToList();
      }
    }
  }
}

Надеюсь, это поможет.

Answer 4

Это похоже на ужасно полезную функцию, поэтому я решил попробовать ее. Мой подход очень похож на heightechrider в том, что он разбивает проблему на объединение двух отсортированных IEnumerables в один, затем выбирает один и объединяет его со следующим в списке. Скорее всего, есть какая-то оптимизация, которую вы можете выполнить, но она работает с моим простым тестовым примером:

      public static IEnumerable<T> mergeSortedEnumerables<T>(
            this IEnumerable<IEnumerable<T>> listOfLists, 
            Func<T, T, Boolean> func)
      {
            IEnumerable<T> l1 = new List<T>{};
            foreach (var l in listOfLists)
            {
                 l1 = l1.mergeTwoSorted(l, func);
            }

            foreach (var t in l1)
            {
                 yield return t;
            }
      }

      public static IEnumerable<T> mergeTwoSorted<T>(
            this IEnumerable<T> l1, 
            IEnumerable<T> l2, 
            Func<T, T, Boolean> func)
      {
            using (var enumerator1 = l1.GetEnumerator())
            using (var enumerator2 = l2.GetEnumerator())
            {
                 bool enum1 = enumerator1.MoveNext();
                 bool enum2 = enumerator2.MoveNext();
                 while (enum1 || enum2)
                 {
                      T t1 = enumerator1.Current;
                      T t2 = enumerator2.Current;

                      //if they are both false
                      if (!enum1 && !enum2)
                      {
                            break;
                      }
                      //if enum1 is false
                      else if (!enum1)
                      {
                            enum2 = enumerator2.MoveNext();
                            yield return t2;

                      }
                      //if enum2 is false
                      else if (!enum2)
                      {
                            enum1 = enumerator1.MoveNext();
                            yield return t1;

                      }
                      //they are both true
                      else
                      {
                            //if func returns true then t1 < t2
                            if (func(t1, t2))
                            {
                                 enum1 = enumerator1.MoveNext();
                                 yield return t1;

                            }
                            else
                            {
                                 enum2 = enumerator2.MoveNext();
                                 yield return t2;

                            }
                      }
                 }
            }
      }

Затем, чтобы проверить это:

                List<int> ws = new List<int>() { 1, 8, 9, 16, 17, 21 };
                List<int> xs = new List<int>() { 2, 7, 10, 15, 18 };
                List<int> ys = new List<int>() { 3, 6, 11, 14 };
                List<int> zs = new List<int>() { 4, 5, 12, 13, 19, 20 };
                List<IEnumerable<int>> lss = new List<IEnumerable<int>> { ws, xs, ys, zs };

                foreach (var v in lss.mergeSortedEnumerables(compareInts))
                {
                     Console.WriteLine(v);
                }

Answer 5

Я подозреваю, что LINQ достаточно умен, чтобы воспользоваться преимуществами предыдущего существующего порядка сортировки:

IEnumerable<string> BiggerSortedList =  BigListOne.Union(BigListTwo).OrderBy(s => s);