HashSet vs rendimiento de la Lista de

Estás viendo esto mal. Sí una búsqueda lineal de una Lista vencerá a un HashSet para un pequeño número de elementos. Pero la diferencia de rendimiento generalmente no importa para colecciones tan pequeñas. Generalmente es de las grandes colecciones de las que tienes que preocuparte, y ahí es donde piensas en términos de Big-O. Sin embargo, si has medido un cuello de botella real en el rendimiento del HashSet, entonces puedes intentar crear una Lista híbrida / HashSet, pero lo harás llevando a cabo un montón de rendimiento empírico pruebas-no hacer preguntas sobre TAN.

Si usar un HashSet o una lista se reduce a cómo necesita acceder a su colección. Si necesita garantizar el orden de los artículos, use una Lista. Si no lo haces, usa un HashSet. Deje que Microsoft se preocupe por la implementación de sus algoritmos de hash y objetos.

Un HashSet accederá a los elementos sin tener que enumerar la colección (complejidad de O (1) o cerca de ella), y debido a que una Lista garantiza el orden, a diferencia de un HashSet, algunos elementos tendrán que ser enumerados (complejidad de O(n)).

Es esencialmente inútil comparar dos estructuras para el rendimiento que se comportan de manera diferente. Utilice la estructura que transmite la intención. Incluso si dices que tu List<T> no tendría duplicados y el orden de iteración no importa haciéndolo comparable a un HashSet<T>, sigue siendo una mala elección usar List<T> porque es relativamente menos tolerante a fallos.

Dicho esto, inspeccionaré algunos otros aspectos del rendimiento,

+------------+--------+-------------+-----------+----------+----------+-----------+
| Collection | Random | Containment | Insertion | Addition |  Removal | Memory    |
|            | access |             |           |          |          |           |
+------------+--------+-------------+-----------+----------+----------+-----------+
| List<T>    | O(1)   | O(n)        | O(n)      | O(1)*    | O(n)     | Lesser    |
| HashSet<T> | O(n)   | O(1)        | n/a       | O(1)     | O(1)     | Greater** |
+------------+--------+-------------+-----------+----------+----------+-----------+

* Even though addition is O(1) in both cases, it will be relatively slower in HashSet<T> since it involves cost of precomputing hash code before storing it.

** The superior scalability of HashSet<T> has a memory cost. Every entry is stored as a new object along with its hash code. This article might give you an idea.

Solo pensé que podría mencionar algunos puntos de referencia para diferentes escenarios para ilustrar las respuestas anteriores:

1. Unas pocas (12 - 20) cadenas pequeñas (longitud entre 5 y 10 caracteres)
2. Muchas (~10K) cuerdas pequeñas
3. Algunas cadenas largas (longitud entre 200 y 1000 caracteres)
4. Muchas cadenas (~5K) largas
5. Unos cuantos enteros
6. Muchos (~10K) enteros

Y para cada escenario, buscar los valores que aparecen:

1. En el inicio de la lista ("inicio", índice 0)
2. Cerca del comienzo de la lista ("temprano", índice 1)
3. En el centro de la lista ("middle", index count/2)
4. Cerca del final de la lista ("late", index count-2)
5. Al final de la lista ("end", index count-1)

Antes de cada escenario generé listas de tamaño aleatorio de cadenas aleatorias, y luego alimenté cada lista a un hashset. Cada escenario se ejecutó 10.000 veces, esencialmente:

(ensayo pseudocódigo)

stopwatch.start
for X times
    exists = list.Contains(lookup);
stopwatch.stop

stopwatch.start
for X times
    exists = hashset.Contains(lookup);
stopwatch.stop

Salida de muestra

Probado en Windows 7, 12GB Ram, 64 bit, Xeon 2.8 GHz

---------- Testing few small strings ------------
Sample items: (16 total)
vgnwaloqf diwfpxbv tdcdc grfch icsjwk
...

Benchmarks:
1: hashset: late -- 100.00 % -- [Elapsed: 0.0018398 sec]
2: hashset: middle -- 104.19 % -- [Elapsed: 0.0019169 sec]
3: hashset: end -- 108.21 % -- [Elapsed: 0.0019908 sec]
4: list: early -- 144.62 % -- [Elapsed: 0.0026607 sec]
5: hashset: start -- 174.32 % -- [Elapsed: 0.0032071 sec]
6: list: middle -- 187.72 % -- [Elapsed: 0.0034536 sec]
7: list: late -- 192.66 % -- [Elapsed: 0.0035446 sec]
8: list: end -- 215.42 % -- [Elapsed: 0.0039633 sec]
9: hashset: early -- 217.95 % -- [Elapsed: 0.0040098 sec]
10: list: start -- 576.55 % -- [Elapsed: 0.0106073 sec]


---------- Testing many small strings ------------
Sample items: (10346 total)
dmnowa yshtrxorj vthjk okrxegip vwpoltck
...

Benchmarks:
1: hashset: end -- 100.00 % -- [Elapsed: 0.0017443 sec]
2: hashset: late -- 102.91 % -- [Elapsed: 0.0017951 sec]
3: hashset: middle -- 106.23 % -- [Elapsed: 0.0018529 sec]
4: list: early -- 107.49 % -- [Elapsed: 0.0018749 sec]
5: list: start -- 126.23 % -- [Elapsed: 0.0022018 sec]
6: hashset: early -- 134.11 % -- [Elapsed: 0.0023393 sec]
7: hashset: start -- 372.09 % -- [Elapsed: 0.0064903 sec]
8: list: middle -- 48,593.79 % -- [Elapsed: 0.8476214 sec]
9: list: end -- 99,020.73 % -- [Elapsed: 1.7272186 sec]
10: list: late -- 99,089.36 % -- [Elapsed: 1.7284155 sec]


---------- Testing few long strings ------------
Sample items: (19 total)
hidfymjyjtffcjmlcaoivbylakmqgoiowbgxpyhnrreodxyleehkhsofjqenyrrtlphbcnvdrbqdvji...
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0018266 sec]
2: list: start -- 115.76 % -- [Elapsed: 0.0021144 sec]
3: list: middle -- 143.44 % -- [Elapsed: 0.0026201 sec]
4: list: late -- 190.05 % -- [Elapsed: 0.0034715 sec]
5: list: end -- 193.78 % -- [Elapsed: 0.0035395 sec]
6: hashset: early -- 215.00 % -- [Elapsed: 0.0039271 sec]
7: hashset: end -- 248.47 % -- [Elapsed: 0.0045386 sec]
8: hashset: start -- 298.04 % -- [Elapsed: 0.005444 sec]
9: hashset: middle -- 325.63 % -- [Elapsed: 0.005948 sec]
10: hashset: late -- 431.62 % -- [Elapsed: 0.0078839 sec]


---------- Testing many long strings ------------
Sample items: (5000 total)
yrpjccgxjbketcpmnvyqvghhlnjblhgimybdygumtijtrwaromwrajlsjhxoselbucqualmhbmwnvnpnm
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: list: start -- 132.73 % -- [Elapsed: 0.0021517 sec]
3: hashset: start -- 231.26 % -- [Elapsed: 0.003749 sec]
4: hashset: end -- 368.74 % -- [Elapsed: 0.0059776 sec]
5: hashset: middle -- 385.50 % -- [Elapsed: 0.0062493 sec]
6: hashset: late -- 406.23 % -- [Elapsed: 0.0065854 sec]
7: hashset: early -- 421.34 % -- [Elapsed: 0.0068304 sec]
8: list: middle -- 18,619.12 % -- [Elapsed: 0.3018345 sec]
9: list: end -- 40,942.82 % -- [Elapsed: 0.663724 sec]
10: list: late -- 41,188.19 % -- [Elapsed: 0.6677017 sec]


---------- Testing few ints ------------
Sample items: (16 total)
7266092 60668895 159021363 216428460 28007724
...

Benchmarks:
1: hashset: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: hashset: end -- 100.45 % -- [Elapsed: 0.0016284 sec]
3: list: early -- 101.83 % -- [Elapsed: 0.0016507 sec]
4: hashset: late -- 108.95 % -- [Elapsed: 0.0017662 sec]
5: hashset: middle -- 112.29 % -- [Elapsed: 0.0018204 sec]
6: hashset: start -- 120.33 % -- [Elapsed: 0.0019506 sec]
7: list: late -- 134.45 % -- [Elapsed: 0.0021795 sec]
8: list: start -- 136.43 % -- [Elapsed: 0.0022117 sec]
9: list: end -- 169.77 % -- [Elapsed: 0.0027522 sec]
10: list: middle -- 237.94 % -- [Elapsed: 0.0038573 sec]


---------- Testing many ints ------------
Sample items: (10357 total)
370826556 569127161 101235820 792075135 270823009
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0015132 sec]
2: hashset: end -- 101.79 % -- [Elapsed: 0.0015403 sec]
3: hashset: early -- 102.08 % -- [Elapsed: 0.0015446 sec]
4: hashset: middle -- 103.21 % -- [Elapsed: 0.0015618 sec]
5: hashset: late -- 104.26 % -- [Elapsed: 0.0015776 sec]
6: list: start -- 126.78 % -- [Elapsed: 0.0019184 sec]
7: hashset: start -- 130.91 % -- [Elapsed: 0.0019809 sec]
8: list: middle -- 16,497.89 % -- [Elapsed: 0.2496461 sec]
9: list: end -- 32,715.52 % -- [Elapsed: 0.4950512 sec]
10: list: late -- 33,698.87 % -- [Elapsed: 0.5099313 sec]

El punto de equilibrio dependerá del costo de calcular el hash. Los cálculos Hash pueden ser triviales o no... :- ) Siempre está el Sistema.Colecciones.Especializar.HybridDictionary clase para ayudarle a no tener que preocuparse por el punto de equilibrio.

La respuesta, como siempre, es "depende". Asumo por las etiquetas que estás hablando de C#.

Su mejor apuesta es determinar

1. Un conjunto de datos
2. Requisitos de uso

Y escribir algunos casos de prueba.

También depende de cómo ordene la lista (si es que está ordenada), qué tipo de comparaciones deben hacerse, cuánto tiempo tarda la operación "Comparar" para el objeto en particular de la lista, o incluso cómo pretende usar el colección.

Generalmente, el mejor para elegir no se basa tanto en el tamaño de los datos con los que está trabajando, sino más bien en cómo pretende acceder a ellos. ¿Tiene cada pieza de datos asociada con una cadena en particular u otros datos? Una colección basada en hash probablemente sería lo mejor. ¿Es importante el orden de los datos que está almacenando, o va a necesitar acceder a todos los datos al mismo tiempo? Una lista regular puede ser mejor entonces.

Adicional:

Por supuesto, mi los comentarios anteriores asumen que 'rendimiento' significa acceso a datos. Algo más a considerar: ¿qué estás buscando cuando dices "performance"? ¿Se busca el valor individual del rendimiento? ¿Es la gestión de grandes (10000, 100000 o más) conjuntos de valores? ¿Es el rendimiento de llenar la estructura de datos con datos? ¿Eliminar datos? ¿Accediendo a bits de datos individuales? ¿Reemplazando valores? Iterar sobre los valores? ¿Uso de memoria? Velocidad de copia de datos? Por ejemplo, si accede a los datos mediante un valor de cadena, pero su principal requisito de rendimiento es el uso mínimo de memoria, es posible que tenga problemas de diseño conflictivos.

Puede usar un HybridDictionary que detecta automáticamente el punto de ruptura y acepta valores null, lo que lo hace esencialmente lo mismo que un HashSet.

Depende. Si la respuesta exacta realmente importa, haz algunos perfiles y averígualo. Si está seguro de que nunca tendrá más de un cierto número de elementos en el conjunto, vaya con una lista. Si el número es ilimitado, utilice un HashSet.

Depende de lo que estés haciendo. Si sus claves son enteros, probablemente no necesite muchos elementos antes de que el HashSet sea más rápido. Si estás ingresarlo en una cadena será más lento, y depende de la cadena de entrada.

Seguramente podrías preparar un benchmark con bastante facilidad?

Un factor que no tienes en cuenta es la robustez de la función GetHashCode (). Con una función hash perfecta, el HashSet claramente tendrá un mejor rendimiento de búsqueda. Pero a medida que la función hash disminuye, también lo hará el tiempo de búsqueda del HashSet.

Depende de muchos factores... Implementación de lista, arquitectura de CPU, JVM, semántica de bucle, complejidad de igual método, etc... En el momento en que la lista se hace lo suficientemente grande como para comparar efectivamente (más de 1000 elementos), las búsquedas binarias basadas en Hash superan a las búsquedas lineales, y la diferencia solo aumenta a partir de ahí.

Espero que esto ayude!