Mejor colección para búsqueda rápida de cadenas

Question

Necesito una lista de cadenas y una forma de determinar rápidamente si una cadena está contenida dentro de esa lista.

Para mejorar la velocidad de búsqueda, consideré SortedList y Dictionary; sin embargo, ambos funcionan con KeyValuePair s cuando todo lo que necesito es un solo string.

Sé que podría usar un KeyValuePair y simplemente ignorar la parte Value. Pero prefiero ser eficiente y me pregunto si hay una colección que se adapte mejor a mis requisitos.

Answer 1

Si tiene .NET 3.5 o superior, use HashSet<String>.

En su defecto, un Dictionary<string, byte> (o cualquier tipo que desee para el parámetro TValue tipo) sería más rápido que un SortedList si usted tiene una gran cantidad de entradas - este último utilizará una búsqueda binaria, por lo que será O (log n) búsqueda, en lugar de O (1).

Answer 2

Si lo que desea saber si una cadena está en el uso conjunto HashSet<string>

Answer 3

HashSet<string> es como un Dictionary, pero solo con llave.

Answer 4

Si desea crear su propia estructura de datos, use un Trie. http://en.wikipedia.org/wiki/Trie

peor de los casos es si la cadena está presente: O (longitud de cadena)

Answer 5

Esto suena como un trabajo para

var keys = new HashSet<string>(); 

por MSDN: La función Contiene tiene O (1) complejidad.

Pero debe tener en cuenta que no da error para los duplicados al agregar.

Answer 6

Sé que esta respuesta es un poco tarde para esta fiesta, pero me encontré con un problema en el que nuestros sistemas funcionaban con lentitud. Después del perfilado descubrimos que había MUCHAS búsquedas de cadenas sucediendo con la estructura de nuestras estructuras de datos.

Así que hicimos un poco de investigación, came across these benchmarks, hicimos nuestras propias pruebas, y ahora pasamos a utilizar SortedList.

if (sortedlist.ContainsKey(thekey)) 
{ 
//found it. 
} 

pesar de que un diccionario demostró ser más rápido, era menos código que teníamos que refactorizar, y el aumento de rendimiento era lo suficientemente bueno para nosotros.

De todos modos, quería compartir el sitio web en caso de que otras personas tengan problemas similares. Hacen comparaciones entre estructuras de datos donde la cadena que está buscando es una "clave" (como HashTable, Dictionary, etc.) o en un "valor" (Lista, Matriz, o en un Diccionario, etc.) que es donde están las nuestras almacenado

Answer 7

Sé que la pregunta es vieja como el infierno, pero tuve que resolver el mismo problema, solo para un conjunto muy pequeño de cadenas (entre 2 y 4).

En mi caso, en realidad utilicé la búsqueda manual en una serie de cadenas que resultó ser mucho más rápido que HashSet<string> (Lo evalué como punto de referencia).

for (int i = 0; i < this.propertiesToIgnore.Length; i++) 
{ 
    if (this.propertiesToIgnore[i].Equals(propertyName)) 
    { 
     return true; 
    } 
} 

¡Tenga en cuenta que es mejor que el conjunto de hash solo para arreglos pequeños!

EDIT: sólo funciona con un bucle manual de for, no use LINQ, detalles en los comentarios