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

Я бы предположил, что это может улучшить ясность и производительность:

• Создайте приоритетную очередь по парам T , IEnumerable , упорядоченных в соответствии с вашим сравнением функция на T
• Для каждого объединяемого IEnumerable добавьте элемент в приоритетную очередь, аннотированный ссылкой на IEnumerable , откуда он был создан
• Пока приоритетная очередь не пуста
  • Извлечь минимальный элемент из приоритетной очереди
  • Переместить IEnumerable в его аннотацию, чтобы следующий элемент
  • Если MoveNext () вернул истину, добавьте следующий элемент в приоритетную очередь, аннотированный ссылкой на IEnumerable , который вы только что продвинули
  • Если MoveNext () вернул false, ничего не добавляйте в очередь приоритетов
  • Получите исключенный из очереди элемент

Похоже, это очень полезная функция, поэтому я решил попробовать ее. Мой подход очень похож на hightechrider в том, что он разбивает проблему на объединение двух отсортированных 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);
                }

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

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

Моя версия ответа sixlettervariables. Я уменьшил количество вызовов orderFunc (каждый элемент проходит через orderFunc только один раз), и в случае равенства сортировка пропускается. Это оптимизировано для небольшого числа источников, большего числа элементов в каждом источнике и, возможно, дорогого orderFunc.

public static IEnumerable<T> MergePreserveOrder<T, TOrder>(
  this IEnumerable<IEnumerable<T>> sources, 
  Func<T, TOrder> orderFunc)  
  where TOrder : IComparable<TOrder> 
{
  Dictionary<TOrder, List<IEnumerable<T>>> keyedSources =
    sources.Select(source => source.GetEnumerator())
      .Where(e => e.MoveNext())
      .GroupBy(e => orderFunc(e.Current))
      .ToDictionary(g => g.Key, g => g.ToList()); 

  while (keyedSources.Any())
  {
     //this is the expensive line
    KeyValuePair<TOrder, List<IEnumerable<T>>> firstPair = keyedSources
      .OrderBy(kvp => kvp.Key).First();

    keyedSources.Remove(firstPair.Key);
    foreach(IEnumerable<T> e in firstPair.Value)
    {
      yield return e.Current;
      if (e.MoveNext())
      {
        TOrder newKey = orderFunc(e.Current);
        if (!keyedSources.ContainsKey(newKey))
        {
          keyedSources[newKey] = new List<IEnumerable<T>>() {e};
        }
        else
        {
          keyedSources[newKey].Add(e);
        }
      }
    }
  }
}

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

Вот решение без СОРТИРОВКИ ... только минимум количество сравнений. (Я опустил фактическую передачу функции порядка для простоты). Обновлено для построения сбалансированного дерева: -

    /// <summary>
    /// Merge a pair of ordered lists
    /// </summary>
    public static IEnumerable<T> Merge<T>(IEnumerable<T> aList, IEnumerable<T> bList)
        where T:IComparable<T>
    {
        var a = aList.GetEnumerator();
        bool aOK = a.MoveNext();

        foreach (var b in bList)
        {
            while (aOK && a.Current.CompareTo(b) <= 0) {yield return a.Current; aOK = a.MoveNext();}
            yield return b;
        }
        // And anything left in a
        while (aOK) { yield return a.Current; aOK = a.MoveNext(); }
    }

    /// <summary>
    /// Merge lots of sorted lists
    /// </summary>
    public static IEnumerable<T> Merge<T>(IEnumerable<IEnumerable<T>> listOfLists)
        where T : IComparable<T>
    {
        int n = listOfLists.Count();
        if (n < 2) 
            return listOfLists.FirstOrDefault();
        else
            return Merge (Merge(listOfLists.Take(n/2)), Merge(listOfLists.Skip(n/2)));
    }


public static void Main(string[] args)
{

    var sample = Enumerable.Range(1, 5).Select((i) => Enumerable.Range(i, i+5).Select(j => string.Format("Test {0:00}", j)));

    Console.WriteLine("Merged:");
    foreach (var result in Merge(sample))
    {
        Console.WriteLine("\t{0}", result);
    }

Сколько списков необходимо объединить? Похоже, ваш алгоритм не будет эффективным, если вам нужно объединить много разных списков. Эта строка является проблемой:

var min = enumerators.OrderBy(t => orderBy(t.Value)).FirstOrDefault();

Это будет выполняться один раз для каждого элемента во всех списках, поэтому ваше время выполнения будет O (n * m), где n - ОБЩЕЕ количество элементов во всех списках, а n - количество списков. Выраженное в терминах средней длины списка в списке списков, время выполнения равно O (a * m ^ 2).

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

Вот мое решение:
Алгоритм берет первый элемент каждого списка и помещает их в небольшой вспомогательный класс (сортированный список, который принимает несколько элементов с одинаковым значением). Этот отсортированный список использует бинарную вставку.
Итак, первый элемент в этом списке - это элемент, который мы хотим вернуть следующим. После этого мы удаляем его из отсортированного списка и вставляем следующий элемент из его исходного списка (по крайней мере, до тех пор, пока этот список содержит еще какие-либо элементы). И снова мы можем вернуть первый элемент нашего отсортированного списка. Когда отсортированный список пуст, мы использовали все элементы из всех исходных списков и закончили.

В этом решении используется меньше операторов foreach и нет OrderBy на каждом шаге - что должно улучшить поведение во время выполнения. Только двоичная вставка должна выполняться снова и снова.

IEnumerable<T> MergeOrderedLists<T, TOrder>( IEnumerable<IEnumerable<T>> orderedlists, Func<T, TOrder> orderBy )
{
    // Get an enumerator for each list, create a sortedList
    var enumerators = orderedlists.Select( enumerable => enumerable.GetEnumerator() );
    var sortedEnumerators = new SortedListAllowingDoublets<TOrder, IEnumerator<T>>();

    // Point each enumerator onto the first element
    foreach( var enumerator in enumerators )
    {
        // Missing: assert true as the return value
        enumerator.MoveNext();

        //  Initially add the first value
        sortedEnumerators.AddSorted( orderBy( enumerator.Current ), enumerator );
    }

    // Continue as long as we have elements to return
    while( sortedEnumerators.Count != 0 )
    {
        // The first element of the sortedEnumerator list always
        // holds the next element to return
        var enumerator = sortedEnumerators[0].Value;

        // Return this enumerators current value
        yield return enumerator.Current;

        // Remove the element we just returned
        sortedEnumerators.RemoveAt( 0 );

        // Check if there is another element in the list of the enumerator
        if( enumerator.MoveNext() )
        {
            // Ok, so add it to the sorted list
            sortedEnumerators.AddSorted( orderBy( enumerator.Current ), enumerator );
        }
    }

Мой вспомогательный класс (использующий простую двоичную вставку):

private class SortedListAllowingDoublets<TOrder, T> : Collection<KeyValuePair<TOrder, T>> where T : IEnumerator
{
    public void AddSorted( TOrder value, T enumerator )
    {
        Insert( GetSortedIndex( value, 0, Count - 1 ), new KeyValuePair<TOrder, T>( value, enumerator ) );
    }

    private int GetSortedIndex( TOrder item, int startIndex, int endIndex )
    {
        if( startIndex > endIndex )
        {
            return startIndex;
        }
        var midIndex = startIndex + ( endIndex - startIndex ) / 2;
        return Comparer<TOrder>.Default.Compare( this[midIndex].Key, item ) < 0 ? GetSortedIndex( item, midIndex + 1, endIndex ) : GetSortedIndex( item, startIndex, midIndex - 1 );
    }
}

Что не реализовано сейчас: проверка на пустой список, что вызовет проблемы.
И класс SortedListAllowingDoublets может быть улучшен, чтобы принимать компаратор вместо использования Comparer.Default самостоятельно.