Confronto stringa veloce con lista

Question

Ho bisogno di un metodo veloce per determinare se una determinata stringa è in una lista di stringhe.

L'elenco di stringhe non è noto fino al runtime, ma da quel momento in poi non cambierà.

potrebbe semplicemente avere un List<String> chiamato strings e poi fare:

if (strings.Contains(item)) 

Tuttavia questo si esibirà male se ci sono molte stringhe nella lista.

Potrei anche usare un HashSet<String>, ma questo richiederebbe chiamare GetHashCode su ogni stringa in entrata e Equals, che sarebbe uno spreco se ci sono, ad es. solo 3 stringhe nella lista. Ho detto che questo deve essere veloce?

quando ho potuto impostazione, decidere di utilizzare un List o una HashSet a seconda del numero di stringhe (per esempio uso Elenco per meno di 10 corde, HashSet altrimenti), piuttosto come la logica in HybridDictionary.

Poiché le stringhe sono unicode, una struttura Trie standard non funzionerà, anche se potrebbe esistere un albero Radix/trie Patricia. Ci sono delle buone implementazioni in C# con benchmark?

Alcuni hanno menzionato l'esclusione di GetHashCodeString e l'utilizzo di una funzione di hash più veloce. Ci sono dei punti di riferimento là fuori?

L'utilizzo di espressioni LINQ per creare essenzialmente una dichiarazione switch ottimizzata è un nuovo approccio che sembra molto interessante.

Cos'altro potrebbe funzionare? Il costo di installazione non è importante, solo la velocità di ricerca.

Se è importante, i valori di stringa in entrata appariranno raramente nell'elenco.

Answer 1

prova anche questi:

Jomo Fisher - Fast Switching with LINQ

Gustavo Guerra - StaticStringDictionary - Fast Switching with LINQ revisited

Answer 2

È possibile utilizzare uno trie per contenere l'elenco di stringhe; i tentativi sono stati progettati per il re veloce trie val. Ecco one example di implementare un trie in C#.

Aggiornamento: Powerpoint presentation on folded tries for Unicode e Ifo on implementation of a folded trie for Unicode (not C#)

Answer 3

Hai pensato di usare la classe HashSet (in .NET 3), invece?

Answer 4

Re il suo "Quando la lista è piccola" preoccupazione; se non ti dispiace usare collezioni non generiche, System.Collections.Specialized.HybridDictionary fa qualcosa del genere; incapsula un System.Collections.Specialized.ListDictionary quando è piccolo, oppure un System.Collections.Hashtable quando diventa più grande (>10). Vale la pena dare un'occhiata?

---

Altrimenti; potresti forse usare con un comparatore personalizzato?Poi si può scegliere quanto costoso GetHashCode() è ...

using System; 
using System.Collections.Generic; 

class CustomStringComparer : IEqualityComparer<string> { 
    public bool Equals(string x, string y) { 
     return string.Equals(x, y); 
    } 
    public int GetHashCode(string s) { 
     return string.IsNullOrEmpty(s) ? 0 : 
      s.Length + 273133 * (int)s[0]; 
    } 
    private CustomStringComparer() { } 
    public static readonly CustomStringComparer Default 
     = new CustomStringComparer(); 
} 
static class Program { 
    static void Main() { 
     HashSet<string> set = new HashSet<string>(
      new string[] { "abc", "def", "ghi" }, CustomStringComparer.Default); 
     Console.WriteLine(set.Contains("abc")); 
     Console.WriteLine(set.Contains("abcde")); 
    } 
} 

Answer 5

Forse il HybridDictionary è una scelta migliore qui. Il suo uso interno dipende da quanti elementi sono presenti nella collezione.

Answer 6

Per inciso, se la memoria serve, quando viene costruita una stringa, il suo HashValue viene precalcolato e memorizzato con la stringa come ottimizzazione per questo tipo di caso d'uso. Se stai usando un array di caratteri o StringBuilder, questo ovviamente non si applica, ma per una stringa immutabile dovrebbe.

MODIFICA: non sono corretto ... Java memorizza nella cache un HashCode di una stringa, C# no.

Answer 7

ho finito per fare questo:

private static bool Contains(List<string> list, string value) 
{ 
    bool contains = null != list.Find(str => str.ToLower().Equals(value.ToLower())); 

    return contains; 
} 

Sto indovinando si potrebbe creare un metodo di estensione per List<string>, ma questo era sufficiente per le mie esigenze.

Answer 8

È possibile utilizzare internamento stringa per eseguire questa operazione molto rapidamente. Quando si crea l'elenco, è necessario memorizzare il formato interno della stringa richiesta (il risultato di string.Intern()). Quindi, è necessario confrontare una stringa internata con object.ReferenceEquals - poiché le stringhe internate hanno lo stesso riferimento.

List<string> BuildList() { 
    List<string> result; 
    foreach (string str from StringSource()) 
     result.Add(str.Intern()); 
    return result; 
} 

bool CheckList(List<string> list, string stringToFind) { // list must be interned for this to work! 
    return list.Find(str => object.ReferenceEquals(str, stringToFind)) != null; 
} 

Ciò comporterà un confronto quattro byte per ciascuna lista, e uno passaggio sulla stringa originale. Il pool interno di stringhe è stato creato appositamente per il confronto rapido delle stringhe e per trovare se ne esiste già uno, quindi l'operazione interna dovrebbe essere abbastanza veloce.