Prestazioni C# della stringa statica [] contains() (slooooow) vs. operatore ==

Solo una breve query: Avevo un pezzo di codice che confrontava una stringa con un lungo elenco di valori, ad es.Prestazioni C# della stringa statica [] contains() (slooooow) vs. operatore ==

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

E per motivi di chiarezza e manutenibilità del codice ho cambiato in

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

Solo per trovare il tempo di esecuzione di codice è passato da 2.5secs a 6.8secs (eseguiti ca. 200.000 volte).
Sicuramente comprendo un leggero aumento delle prestazioni, ma il 300%?
In ogni caso, potrei definire le stringhe statiche in modo diverso per migliorare le prestazioni?
Cheers.

fonte

2010-05-20 Andrew White

Questa parte del codice è il collo di bottiglia nell'applicazione? –

@mark, importa? la domanda è di ottenere più prestazioni, che è una buona domanda a sé stante. –

"un lungo elenco di valori": quanto è "lungo"? Quante stringhe hai nella tua lista? –

Fyi ..

Usando:

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

Controllo per i primi e gli ultimi stringhe nell'elenco poi controllo per una stringa non nella lista: "xstring" Esecuzione 500.000 iterazioni, tutti i tempi in millisecondi.

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

Interessante (se non inaspettata) risultati quando cambiamo le stringhe nella lista:

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

Con "string99" come nessun controllo.

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

per i casi A e B si presenta come test 2 e 3 hanno il vantaggio.

Tuttavia, HashSet.Contains (stringa) è molto efficiente, non viene influenzato dal contenuto dell'elenco e presenta una sintassi chiara ... potrebbe essere la scelta migliore.

Sì, è vero, non ho vita.

fonte

2010-05-21 16:07:59 Rusty

La vita o no era maledettamente buona! :) –

Entrambi i metodi che hai provato hanno prestazioni O (n) in modo che diventino più lenti man mano che aggiungi più stringhe. Se si utilizza .NET 3.5 o versione successiva, è possibile provare a utilizzare HashSet<string> anziché inizializzarlo una volta all'inizio dell'applicazione. È quindi possibile ottenere circa O (1) ricerche.

Per .NET v2.0 è possibile emulare un HashSet utilizzando un Dictionary<string, object> e utilizzare ContainsKey e non utilizzare il valore.

fonte

2010-05-20 22:31:20

Scusate ma vi sbagliate un po '. Penso che il meglio per Framework 1.x sia 'System.Collections.Hashtable'. Perché 1.x non ha generici! – abatishchev

@abatishchev: hai ragione che 1.x non ha generici. Ma credo che sia giusto presumere che le persone non stiano usando .NET 1.x in questi giorni a meno che non lo menzionino nella loro domanda. Detto questo, ho riformulato la mia risposta per renderla più chiara. –

ha appena fatto un esperimento e HashSet ha la stessa velocità dei if. –

Attualmente stai eseguendo questo codice di 200.000 volte in produzione? Si consiglia di considerare i controlli hash come un controllo negativo più veloce in caso affermativo.

Se le 200.000 volte erano solo per illustrare la differenza, allora non me ne preoccuperei. È solo un aumento di 0,02 millisecondi.

Contains è più generico del test delle stringhe statiche, quindi c'è una piccola quantità di sovraccarico. A meno che questo codice non costituisca un collo di bottiglia, come menzionato da Mark, non vale la pena di essere ottimizzato. C'è una famosa citazione in CS: "l'ottimizzazione prematura è la radice di tutto il male". La citazione non è abbastanza precisa, ma è un buon promemoria dell'ottima linea guida per l'ottimizzazione: misura prima.

fonte

2010-05-20 22:32:16

va tutto bene, ma non dovrebbe essere uno spreco quando è altrettanto facile usare un'alternativa più efficiente. e la sostituzione di string [] con HashSet è più efficiente e altrettanto concisa. In questo modo vengono scelti automaticamente i meccanismi efficienti, indipendentemente dal fatto che facciano davvero la differenza o no –

Trovo che * il codice chiaro e leggibile * sia molto più rapido rispetto a un grande lavoro di micro-ottimizzazioni che hanno un impatto ininterrottamente piccolo di runtime se utilizzato in scenari reali. –

sicuro ...ma come ho detto, se ci sono impostazioni predefinite più efficienti di una leggibilità equivalente che puoi scegliere, dovresti. il consiglio di una prematura ottimizzazione è stato dato principalmente nel contesto dei sistemi di strutturazione a favore di prestazioni che potrebbero non essere mai redditizie. Il problema è che le persone ora lo usano come scusa per non essere generalmente efficienti quando possono. la sostituzione di string [] con hashset non causa modifiche strutturali –

Potresti scoprire che Contains() funziona meglio per un elenco più lungo. Può, per esempio, ordinare l'elenco e fare una ricerca binaria (solo un esperimento mentale, per un esempio.)

fonte

2010-05-20 22:43:29 whybird

Sfortunatamente, Contains non può formulare tali presupposti. Farà sempre una ricerca lineare sugli array. – Ruben

Ecco un'alternativa che si potrebbe probabilmente trovare leggibile e mantenibile, che si potrebbe desiderare di testare per la velocità. Se lo fai testare per la velocità, per favore pubblica il tuo risultato!

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

fonte

2010-05-20 22:57:05 whybird

Per quanto posso ricordare, il compilatore C# crea automaticamente una sorta di hashtable per il blocco del caso switch se il numero di casi è maggiore di 4. – abatishchev

è necessario un 'break' dopo' DoSomething() 'per compilare . – juharr

@juharr sei corretto; risposta modificata per aggiungerla. – whybird

Sebbene l'utilizzo di un HashSet<string> come suggerito potrebbe essere una scelta migliore, il motivo per cui strValues.Contains(str) è più lento, è perché si tratta di un metodo di estensione generica. Non esiste un metodo Contiene sugli array.

Il modo in cui funziona per array è fondamentalmente

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

che aggiunge una TYPECHECK, chiamata typecast e virtuale. Quindi eseguirà l'iterazione dell'array (causando controlli sui limiti). Solo allora arriverà a fare confronti con le stringhe. Quindi sta facendo un lavoro .

Si noti che in C# 3 (che è necessario utilizzare se si sta utilizzando metodi di estensione), si può semplicemente inizializzare il HashSet<string> in questo modo:

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

questo modo il vostro programma di altrettanto leggibile come è ora usando gli array.

fonte

2010-05-20 23:56:15 Ruben

Prestazioni C# della stringa statica [] contains() (slooooow) vs. operatore ==

risposta

Problemi correlati