Die meisten effizienten Algorithmus für die Zusammenführung sortiert IEnumerable<T>
Habe ich mehrere riesige sortiert enumerable-Sequenzen, die ich Zusammenführen möchten. Diese Listen manipuliert, weil IEnumerable
aber bereits sortiert. Da die input-Listen sortiert sind, sollte es möglich sein, mischen Sie Sie in einer Tour, ohne neu zu Sortieren alles.
Möchte ich halten, die zeitlich verzögert die Ausführung Verhalten.
Ich zu schreiben versucht, ein naiver Algorithmus, die das tun (siehe unten). Allerdings sieht es ziemlich hässlich und ich bin mir sicher, dass es optimiert werden kann. Es kann existieren eine mehr Akademische Algorithmus...
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;
}
}
Die Methode kann verwendet werden, wie:
//Person lists are already sorted by age
MergeOrderedLists(orderedList, p => p.Age);
vorausgesetzt, die folgenden Person
Klasse existiert irgendwo:
public class Person
{
public int Age { get; set; }
}
Duplikate sollten konserviert werden, wir kümmern uns nicht um Ihre Reihenfolge in der Sequenz. Sehen Sie offensichtliche Optimierung, die ich verwenden könnte?
Du musst angemeldet sein, um einen Kommentar abzugeben.
Hier ist meine vierte (Dank an @tanascius zum schieben diese zusammen zu etwas viel mehr LINQ -) Schnitt ist es:
Ergebnisse:
Verbessert .Net 4.0 ist Tupel-Unterstützung:
items.Any()
viel schneller alsitems.Count
in einer Vielzahl von Situationen? Es ist wahrscheinlich ein bisschen langsamer, für in-memory-Listen, aber wenn einer der Enumeratoren sind wirklich lazy loading oder mityield
, dann.Any()
sollte viel schneller sein.items
ist einList<T>
, soitems.Count
wirdO(1)
.Einen Versuch würde ich machen, die möglicherweise verbessern die Klarheit und Leistung ist diese:
T
,IEnumerable<T>
geordnet nach Ihrer Vergleich-Funktion aufT
IEnumerable<T>
zusammengeführt werden kann, fügen Sie das Element an die Warteschlange Priorität versehen mit einem Verweis auf dieIEnumerable<T>
wo es entstanden istIEnumerable<T>
in seiner Anmerkung zu dem nächsten elementMoveNext()
true zurückgegeben, fügen Sie das nächste element der Warteschlange Priorität versehen mit einem Verweis auf dieIEnumerable<T>
Sie gerade fortgeschritteneMoveNext()
false zurückgegeben, don nichts hinzufügen, um die WarteschlangeIEnumerable
in diese Antwort sollte eigentlichIEnumerator
. Sie nicht Voraus, einenIEnumerable
Sie einfach nur einIEnumerator
aus ihm heraus. Sie Voraus eineIEnumerator
. Sie brauchen auch nicht zu habenTuple<T, IEnumerator<T>>
, können Sie auch einfach einenIEnumerator<T>
und verwendenIEnumerator.Current
Wann immer Sie möchten, das aktuelle Element in der Sequenz.Hier ist eine Lösung, die sehr gut die Komplexität-Analyse-und das ist wesentlich kürzer als die anderen vorgeschlagenen Lösungen.
Wie viele Listen, die Sie erwarten zu müssen, um zu fusionieren? Es sieht aus wie dein Algorithmus nicht effizient, wenn Sie viele verschiedene Listen zu verschmelzen. Diese Zeile ist das Problem:
Dieser wird ausgeführt, sobald die für jedes element in allen Listen, so dass Ihre Laufzeit in O(n * m), wobei n die GESAMTZAHL der Elemente in allen Listen, und n ist die Anzahl der Listen. Ausgedrückt in der durchschnittlichen Länge einer Liste in der Liste von Listen, die Laufzeit ist O(a * m^2).
Wenn Sie gehen zu müssen, verbinden eine Menge von Listen, würde ich vorschlagen, mit einem heap. Dann in jeder iteration können Sie den kleinsten Wert aus dem heap, und fügen Sie das nächste element auf dem heap aus der Liste, der kleinste Wert kam.
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:-
Hier ist meine Lösung:
Der Algorithmus nimmt die erste element jeder Liste und legt Sie in eine kleine helper-Klasse (eine sortierte Liste, die akzeptiert mehrere Elemente mit dem gleichen Wert). Diese sortierte Liste verwendet eine binary einfügen.
Also das erste element in dieser Liste ist das element, wir wollen zurück weiter. Danach entfernen wir es aus der sortierten Liste aus, und legen Sie das nächste element aus der ursprünglichen Quelle Liste (zumindest so lange, wie diese Liste enthält mehr Elemente). Wieder können wir das erste element unserer sortierten Liste. Wenn die sortierte Liste leer ist, sobald wir verwendet alle element aus verschiedenen Quell-Listen und sind fertig.
Diese Lösung verbraucht weniger
foreach
Aussagen und keineOrderBy
in jedem Schritt - verbessert das Laufzeitverhalten. Nur die Binärdatei einfügen getan werden muss, wieder und wieder.Mein Helfer-Klasse (mit Hilfe eines einfachen binären einfügen):
Was nicht umgesetzt und jetzt: überprüfen Sie, ob eine leere Liste, die wird Probleme verursachen.
Und die
SortedListAllowingDoublets
Klasse verbessert werden könnten, nehmen einen comparer, anstatt dieComparer<TOrder>.Default
auf seine eigenen.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.
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.
List
für jeden Wert. Die OP sagt, dass er will, um große Listen Sortieren - also die Initialisierung von so vielen Listen ein problem sein könnte. Ich hatte eine Lösung mit einerSortedDictionary
, aber der Schlüssel muss eindeutig sein - so muss der Wert einer Sammlung wieder. Das ist, warum ich beschlossen, mit einer einzigen Liste, die ist in der Lage, mehrere Schlüssel enthalten (und nutzt schnelle binäre Suche)Hier ist eine Linq-freundliche Lösung, basierend auf dem Wintellect ist OrderedBag:
Wenn Sie eine Enumerator-basierte Lösung, vergessen Sie nicht zu nennen Dispose()
Und hier ist ein einfacher test:
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:
Dann, um es zu testen:
Wurde ich gefragt diese Frage eine interview-Frage an diesem Abend nicht und haben eine tolle Antwort in 20 Minuten oder so zugeteilt. Also habe ich mich gezwungen zu schreiben, ein Algorithmus, ohne irgendetwas zu suchen. Die Einschränkung war, dass die Eingänge wurden bereits sortiert sind. Hier ist mein code:
Hoffe, es hilft.
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.Jede Liste zusammengeführt werden sollen, bereits sortiert. Diese Methode wird finden die gleichen Elemente in Bezug auf die Reihenfolge der Listen. Zum Beispiel, wenn Elemente Ti == Tj, und Sie werden jeweils aus der Liste i und Liste j (i < j), dann ist Ti vor Tj in das zusammengeführte Ergebnis.
Die Komplexität ist O(mn), wobei n die Anzahl der Listen, die zusammengeführt und m ist die Summe der Längen der Listen.
{}
- Taste. Es ist ein Knebel, den Sie sehen.Habe ich nahm einen mehr funktionalen Ansatz, hoffe das liest sich gut.
Hier ist zunächst einmal die merge-Methode selbst:
Die Idee ist, dass wir jeden
IEnumerable
inEnumerableStack
hatPeek()
,Pop()
undIsEmpty
Mitglieder.Es funktioniert wie eine normale stack. Beachten Sie, dass der Aufruf
IsEmpty
könnte aufzählen gewickeltIEnumerable
.Hier ist der code:
Schließlich, hier ist der MinBy Erweiterung Methode im Falle noch nicht geschrieben man auf der eigenen schon:
Dies ist eine Alternative Lösung:
Ich bin misstrauisch LINQ ist smart genug, um die Vorteile der vor bestehende Sortierung:
IEnumerable
im Allgemeinen? Ich bezweifle es.