Comparación rápida de cadenas con la lista

Question

Necesito un método rápido para determinar si una cadena dada se encuentra en una lista de cadenas.

La lista de cadenas no se conoce hasta el tiempo de ejecución, pero a partir de entonces no cambiará.

yo podría simplemente tener un List<String> llamados strings y luego hacer:

if (strings.Contains(item)) 

Sin embargo, esto no rinden adecuadamente si hay muchas cadenas de la lista.

También podría utilizar un HashSet<String>, pero para ello sería necesario llamar GetHashCode en cada cuerda entrante, así como Equals, lo que sería un desperdicio si hay, por ejemplo, solo 3 cadenas en la lista. ¿Mencioné que esto debe ser rápido?

que pude en la configuración y decide utilizar un List o una HashSet dependiendo del número de cadenas (por ejemplo, el uso de lista por menos de 10 cuerdas, HashSet de otra manera), algo así como la lógica en HybridDictionary.

Como las cadenas son unicode, una estructura Trie estándar no funcionará, aunque un árbol Radix/Patricia trie podría. ¿Hay alguna buena implementación de C# con benchmarks?

Algunos han mencionado pasar por alto String 's GetHashCode y utilizando una función hash de más rápido rendimiento. ¿Hay puntos de referencia por ahí?

El uso de expresiones LINQ para crear esencialmente una declaración de conmutación optimizada es un enfoque novedoso que se ve muy interesante.

¿Qué más podría funcionar? El costo de instalación no es importante, solo la velocidad de búsqueda.

Si es importante, los valores de las cadenas entrantes raramente aparecerán en la lista.

Answer 1

Consultar estas:

Jomo Fisher - Fast Switching with LINQ

Gustavo Guerra - StaticStringDictionary - Fast Switching with LINQ revisited

Answer 2

Puede usar un trie para contener la lista de cadenas; los intentos fueron diseñados para re rápido trie val. Aquí está one example de implementar un trie en C#.

actualización: Powerpoint presentation on folded tries for Unicode y Ifo on implementation of a folded trie for Unicode (not C#)

Answer 3

¿Usted ha considerado el uso de la clase HashSet (en .NET 3) en su lugar?

Answer 4

Re su "cuando la lista es pequeña" preocupación; si no te importa usar colecciones no genéricas, System.Collections.Specialized.HybridDictionary hace algo como esto; encapsula un System.Collections.Specialized.ListDictionary cuando es pequeño, o un System.Collections.Hashtable cuando se vuelve más grande (>10). ¿Digno de una mirada?

---

De lo contrario; quizás podría usar HashSet<T> con un comparador personalizado?A continuación, puede elegir qué tan caro es 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

Quizás el HybridDictionary es una mejor opción aquí. Su uso interno depende de cuántos elementos hay en la colección.

Answer 6

Como nota adicional, si la memoria sirve, cuando se construye una Cadena, su HashValue se precalcula y se almacena con la Cadena como una optimización para este tipo de caso de uso. Si está usando una matriz de caracteres o StringBuilder, obviamente esto no se aplica, pero para una cadena inmutable debería.

EDIT: No soy correcto ... Java almacena en caché el HashCode de una cadena, C# no.

Answer 7

que terminé haciendo esto:

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

    return contains; 
} 

supongo que podría crear un método de extensión para List<string>, pero esto era suficiente para mis necesidades.

Answer 8

Puede utilizar la interna de cuerdas para hacer esto muy rápidamente. Al compilar la lista, debe almacenar el formato interno de la cadena requerida (el resultado es string.Intern()). Luego, debe comparar con una cadena interna con object.ReferenceEquals, ya que las cadenas internas tienen la misma referencia.

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

Esto dará como resultado una comparación de cuatro bytes para cada lista, y una pasada sobre la cadena original. El grupo interno de cadenas está diseñado específicamente para la comparación rápida de cadenas y para encontrar si ya existe una, por lo que la operación interna debería ser bastante rápida.