Effizient fusionieren String-Arrays in .NET, unterschiedliche Werte halten
https://stackoverflow.com/questions/146358
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich bin mit .NET 3.5. Ich habe zwei String-Arrays, die einen oder mehr Werte teilen können:
string[] list1 = new string[] { "apple", "orange", "banana" };
string[] list2 = new string[] { "banana", "pear", "grape" };
ich einen Weg, möchte sie in ein Array ohne doppelte Werte fusionieren:
{ "apple", "orange", "banana", "pear", "grape" }
Das kann ich mit LINQ:
string[] result = list1.Concat(list2).Distinct().ToArray();
aber ich glaube, dass für großen Arrays nicht sehr effizient ist.
Gibt es einen besseren Weg?
Lösung
string[] result = list1.Union(list2).ToArray();
Msdn : „Diese Methode schließt Duplikate aus dem Rück Set Dies. ist ein anderes Verhalten auf die Concat (TSource) -Methode, die alle Elemente in den Eingangssequenzen, einschließlich Duplikate zurückkehren.“
Andere Tipps
Warum stellen Sie sich, dass es ineffizient wäre? Soweit ich weiß, beide Concat und Distinct sind faul ausgewertet, eine HashSet hinter den Kulissen für Distinct mit Spur der Elemente zu halten, die bereits zurückgegeben wurden.
Ich bin mir nicht sicher, wie Sie es effizienter ist als die in allgemeiner Art und Weise zu machen, verwalten würden:)
EDIT: Distinct tatsächlich verwendet Set (eine interne Klasse) statt HashSet, aber das Wesentliche ist nach wie vor richtig. Dies ist ein wirklich gutes Beispiel dafür, wie ordentlich LINQ ist. Die einfachste Antwort ist so ziemlich so effizient wie Sie ohne weiteres Domain-Wissen erreichen können.
Der Effekt ist das Äquivalent von:
public static IEnumerable<T> DistinctConcat<T>(IEnumerable<T> first, IEnumerable<T> second)
{
HashSet<T> returned = new HashSet<T>();
foreach (T element in first)
{
if (returned.Add(element))
{
yield return element;
}
}
foreach (T element in second)
{
if (returned.Add(element))
{
yield return element;
}
}
}
.NET 3.5 die HashSet Klasse eingeführt, die dies tun könnte:
IEnumerable<string> mergedDistinctList = new HashSet<string>(list1).Union(list2);
Nicht die Leistung sicher, aber es sollte das Linq Beispiel du hast verloren.
EDIT: Ich stehe korrigiert. Die faule Implementierung von Concat und Distinct einen Schlüsselspeicher und Geschwindigkeitsvorteil. Concat / Distinct ca. 10% schneller und spart mehrere Kopien von Daten.
I bestätigt durch Code:
Setting up arrays of 3000000 strings overlapping by 300000
Starting Hashset...
HashSet: 00:00:02.8237616
Starting Concat/Distinct...
Concat/Distinct: 00:00:02.5629681
ist die Ausgabe von:
int num = 3000000;
int num10Pct = (int)(num / 10);
Console.WriteLine(String.Format("Setting up arrays of {0} strings overlapping by {1}", num, num10Pct));
string[] list1 = Enumerable.Range(1, num).Select((a) => a.ToString()).ToArray();
string[] list2 = Enumerable.Range(num - num10Pct, num + num10Pct).Select((a) => a.ToString()).ToArray();
Console.WriteLine("Starting Hashset...");
Stopwatch sw = new Stopwatch();
sw.Start();
string[] merged = new HashSet<string>(list1).Union(list2).ToArray();
sw.Stop();
Console.WriteLine("HashSet: " + sw.Elapsed);
Console.WriteLine("Starting Concat/Distinct...");
sw.Reset();
sw.Start();
string[] merged2 = list1.Concat(list2).Distinct().ToArray();
sw.Stop();
Console.WriteLine("Concat/Distinct: " + sw.Elapsed);
Hinweis Dies ist eine vorzeitige Optimierung. Für Ihr Beispiel Arrays verwenden, um die 3,5-Erweiterungsmethoden. Bis Sie wissen, dass Sie ein Leistungsproblem in diesem Bereich haben, sollten Sie Bibliotheks-Code verwenden.
Wenn Sie die Arrays sortieren können, oder sie sortiert, wenn Sie zu diesem Punkt in dem Code zu erhalten, können Sie die folgenden Methoden verwenden.
Diese werden ein Element aus sowohl ziehen, und produzieren das „niedrigste“ Objekt, dann ein neues Element aus der entsprechenden Quelle holen, bis beide Quellen erschöpft sind. In dem Fall, dass das aktuelle Element aus den beiden Quellen geholt gleich, es wird die eine von der ersten Quelle erzeugen, und überspringt sie in beiden Quellen.
private static IEnumerable<T> Merge<T>(IEnumerable<T> source1,
IEnumerable<T> source2)
{
return Merge(source1, source2, Comparer<T>.Default);
}
private static IEnumerable<T> Merge<T>(IEnumerable<T> source1,
IEnumerable<T> source2, IComparer<T> comparer)
{
#region Parameter Validation
if (Object.ReferenceEquals(null, source1))
throw new ArgumentNullException("source1");
if (Object.ReferenceEquals(null, source2))
throw new ArgumentNullException("source2");
if (Object.ReferenceEquals(null, comparer))
throw new ArgumentNullException("comparer");
#endregion
using (IEnumerator<T>
enumerator1 = source1.GetEnumerator(),
enumerator2 = source2.GetEnumerator())
{
Boolean more1 = enumerator1.MoveNext();
Boolean more2 = enumerator2.MoveNext();
while (more1 && more2)
{
Int32 comparisonResult = comparer.Compare(
enumerator1.Current,
enumerator2.Current);
if (comparisonResult < 0)
{
// enumerator 1 has the "lowest" item
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
}
else if (comparisonResult > 0)
{
// enumerator 2 has the "lowest" item
yield return enumerator2.Current;
more2 = enumerator2.MoveNext();
}
else
{
// they're considered equivalent, only yield it once
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
more2 = enumerator2.MoveNext();
}
}
// Yield rest of values from non-exhausted source
while (more1)
{
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
}
while (more2)
{
yield return enumerator2.Current;
more2 = enumerator2.MoveNext();
}
}
}
Beachten Sie, dass, wenn eine der Quellen Duplikate enthält, Duplikate in der Ausgabe sehen könnten. Wenn Sie diese Duplikate in den bereits sortierten Listen entfernen möchten, verwenden Sie die folgende Methode:
private static IEnumerable<T> CheapDistinct<T>(IEnumerable<T> source)
{
return CheapDistinct<T>(source, Comparer<T>.Default);
}
private static IEnumerable<T> CheapDistinct<T>(IEnumerable<T> source,
IComparer<T> comparer)
{
#region Parameter Validation
if (Object.ReferenceEquals(null, source))
throw new ArgumentNullException("source");
if (Object.ReferenceEquals(null, comparer))
throw new ArgumentNullException("comparer");
#endregion
using (IEnumerator<T> enumerator = source.GetEnumerator())
{
if (enumerator.MoveNext())
{
T item = enumerator.Current;
// scan until different item found, then produce
// the previous distinct item
while (enumerator.MoveNext())
{
if (comparer.Compare(item, enumerator.Current) != 0)
{
yield return item;
item = enumerator.Current;
}
}
// produce last item that is left over from above loop
yield return item;
}
}
}
Beachten Sie, dass keiner von diesen wird intern eine Datenstruktur verwenden, um eine Kopie der Daten zu halten, damit sie billig sein, wenn der Eingang sortiert ist. Wenn Sie nicht können oder nicht, garantieren, dass, sollten Sie die 3.5-Erweiterungsmethoden verwenden, die Sie bereits gefunden.
Hier ist Beispielcode, der die oben genannten Methoden aufruft:
String[] list_1 = { "apple", "orange", "apple", "banana" };
String[] list_2 = { "banana", "pear", "grape" };
Array.Sort(list_1);
Array.Sort(list_2);
IEnumerable<String> items = Merge(
CheapDistinct(list_1),
CheapDistinct(list_2));
foreach (String item in items)
Console.Out.WriteLine(item);
Wahrscheinlich eine Hash-Tabelle mit Ihren Werten als Schlüssel zu schaffen (nur diejenigen, die nicht bereits vorhanden Hinzufügen) und dann die Schlüssel zu einem Array konvertieren könnte eine praktikable Lösung sein.
Sie wissen nicht, welche Methode ist schneller, bis Sie es messen. Der LINQ Weg ist elegant und leicht zu verstehen.
Eine weitere Möglichkeit ist es, einen Satz als ein Hash-Array (Dictionary) und fügen alle Elemente der beiden Arrays zu dem Satz zu implementieren. Dann verwendet set.Keys.ToArray () Methode das resultierende Array zu schaffen.
