¿Es el HashSet <T> el contenedor más rápido para buscar?

Question

Tengo que comprobar esa cadena específica contiene en el conjunto de los demás:

private bool Contains(string field) 
{ 
    return this.Fields.Contains(field); // HashSet<string> local property 
} 

¿Cuál es el mejor tipo de recipiente a utilizar si sólo una tarea de la misma - para sostener una serie de cadenas y verificación hace otra está dentro o no?

Answer 1

Sí, HashSet es perfecto para esto, ya que contiene un valor para buscar a diferencia de un diccionario que requiere una clave y un valor.

Answer 2

¿Funciona HashSet? Por supuesto. Pero esa no es la pregunta que hiciste. Usted solicitó la búsqueda más rápida posible.

¿Es el más rápido posible? No, por supuesto que no, de ninguna manera.

En primer lugar, para hablar de "más rápido", necesitamos describir con precisión qué significa "más rápido". ¿Se refiere a:

• más pequeño peor caso posible tiempo
• más pequeño promedio tiempo promedio durante muchos tiempos
• menor tiempo promedio dado un patrón de uso particular,
• algo más

? Por favor, aclaren con precisión qué significa "lo más rápido posible". Podemos idear un algoritmo que es el en teoría el más rápido posible solo si sabemos exactamente qué es lo más rápido posible significa para usted.

Por ejemplo, supongamos que está escribiendo un compilador. Algo que tenemos que hacer todo el tiempo en los compiladores es comprobar si una cadena en particular está en una lista de cadenas. Tal vez estamos verificando si una cadena es una palabra clave, por lo que debemos buscar si una cadena determinada está dentro del conjunto {"int", "double", "for", "foreach", "class" ... }

Pudimos poner esos en un conjunto de hash y obtener un rendimiento decente. Pero si quisiéramos el mejor rendimiento posible podríamos hacerlo mucho mejor. Podríamos, por ejemplo, hacer un análisis de unas mil millones de líneas de código fuente existente para descubrir qué palabras clave eran las más comunes y cuáles eran menos comunes, y luego escribir una tabla hash personalizada que optimizara (1) rechazar rápidamente las cosas que eran no palabras clave, y (2) reconocer rápidamente las palabras clave más comunes a expensas de reconocer otras palabras clave.

Tenga en cuenta que esto requiere un análisis estático; aunque funciona bien en casos típicos, tiene un rendimiento bajo en los raros casos en los que se usan muchas palabras clave raras. Otro enfoque que podríamos tomar sería escribir un autoajuste tabla hash que dinámicamente identificado cuando determinadas cadenas se buscan con frecuencia.

Considere, por ejemplo, si está escribiendo una implementación del tiempo de ejecución de JScript.Con frecuencia hay que buscar una cadena en un conjunto de cadenas:

for(i = 0; i < 10; ++i) { foo.bar(i); } 

Aquí hay que buscar la cadena "bar" en el interior del objeto identificado por "foo" diez veces. La tabla hash dentro "foo" que implementa que las operaciones de búsqueda da cuenta de la primera vez a través del bucle que "bar" se ha utilizado, por lo que de forma dinámica pellizca la estructura de la tabla de hash de modo que el segundo vez a través del bucle, la búsqueda es más rápida. Esta es la estrategia que empleamos en nuestra implementación de JScript.

Ahora, que optimiza el caso de bucles, pero hace que este caso potencialmente más lento de lo que podría ser:

for(i = 0; i < 10; ++i) { foo.bar(i); foo.blah(i); foo.abc(i); } 

porque no hacemos más análisis y la cuenta de "oye, sólo re-optimizado esta tabla hash tres veces, y ahora vamos a hacerlo todo de nuevo, tal vez deberíamos dejarlo tal como está ".

Afortunadamente para nosotros, no estábamos, como usted, buscando el búsqueda más rápida posible. Sólo estábamos buscando un razonablemente rápido de búsqueda.

¿Puede describir detallada y cuidadosamente cuál es exactamente su caso de uso para la búsqueda más rápida posible? Hay muchos algoritmos que puede usar para acelerar las búsquedas, pero se vuelven muy complicados.