C# Leistung der statischen Zeichenfolge [] enthält() (sloooooow) vs. == Operator

Nur eine schnelle Abfrage: Ich hatte ein Stück Code, der eine Zeichenfolge mit einer langen Liste von Werten, z.C# Leistung der statischen Zeichenfolge [] enthält() (sloooooow) vs. == Operator

if(str == "string1" || str == "string2" || str == "string3" || str == "string4". 
    DoSomething();

Und das Interesse der Klarheit des Codes und Wartbarkeit habe ich es zu

public static string[] strValues = { "String1", "String2", "String3", "String4"}; 
... 
if(strValues.Contains(str) 
    DoSomething();

Nur die Code-Ausführungszeit von 2.5secs ging zu finden, um 6.8secs (ausgeführt ca. 200.000 Mal).
Ich verstehe sicherlich eine leichte Leistungsabwägung, aber 300%?
Wie auch immer, ich könnte die statischen Strings anders definieren, um die Leistung zu verbessern?
Prost.

Quelle

2010-05-20 Andrew White

Ist dieser Teil des Codes der Flaschenhals in Ihrer Anwendung? –

@mark, ist es wichtig? Die Frage ist, mehr Leistung zu bekommen, was eine gute Frage ist. –

"eine lange Liste von Werten": Wie lang ist "lang"? Wie viele Strings haben Sie in Ihrer Liste? –

Fyi ..

Verwendung:

private static HashSet<string> strHashSet = new HashSet<string>() 
{ "0string", "1string", "2string", "3string", "4string", "5string", 
    "6string", "7string", "8string", "9string", "Astring", "Bstring" }; 

private static List<string> strList = strHashSet.ToList(); 
private static string[] strArray = strList.ToArray(); 
private static Dictionary<int, string> strHashDict = strHashSet.ToDictionary(h => h.GetHashCode()); 
private static Dictionary<string, string> strDict = strHashSet.ToDictionary(h => h); 

// Only one test uses this method. 
private static bool ExistsInList(string str) 
{ 
    return strHashDict.ContainsKey(str.GetHashCode()); 
}

Überprüfung auf den ersten und letzte Strings in der Liste dann nach einer Zeichenkette nicht in der Liste überprüft: "xstring" Ausführen von 500.000 Iterationen, alle Zeiten in Millisekunden.

1.A Test: result = (str == "0string" || str == "1string" ... 
[storage var]   [first]:[ last ]:[ none ]:[average] 
strArray     3.78 : 45.90 : 57.77 : 35.82 

2.A Test: ExistsInList(string); 
[storage var]   [first]:[ last ]:[ none ]:[average] 
none     36.14 : 28.97 : 24.02 : 29.71 

3.A Test: .ContainsKey(string.GetHashCode()); 
[storage var]   [first]:[ last ]:[ none ]:[average] 
strHashDict    34.86 : 28.41 : 21.46 : 28.24 

4.A Test: .ContainsKey(string); 
[storage var]   [first]:[ last ]:[ none ]:[average] 
strDict     38.99 : 32.34 : 22.75 : 31.36 

5.A Test: .Contains(string); 
[storage var]   [first]:[ last ]:[ none ]:[average] 
strHashSet    39.54 : 34.78 : 24.17 : 32.83 
strList     23.36 : 122.07 : 127.38 : 90.94 
strArray    350.34 : 426.29 : 426.05 : 400.90 

6.A Test: .Any(p => p == string); 
[storage var]   [first]:[ last ]:[ none ]:[average] 
strHashSet    75.70 : 331.38 : 339.40 : 248.82 
strList     72.51 : 305.00 : 319.29 : 232.26 
strArray    38.49 : 213.63 : 227.13 : 159.75

Interessant (wenn nicht unerwartet) ergibt sich, wenn wir die Strings in der Liste ändern:

private static HashSet<string> strHashSet = new HashSet<string>() 
{ "string00", "string01", "string02", "string03", "string04", "string05", 
    "string06", "string07", "string08", "string09", "string10", "string11" };

Mit "string99", wie die Überprüfung keine.

1.B Test: result = (str == "string00" || str == "string01" ... 
[storage var]   [first]:[ last ]:[ none ]:[average] 
strArray    85.45 : 87.06 : 91.82 : 88.11 

2.B Test: ExistsInList(string); 
[storage var]   [first]:[ last ]:[ none ]:[average] 
none     30.12 : 27.97 : 21.36 : 26.48 

3.B Test: .ContainsKey(string.GetHashCode()); 
[storage var]   [first]:[ last ]:[ none ]:[average] 
strHashDict    32.51 : 28.00 : 20.83 : 27.11 

4.B Test: .ContainsKey(string); 
[storage var]   [first]:[ last ]:[ none ]:[average] 
strDict     36.45 : 32.13 : 22.39 : 30.32 

5.B Test: .Contains(string); 
[storage var]   [first]:[ last ]:[ none ]:[average] 
strHashSet    37.29 : 34.33 : 23.56 : 31.73 
strList     23.34 : 147.75 : 153.04 : 108.04 
strArray    349.62 : 460.19 : 459.99 : 423.26 

6.B Test: .Any(p => p == string); 
[storage var]   [first]:[ last ]:[ none ]:[average] 
strHashSet    76.26 : 355.09 : 361.31 : 264.22 
strList     70.20 : 332.33 : 341.79 : 248.11 
strArray    37.23 : 234.70 : 251.81 : 174.58

Für Fälle A und B sieht aus wie Tests 2 und 3 haben den Vorteil.

HashSet.Contains (string) ist jedoch sehr effizient, nicht durch Listeninhalte beeinflusst und hat eine klare Syntax ... könnte die beste Wahl sein.

Ja, es ist wahr, ich habe kein Leben.

Quelle

2010-05-21 16:07:59 Rusty

Das Leben oder nicht, das war verdammt gut! :) –

Beide Methoden, die Sie versucht haben, haben O (n) Leistung, so dass sie langsamer werden, wenn Sie weitere Zeichenfolgen hinzufügen. Wenn Sie .NET 3.5 oder neuer verwenden, können Sie stattdessen versuchen, eine HashSet<string> zu verwenden und sie zu Beginn der Anwendung einmal zu initialisieren. Sie können dann ungefähr O (1) Suchvorgänge erhalten.

Für .NET v2.0 können Sie eine HashSet mit einer Dictionary<string, object> emulieren und ContainsKey verwenden und den Wert nicht verwenden.

Quelle

2010-05-20 22:31:20

Sorry, aber du liegst etwas falsch. Ich denke, das beste für Framework 1.x ist 'System.Collections.Hashtable'. Weil 1.x keine Generika hat! – abatishchev

@abatiishchev: Sie haben Recht, dass 1.x keine Generika hat. Aber ich denke, es ist in Ordnung, anzunehmen, dass Leute .NET.x in diesen Tagen nicht verwenden, es sei denn, sie erwähnen es in ihrer Frage. Nachdem ich das gesagt habe, habe ich meine Antwort umformuliert, um es klarer zu machen. –

hat gerade ein Experiment gemacht, und HashSet ist die gleiche Geschwindigkeit wie die ifs. –

Führen Sie diese 200.000 Mal im Produktionscode tatsächlich? Sie können Hash-Checks als schnelleres Negativ prüfen, wenn dies der Fall ist.

Wenn die 200.000-mal nur um den Unterschied zu veranschaulichen, dann würde ich mich nicht darum kümmern. Es ist nur ein 0,02 Millisekunden Anstieg der Zeit.

Contains ist allgemeiner als das Testen von statischen Strings, daher ist der Overhead gering. Wenn dieser Code kein Flaschenhals ist, wie Mark es erwähnt hat, lohnt es sich nicht, ihn zu optimieren. Es gibt ein berühmtes Zitat in CS: "vorzeitige Optimierung ist die Wurzel allen Übels." Das Zitat ist nicht sehr genau, aber es ist eine gute Erinnerung an die ultimative Optimierungsrichtlinie: messen zuerst.

Quelle

2010-05-20 22:32:16

das ist alles gut und gut, aber Sie sollten nicht verschwenderisch sein, wenn es genauso einfach ist, eine effizientere Alternative zu verwenden. und das Ersetzen von string [] durch HashSet ist effizienter und ebenso prägnant. Auf diese Weise werden effiziente Mechanismen standardmäßig ausgewählt, ob sie tatsächlich einen wirklichen Unterschied machen oder nicht –

Ich finde, dass * klarer und lesbarer Code * viel mehr Zeit spart als viel Arbeit in Mikrooptimierungen zu investieren, die eine nicht spürbare geringe Laufzeit haben wenn sie in realen Szenarien verwendet werden. –

sicher ...Aber wie gesagt, Sie sollten, wenn es effizientere Standardwerte gibt, die von gleicher Lesbarkeit sind. Der Rat der verfrühten Optimierung wurde hauptsächlich im Zusammenhang mit der Strukturierung von Systemen zugunsten von Leistungen gegeben, die sich niemals auszahlen können. Das Problem ist, dass die Leute es jetzt als Ausrede benutzen, nicht im Allgemeinen effizient zu sein, wenn sie es können. Die Ersetzung von string [] durch hashset verursacht keine Strukturänderung –

Sie können feststellen, dass Contains() für eine längere Liste besser funktioniert. Es kann zum Beispiel die Liste sortieren und eine binäre Suche (nur ein Gedankenexperiment, für ein Beispiel).

Quelle

2010-05-20 22:43:29 whybird

Leider kann Contains solche Annahmen nicht treffen. Es wird immer eine lineare Suche auf Arrays durchgeführt. – Ruben

Hier ist eine Alternative, die Sie möglicherweise lesbar und wartbar finden, die Sie für die Geschwindigkeit testen möchten. Wenn Sie es auf Geschwindigkeit testen, posten Sie bitte Ihr Ergebnis!

 switch (str) 
     { 
      case "String1": 
      case "String2": 
      case "String3": 
      case "String4": 
       DoSomething(); 
       break; 
     }

Quelle

2010-05-20 22:57:05 whybird

Soweit ich mich erinnern kann, erzeugt der C# -Compiler automatisch eine Art von Hashtable für einen Switch-Case-Block, wenn die Anzahl der Fälle größer als 4 ist. – abatishchev

Sie benötigen einen 'break' nach' DoSomething() ', um dies zu kompilieren . – juharr

@juharr du bist richtig; Antwort editiert, um es hinzuzufügen. – whybird

Obwohl eine HashSet<string> wie vorgeschlagen verwendet, könnte eine bessere Option sein, den Grund, warum strValues.Contains(str) langsamer ist, ist, weil es sich um eine generische Erweiterungsmethode ist. Es gibt keine Contains-Methode für Arrays.

So wie es für Arrays funktioniert, ist im Grunde

if (strValues is ICollection<string>) // true 
{ 
    return ((ICollection<string>) strValues).Contains(str); 
}

, die einen typecheck Anruf, Typumwandlung und virtuelle ergänzt. Dann wird das Array iteriert (was Begrenzungen verursacht). Nur dann wird es zu String-Vergleichen kommen. So macht es eine Los mehr Arbeit.

Beachten Sie, dass 3 in C# (die Sie verwenden müssen, wenn Sie Erweiterungsmethoden verwenden), können Sie einfach die HashSet<string> wie folgt initialisieren:

public static HashSet<string> strValues = new HashSet<string> { 
            "String1", "String2", "String3", "String4" };

Dieses Ihr Programm hält ebenso lesbar wie es ist jetzt mit Arrays.

Quelle

2010-05-20 23:56:15 Ruben

C# Leistung der statischen Zeichenfolge [] enthält() (sloooooow) vs. == Operator

Antwort

Verwandte Themen