Rendimiento de HashSet vs. List
https://stackoverflow.com/questions/150750
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Está claro que el rendimiento de búsqueda de la clase genérica HashSet<T> es mayor que el de la clase genérica List<T>. Simplemente compare la clave basada en hash con el enfoque lineal en la clase Equals().
Sin embargo, calcular una clave hash puede tomar algunos ciclos de CPU, por lo que para una pequeña cantidad de elementos, la búsqueda lineal puede ser una alternativa real a la <=>.
Mi pregunta: ¿dónde está el equilibrio?
Para simplificar el escenario (y para ser justos) supongamos que la clase <=> usa el método <=> del elemento para identificar un elemento.
Solución
Mucha gente dice que una vez que se llega al tamaño en que la velocidad es realmente una preocupación, HashSet<T> siempre vencerá a List<T>, pero eso depende de lo que esté haciendo.
Digamos que tiene un <=> que solo tendrá un promedio de 5 elementos. Durante un gran número de ciclos, si se agrega o elimina un solo elemento en cada ciclo, es mejor que use un <=>.
Hice una prueba para esto en mi máquina y, bueno, tiene que ser muy muy pequeño para obtener una ventaja de <=>. Para una lista de cadenas cortas, la ventaja se fue después del tamaño 5, para los objetos después del tamaño 20.
1 item LIST strs time: 617ms
1 item HASHSET strs time: 1332ms
2 item LIST strs time: 781ms
2 item HASHSET strs time: 1354ms
3 item LIST strs time: 950ms
3 item HASHSET strs time: 1405ms
4 item LIST strs time: 1126ms
4 item HASHSET strs time: 1441ms
5 item LIST strs time: 1370ms
5 item HASHSET strs time: 1452ms
6 item LIST strs time: 1481ms
6 item HASHSET strs time: 1418ms
7 item LIST strs time: 1581ms
7 item HASHSET strs time: 1464ms
8 item LIST strs time: 1726ms
8 item HASHSET strs time: 1398ms
9 item LIST strs time: 1901ms
9 item HASHSET strs time: 1433ms
1 item LIST objs time: 614ms
1 item HASHSET objs time: 1993ms
4 item LIST objs time: 837ms
4 item HASHSET objs time: 1914ms
7 item LIST objs time: 1070ms
7 item HASHSET objs time: 1900ms
10 item LIST objs time: 1267ms
10 item HASHSET objs time: 1904ms
13 item LIST objs time: 1494ms
13 item HASHSET objs time: 1893ms
16 item LIST objs time: 1695ms
16 item HASHSET objs time: 1879ms
19 item LIST objs time: 1902ms
19 item HASHSET objs time: 1950ms
22 item LIST objs time: 2136ms
22 item HASHSET objs time: 1893ms
25 item LIST objs time: 2357ms
25 item HASHSET objs time: 1826ms
28 item LIST objs time: 2555ms
28 item HASHSET objs time: 1865ms
31 item LIST objs time: 2755ms
31 item HASHSET objs time: 1963ms
34 item LIST objs time: 3025ms
34 item HASHSET objs time: 1874ms
37 item LIST objs time: 3195ms
37 item HASHSET objs time: 1958ms
40 item LIST objs time: 3401ms
40 item HASHSET objs time: 1855ms
43 item LIST objs time: 3618ms
43 item HASHSET objs time: 1869ms
46 item LIST objs time: 3883ms
46 item HASHSET objs time: 2046ms
49 item LIST objs time: 4218ms
49 item HASHSET objs time: 1873ms
Aquí están los datos que se muestran como un gráfico:
Aquí está el código:
static void Main(string[] args)
{
int times = 10000000;
for (int listSize = 1; listSize < 10; listSize++)
{
List<string> list = new List<string>();
HashSet<string> hashset = new HashSet<string>();
for (int i = 0; i < listSize; i++)
{
list.Add("string" + i.ToString());
hashset.Add("string" + i.ToString());
}
Stopwatch timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
list.Remove("string0");
list.Add("string0");
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item LIST strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
hashset.Remove("string0");
hashset.Add("string0");
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item HASHSET strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
Console.WriteLine();
}
for (int listSize = 1; listSize < 50; listSize+=3)
{
List<object> list = new List<object>();
HashSet<object> hashset = new HashSet<object>();
for (int i = 0; i < listSize; i++)
{
list.Add(new object());
hashset.Add(new object());
}
object objToAddRem = list[0];
Stopwatch timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
list.Remove(objToAddRem);
list.Add(objToAddRem);
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item LIST objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
hashset.Remove(objToAddRem);
hashset.Add(objToAddRem);
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item HASHSET objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
Console.WriteLine();
}
Console.ReadLine();
}
Otros consejos
Estás mirando esto mal. Sí, una búsqueda lineal de una Lista superará a un HashSet para una pequeña cantidad de elementos. Pero la diferencia de rendimiento generalmente no importa para colecciones tan pequeñas. En general, es de las grandes colecciones de las que tiene que preocuparse, y ahí es donde piensa en términos de Big-O . Sin embargo, si ha medido un cuello de botella real en el rendimiento de HashSet, puede intentar crear un List / HashSet híbrido, pero lo hará realizando muchas pruebas de rendimiento empíricas, sin hacer preguntas sobre SO.
Es esencialmente inútil comparar dos estructuras para rendimiento que se comportan de manera diferente. Use la estructura que transmite la intención. Incluso si dice que su List<T> no tendría duplicados y el orden de iteración no importa por lo que es comparable a un HashSet<T>, sigue siendo una mala elección para usar * 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. porque es relativamente menos tolerante a fallas.
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** |
+------------+--------+-------------+-----------+----------+----------+-----------+
** 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. <=>
Si se debe usar un HashSet < > o 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 hace, use un HashSet. Deje que Microsoft se preocupe por la implementación de sus algoritmos y objetos de hash.
Un HashSet accederá a los elementos sin tener que enumerar la colección (complejidad de O (1) o cerca de él), y debido a que una Lista garantiza el orden, a diferencia de un HashSet, algunos elementos deberán enumerarse (complejidad de O (n)).
Solo pensé en intervenir con algunos puntos de referencia para diferentes escenarios para ilustrar las respuestas anteriores:
- Algunas (12-20) cadenas pequeñas (longitud entre 5 y 10 caracteres)
- Muchas (~ 10K) cadenas pequeñas
- Algunas cadenas largas (longitud entre 200 y 1000 caracteres)
- Muchas (~ 5K) cadenas largas
- Algunos enteros
- Muchos (~ 10K) enteros
Y para cada escenario, buscar valores que aparecen:
- Al comienzo de la lista (" start " ;, index 0)
- Cerca del comienzo de la lista (" early " ;, index 1)
- En el medio de la lista (" middle " ;, index count / 2)
- Cerca del final de la lista (" late " ;, index count-2)
- Al final de la lista (" end " ;, index count-1)
Antes de cada escenario, generaba listas de cadenas aleatorias de tamaño aleatorio, y luego alimentaba cada lista a un hashset. Cada escenario se ejecutó 10,000 veces, esencialmente:
(pseudocódigo de prueba)
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, 12 GB de RAM, 64 bits, 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 de hash pueden ser triviales o no ... :-) Siempre existe la clase System.Collections.Specialized.HybridDictionary para ayudarlo a no tener que preocuparse por el punto de equilibrio.
La respuesta, como siempre, es " Depende " ;. Asumo por las etiquetas de las que está hablando C #.
Su mejor apuesta es determinar
- Un conjunto de datos
- Requisitos de uso
y escriba algunos casos de prueba.
También depende de cómo ordena la lista (si está ordenada), qué tipo de comparaciones deben hacerse, cuánto tiempo " Compare " la operación toma para el objeto particular en la lista, o incluso cómo piensa usar la 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 tiene la intención de acceder a ellos. ¿Tiene cada pieza de datos asociada con una cadena 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, mis comentarios anteriores asumen que 'rendimiento' significa acceso a datos. Algo más a considerar: ¿qué buscas cuando dices & Quot; performance & Quot ;? ¿Se busca el valor individual del rendimiento? ¿Es gestión de grandes conjuntos de valores (10000, 100000 o más)? ¿Es el rendimiento de llenar la estructura de datos con datos? ¿Eliminar datos? ¿Acceso a bits de datos individuales? ¿Reemplazar valores? Iterando sobre los valores? ¿Uso de memoria? Velocidad de copia de datos? Por ejemplo, si accede a los datos por un valor de cadena, pero su principal requisito de rendimiento es un 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 nulos, lo que lo hace esencialmente igual que un HashSet.
Depende. Si la respuesta exacta realmente importa, haga un perfil y averígüelo. 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 no tiene límites, use un HashSet.
Depende de lo que estés haciendo. Si sus claves son enteras, probablemente no necesite muchos elementos antes de que HashSet sea más rápido. Si lo está escribiendo en una cadena, será más lento y dependerá de la cadena de entrada.
¿Seguramente podrías preparar un punto de referencia con bastante facilidad?
Un factor que no tiene en cuenta es la solidez 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 disminuye la función hash, también lo hará el tiempo de búsqueda de HashSet.
Depende de muchos factores ... Implementación de la lista, arquitectura de la CPU, JVM, semántica de bucle, complejidad del método igual, etc. Para cuando la lista se vuelva lo suficientemente grande como para comparar de manera efectiva (más de 1000 elementos), Hash las búsquedas binarias basadas en datos superan las búsquedas lineales, y la diferencia solo aumenta a partir de ahí.
¡Espero que esto ayude!
