Es HashSet contenedor más rápida para buscar en?

Question

Tengo que comprobar que contiene cadena específica 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 ella - para sostener una serie de cadenas y cheque no es en otra o que 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? Seguro. Pero esa no es la pregunta que hizo. En que pidió la más rápida posible de búsqueda.

Es el más rápido posible? No, por supuesto que no, no por cualquier medida.

En primer lugar, con el fin de hablar de "más rápido" tenemos que describir con precisión lo que significa "rápido". ¿Se refiere a:

• menor peor caso posible Tiempo
• menor medio Tiempo promedio durante muchos tiempos
• más pequeño temporización media da un patrón de uso particular,
• algo

? Por favor, aclarar con precisión qué significa "más rápida posible". Podemos diseñar un algoritmo que es el en la teoría más rápida posible sólo si sabemos precisamente lo que más rápida posible significa para usted.

Por ejemplo, supongamos que usted está escribiendo un compilador. Algo que tenemos que hacer todo el tiempo en los compiladores es comprobar si una cadena particular está en una lista de cadenas. Tal vez estamos comprobando para ver si una cadena es una palabra clave, por lo que tenemos que mirar hacia arriba si una cadena dada está dentro del conjunto { "int", "doble", "para", "foreach", "clase" ... }

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

Tenga en cuenta que esto requiere el análisis estático; aunque se desempeña bien en los casos típicos, no da buenos resultados en los raros casos en los que hay un montón de palabras clave utilizadas raras. Otro enfoque que podríamos tener sería escribir un autoajuste tabla hash que dinámicamente identificada cuando las cadenas particulares estaban siendo buscado 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 "barra" cadena dentro 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" ha sido utilizado, por lo que de forma dinámica pellizca la estructura de la tabla de hash de modo que el segunda 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); }

debido a que 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 como está."

Afortunadamente para nosotros, no estábamos, al igual que, en busca de la más rápida posible de búsqueda. Sólo estuvimos buscando para un razonablemente rápido de búsqueda.

Puede describir cuidadosamente y completamente qué es exactamente lo que su uso es para el caso de más rápida posible de búsqueda ? Hay un montón de algoritmos que se pueden utilizar para acelerar las búsquedas, pero se ponen muy complicado.