Die meisten effizienten Algorithmus für die Zusammenführung sortiert IEnumerable<T>

Hier ist meine vierte (Dank an @tanascius zum schieben diese zusammen zu etwas viel mehr LINQ -) Schnitt ist es:

public static IEnumerable<T> MergePreserveOrder3<T, TOrder>(
    this IEnumerable<IEnumerable<T>> aa,
    Func<T, TOrder> orderFunc)
where TOrder : IComparable<TOrder>
{
    var items = aa.Select(xx => xx.GetEnumerator()).Where(ee => ee.MoveNext())
        .OrderBy(ee => orderFunc(ee.Current)).ToList();

    while (items.Count > 0)
    {
        yield return items[0].Current;

        var next = items[0];
        items.RemoveAt(0);
        if (next.MoveNext())
        {
            //simple sorted linear insert
            var value = orderFunc(next.Current);
            var ii = 0;
            for ( ; ii < items.Count; ++ii)
            {
                if (value.CompareTo(orderFunc(items[ii].Current)) <= 0)
                {
                    items.Insert(ii, next);
                    break;
                }
            }

            if (ii == items.Count) items.Add(next);
        }
        else next.Dispose(); //woops! can't forget IDisposable
    }
}

Ergebnisse:

for (int p = 0; p < people.Count; ++p)
{
    Console.WriteLine("List {0}:", p + 1);
    Console.WriteLine("\t{0}", String.Join(", ", people[p].Select(x => x.Name)));
}

Console.WriteLine("Merged:");
foreach (var person in people.MergePreserveOrder(pp => pp.Age))
{
    Console.WriteLine("\t{0}", person.Name);
}

List 1:
        8yo, 22yo, 47yo, 49yo
List 2:
        35yo, 47yo, 60yo
List 3:
        28yo, 55yo, 64yo
Merged:
        8yo
        22yo
        28yo
        35yo
        47yo
        47yo
        49yo
        55yo
        60yo
        64yo

Verbessert .Net 4.0 ist Tupel-Unterstützung:

public static IEnumerable<T> MergePreserveOrder4<T, TOrder>(
    this IEnumerable<IEnumerable<T>> aa,
    Func<T, TOrder> orderFunc) where TOrder : IComparable<TOrder>
{
    var items = aa.Select(xx => xx.GetEnumerator())
                  .Where(ee => ee.MoveNext())
                  .Select(ee => Tuple.Create(orderFunc(ee.Current), ee))
                  .OrderBy(ee => ee.Item1).ToList();

    while (items.Count > 0)
    {
        yield return items[0].Item2.Current;

        var next = items[0];
        items.RemoveAt(0);
        if (next.Item2.MoveNext())
        {
            var value = orderFunc(next.Item2.Current);
            var ii = 0;
            for (; ii < items.Count; ++ii)
            {
                if (value.CompareTo(items[ii].Item1) <= 0)
                {   //NB: using a tuple to minimize calls to orderFunc
                    items.Insert(ii, Tuple.Create(value, next.Item2));
                    break;
                }
            }

            if (ii == items.Count) items.Add(Tuple.Create(value, next.Item2));
        }
        else next.Item2.Dispose(); //woops! can't forget IDisposable
    }
}

Hier ist eine Lösung, die sehr gut die Komplexität-Analyse-und das ist wesentlich kürzer als die anderen vorgeschlagenen Lösungen.

public static IEnumerable<T> Merge<T>(this IEnumerable<IEnumerable<T>> self) 
    where T : IComparable<T>
{
    var es = self.Select(x => x.GetEnumerator()).Where(e => e.MoveNext());
    var tmp = es.ToDictionary(e => e.Current);
    var dict = new SortedDictionary<T, IEnumerator<T>>(tmp);
    while (dict.Count > 0)
    {
        var key = dict.Keys.First();
        var cur = dict[key];
        dict.Remove(key);
        yield return cur.Current;
        if (cur.MoveNext())
            dict.Add(cur.Current, cur);                    
    }
}

Hier ist eine Lösung OHNE SORTIERUNG ... nur die minimale Anzahl von vergleichen. (Ich weggelassen, um tatsächliche func übergeben, für die Einfachheit). Aktualisiert zu bauen, einen ausgeglichenen Baum:-

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

Meine version von sixlettervariables Antwort. Ich reduzierte die Anzahl der Aufrufe orderFunc (jedes element nur durchläuft orderFunc einmal), und im Fall von Bindungen, die Sortierung übersprungen. Dieser ist optimiert für eine kleine Zahl von Quellen, die eine größere Anzahl von Elementen innerhalb jeder Quelle und möglicherweise eine teure 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);
        }
      }
    }
  }
}

Bin ich Wetten könnte dies weiter verbessert werden, indem ein SortedDictionary, bin aber nicht mutig genug, zu versuchen, eine Lösung, bei der man ohne einen editor.

Diese sieht aus wie eine furchtbar nützliche Funktion zu haben, um, so habe ich beschlossen, nehmen Sie einen Stich an Sie. Mein Ansatz ist ein viel wie heightechrider, dass es bricht, das problem in das Zusammenführen von zwei sortierten IEnumerables in einem, dann mit ein und verbindet es mit dem nächsten in der Liste. Es ist wahrscheinlich eine Optimierung, die Sie tun können, es funktioniert aber mit meiner einfachen testcase:

      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;

                            }
                      }
                 }
            }
      }

Dann, um es zu testen:

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

Den Versuch, die auf @cdiggins ist Antwort.
Diese Implementierung funktioniert, wenn zwei Elemente als gleich verglichen werden, sind in zwei unterschiedlichen Sequenzen (ich. e. nicht die Fehler erwähnt, die von @ChadHenderson).

Wird der Algorithmus beschrieben in der Wikipedia, die Komplexität ist O(m log n), wo n wird die Anzahl der Listen, die zusammengeführt und m ist die Summe der Längen der Listen.

Den OrderedBag<T> aus Wintellect.PowerCollections verwendet, anstatt eine heap-basierte priority queue, aber es ändert nichts an der Komplexität.

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

Habe ich nahm einen mehr funktionalen Ansatz, hoffe das liest sich gut.

Hier ist zunächst einmal die merge-Methode selbst:

public static IEnumerable<T> MergeSorted<T>(IEnumerable<IEnumerable<T>> xss) where T :IComparable
{
    var stacks = xss.Select(xs => new EnumerableStack<T>(xs)).ToList();

    while (true)
    {
        if (stacks.All(x => x.IsEmpty)) yield break;

        yield return 
            stacks
                .Where(x => !x.IsEmpty)
                .Select(x => new { peek = x.Peek(), x })
                .MinBy(x => x.peek)
                .x.Pop();
    }
}

Die Idee ist, dass wir jeden IEnumerable in EnumerableStack hat Peek(), Pop() und IsEmpty Mitglieder.

Es funktioniert wie eine normale stack. Beachten Sie, dass der Aufruf IsEmpty könnte aufzählen gewickelt IEnumerable.

Hier ist der code:

///<summary>
///Wraps IEnumerable in Stack like wrapper
///</summary>
public class EnumerableStack<T>
{
    private enum StackState
    {
        Pending,
        HasItem,
        Empty
    }

    private readonly IEnumerator<T> _enumerator;

    private StackState _state = StackState.Pending;

    public EnumerableStack(IEnumerable<T> xs)
    {
        _enumerator = xs.GetEnumerator();
    }

    public T Pop()
    {
        var res = Peek(isEmptyMessage: "Cannot Pop from empty EnumerableStack");
        _state = StackState.Pending;
        return res;
    }

    public T Peek()
    {
        return Peek(isEmptyMessage: "Cannot Peek from empty EnumerableStack");
    }

    public bool IsEmpty
    {
        get
        {
            if (_state == StackState.Empty) return true;
            if (_state == StackState.HasItem) return false;
            ReadNext();
            return _state == StackState.Empty;
        }
    }

    private T Peek(string isEmptyMessage)
    {
        if (_state != StackState.HasItem)
        {
            if (_state == StackState.Empty) throw new InvalidOperationException(isEmptyMessage);
            ReadNext();
            if (_state == StackState.Empty) throw new InvalidOperationException(isEmptyMessage);
        }
        return _enumerator.Current;
    }

    private void ReadNext()
    {
        _state = _enumerator.MoveNext() ? StackState.HasItem : StackState.Empty;
    }
}

Schließlich, hier ist der MinBy Erweiterung Methode im Falle noch nicht geschrieben man auf der eigenen schon:

public static T MinBy<T, TS>(this IEnumerable<T> xs, Func<T, TS> selector) where TS : IComparable
{
    var en = xs.GetEnumerator();
    if (!en.MoveNext()) throw new Exception();

    T max = en.Current;
    TS maxVal = selector(max);
    while(en.MoveNext())
    {
        var x = en.Current;
        var val = selector(x);
        if (val.CompareTo(maxVal) < 0)
        {
            max = x;
            maxVal = val;
        }
    }

    return max;
}

Ich bin misstrauisch LINQ ist smart genug, um die Vorteile der vor bestehende Sortierung:

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