net mvc framework asp .net performance collections list hash

.net - mvc - hashset vs dictionary c#



HashSet vs rendimiento de la lista (12)

Está claro que el rendimiento de búsqueda de la clase HashSet<T> genérica es superior al de la clase List<T> genérica. Simplemente compare la clave basada en hash con el enfoque lineal en la clase List<T> .

Sin embargo, el cálculo de una clave hash puede requerir algunos ciclos de CPU, por lo que para una pequeña cantidad de elementos, la búsqueda lineal puede ser una alternativa real al HashSet<T> .

Mi pregunta: ¿dónde está el punto de equilibrio?

Para simplificar el escenario (y para ser justos), supongamos que la clase List<T> utiliza el método Equals() del elemento para identificar un elemento.

Depende de lo que tengas hash. Si sus claves son números enteros, probablemente no necesite muchos elementos antes de que HashSet sea más rápido. Si lo está tecleando en una cadena, será más lento y dependerá de la cadena de entrada.

¿Seguramente podrías sacar un punto de referencia con bastante facilidad?

Depende de muchos factores ... Implementación de listas, arquitectura de CPU, JVM, semántica de bucle, complejidad del método de iguales, etc. En el momento en que la lista se haga lo suficientemente grande como para evaluar de manera efectiva (más de 1000 elementos), binario basado en hash las búsquedas superan las búsquedas lineales de manera manual, y la diferencia solo aumenta desde allí.

¡Espero que esto ayude!

Depende. Si la respuesta exacta realmente importa, haz un poco de perfil y descúbrelo. 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.

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.

Es esencialmente inútil comparar dos estructuras para el rendimiento que se comportan de manera diferente. Usa 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 es importante para que sea comparable a un HashSet<T> , todavía es una mala opción usar la List<T> porque es relativamente menos tolerante a los 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.

Estás mirando esto mal. Sí, una búsqueda lineal de una Lista vencerá a un HashSet para una pequeña cantidad de elementos. Pero la diferencia de rendimiento por lo general no importa para colecciones tan pequeñas. En general, son las grandes colecciones de las que tienes que preocuparte, y ahí es donde piensas en términos de Big-O . Sin embargo, si ha medido un cuello de botella real en el rendimiento de HashSet, puede intentar crear una Lista / HashSet híbrida, pero lo hará realizando muchas pruebas de rendimiento empíricas, no haciendo preguntas sobre el SO.

La respuesta, como siempre, es " depende ". Supongo que a partir de las etiquetas de las que estás hablando C #.

Tu mejor apuesta es determinar

  1. Un conjunto de datos
  2. Requisitos de uso

y escribe algunos casos de prueba.

También depende de cómo ordene la lista (si está ordenada), qué tipo de comparaciones se deben hacer, cuánto tiempo lleva la operación "Comparar" para el objeto en particular en la lista, o incluso cómo piensa utilizar el colección.

En general, el mejor para elegir no se basa tanto en el tamaño de los datos con los que está trabajando, sino en cómo desea 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 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 tener en cuenta: ¿qué estás buscando cuando dices "rendimiento"? ¿Se busca el valor individual del desempeño? ¿Es gestión de conjuntos de valores grandes (10000, 100000 o más)? ¿Es el rendimiento de llenar la estructura de datos con datos? ¿Eliminando datos? ¿Accediendo a bits de datos individuales? ¿Reemplazando 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 el uso mínimo de memoria, es posible que tenga problemas de diseño conflictivos.

Mucha gente dice que una vez que llegas al tamaño en el que la velocidad es realmente una preocupación, HashSet<T> siempre HashSet<T> a la List<T> , pero eso depende de lo que estés haciendo.

Digamos que tiene una List<T> que solo tendrá un promedio de 5 elementos en ella. Durante un gran número de ciclos, si se agrega o elimina un solo elemento en cada ciclo, es posible que esté mejor utilizando una List<T> .

Hice una prueba de esto en mi máquina y, bueno, tiene que ser muy pequeña para obtener una ventaja de la List<T> . Para una lista de cadenas cortas, la ventaja desapareció 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(); }

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

Si usar un HashSet <> o List <> depende de cómo necesite 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 ella), y debido a que una Lista garantiza el orden, a diferencia de un HashSet, algunos elementos deberán ser enumerados (complejidad de O (n)).

Solo pensé que iba a participar con 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. Unas pocas cadenas largas (longitud entre 200 y 1000 caracteres)
  4. Muchas (~ 5K) cuerdas largas
  5. Unos cuantos enteros
  6. Muchos enteros (~ 10K)

Y para cada escenario, buscando los valores que aparecen:

  1. Al principio de la lista ("inicio", índice 0)
  2. Cerca del comienzo de la lista ("temprano", índice 1)
  3. En la mitad de la lista ("middle", cuenta de índice / 2)
  4. Cerca del final de la lista ("tarde", índice contado-2)
  5. Al final de la lista ("final", índice cuenta-1)

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

(prueba de 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.8GHz

---------- 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]

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