Der schnellste Weg, um herauszufinden, ob zwei iCollection -Kollektionen dieselben Objekte enthalten

StackOverflow https://stackoverflow.com/questions/308476

Frage

Was ist der schnellste Weg, um herauszufinden, ob zwei ICollection<T> Sammlungen enthalten genau die gleichen Einträge? Brute Force ist klar, ich habe mich gefragt, ob es eine elegantere Methode gibt.

Wir verwenden C# 2.0, also bitte keine Erweiterungsmethoden, bitte!

Bearbeiten: Die Antwort wäre sowohl für geordnete als auch für nicht ordnungsgemäße Sammlungen interessant und würde hoffentlich für jeden anders anders sein.

War es hilfreich?

Lösung

Verwenden Sie C5

http://www.itu.dk/research/c5/

Enthält

"Überprüfen Sie, ob sich alle Artikel in einer mitgelieferten Sammlung in dieser Tasche befinden
(Multiplikationen zählen).
Die Gegenstände, nach denen man suchen sollte.

Wahr, wenn alle Elemente gefunden werden. "

[Tested]

public virtual bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T
{
  HashBag<T> res = new HashBag<T>(itemequalityComparer);

  foreach (T item in items)
    if (res.ContainsCount(item) < ContainsCount(item))
      res.Add(item);
    else
      return false;

  return true;
}

Andere Tipps

Vergleichen Sie zuerst die.Zählen von den Sammlungen, wenn sie die gleiche Zählung haben, do eine brutale Kraft vergleiche alle Elemente. Schlimmste Szenarien sind o (n). Dies ist in dem Fall, dass die Reihenfolge der Elemente gleich sein muss.

Der zweite Fall, in dem die Bestellung nicht gleich ist, müssen Sie ein Wörterbuch verwenden, um die Anzahl der in den Sammlungen enthaltenen Elemente zu speichern: Hier ist ein möglicher Algorithmus

  • Vergleichen Sie die Sammlung der Sammlung: Rückgabe falsch, wenn sie unterschiedlich sind
  • Iterieren Sie die erste Sammlung
    • Wenn das Element im Wörterbuch nicht vorhanden ist, fügen Sie mit Key = itel, value = 1 (die Anzahl) hinzu und geben Sie sie ein.
    • Wenn der Artikel existiert, erhöhen Sie die Anzahl für das Element int das Wörterbuch;
  • Iterieren Sie die zweite Sammlung
    • Wenn der Artikel nicht im Wörterbuch ist, geben Sie false zurück
    • Wenn sich der Artikel im Wörterbuch -Decrement -Zählung für den Artikel befindet
      • Wenn count == 0 das Entfernen von Element;
  • return Dictionary.Count == 0;

Für bestellte Sammlungen können Sie die verwenden SequenceEqual() Erweiterungsmethode definiert durch System.Linq.Enumerable:

if (firstCollection.SequenceEqual(secondCollection))

Sie meinen die gleichen oder die gleichen Einträge in derselben Reihenfolge?

Angenommen, Sie möchten vergleichen, wenn sie dieselben Einträge in derselben Reihenfolge enthalten, ist "Brute Force" wirklich Ihre einzige Option in C# 2.0. Ich weiß, was Sie unter nicht elegant meinen, aber wenn die Atomvergleich selbst o (1) ist, sollte der gesamte Prozess in O (n) sein, was nicht ist das Schlecht.

Wenn die Einträge in derselben Reihenfolge sein müssen (nicht nur dieselbe), schlage ich - als Optimierung - vor, beide Sammlungen gleichzeitig zu itererieren und den aktuellen Eintrag in jeder Sammlung zu vergleichen. Ansonsten ist die rohe Kraft der richtige Weg.

Oh, und ein weiterer Vorschlag - Sie können gleich für die Sammlungsklasse überschreiben und das Gleichstellungsmaterial dort implementieren (hängt jedoch von Ihrem Projekt ab).

Mit der C5 -Bibliothek mit zwei Sätzen können Sie erneut verwenden:

C5.ICollection<T> set1 = C5.ICollection<T> ();
C5.ICollection<T> set2 = C5.ICollecton<T> ();
if (set1.UnsequencedEquals (set2)) {
  // Do something
}

Die C5 -Bibliothek enthält eine Heuristik, die tatsächlich die nicht ausgeleiteten Hash -Codes der beiden Sätze testet (siehe C5.ICollection<T>.GetUnsequencedHashCode()), so dass, wenn die Hash -Codes der beiden Sätze ungleich sind, nicht über jedes Element iterieren müssen, um die Gleichheit zu testen.

Auch für Sie ist etwas zu beachten ist das C5.ICollection<T> Erben von System.Collections.Generic.ICollection<T>, Sie können so C5 -Implementierungen verwenden, während Sie die .NET -Schnittstellen verwenden (obwohl Sie über die geizigen Schnittstellen von .NET auf weniger Funktionen zugreifen können).

Brute Force nimmt O (n) - Vergleich aller Elemente (vorausgesetzt, sie sind sortiert), was ich für das Beste für das Beste für die Daten halte - es sei denn, es gibt eine Eigenschaft der Daten, die es einfacher machen.

Ich denke für den Fall von nicht sortiert, sein o (n*n).

In diesem Fall würde ich eine Lösung denken, die auf a basiert Zusammenführen, sortieren würde wahrscheinlich helfen.

Könnten Sie es zum Beispiel neu modellieren, dass es nur eine Sammlung gab? Oder 3 Kollektionen, eine für diejenigen, die in Sammlung a nur für B und in beiden eine Sammlung von A und B nur leer sind - dann sind sie gleich ... ich gehe wahrscheinlich auf völlig falscher Tangente aus hier...

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top