Rendimiento de HashSet frente a lista
Está claro que el rendimiento de búsqueda de la HashSet<T>clase genérica es mayor que el de la List<T>clase genérica. Simplemente compare la clave basada en hash con el enfoque lineal en elList<T> clase.
Sin embargo, calcular 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 a laHashSet<T> .
Mi pregunta: ¿dónde está el punto de equilibrio?
Para simplificar el escenario (y para ser justos), supongamos que la List<T>clase usa el método del elemento Equals()para identificar un elemento.
Mucha gente dice que una vez que llegas al tamaño en el que la velocidad es en realidad una preocupación, HashSet<T>siempre superarás List<T>, pero eso depende de lo que estés haciendo.
Digamos que tiene un archivo List<T>que solo tendrá un promedio de 5 elementos. Durante una gran cantidad de ciclos, si se agrega o elimina un solo elemento en cada ciclo, es mejor que utilices un archivo List<T>.
Hice una prueba para esto en mi máquina y, bueno, tiene que ser muy pequeño para aprovecharlo List<T>. Para una lista de cadenas cortas, la ventaja desapareció después del tamaño 5, para 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í se muestran los datos en forma de 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();
}
Básicamente, no tiene sentido comparar el rendimiento de dos estructuras que se comportan de manera diferente. Utilice la estructura que transmita la intención. Incluso si dice que List<T>no tendría duplicados y que el orden de iteración no importa, lo que lo hace comparable a a HashSet<T>, sigue siendo una mala elección List<T>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** |
+------------+--------+-------------+-----------+----------+----------+-----------+
* Aunque la suma es O(1) en ambos casos, será relativamente más lenta en HashSet ya que implica el costo de precalcular el código hash antes de almacenarlo.
** La escalabilidad superior de HashSet tiene un costo de memoria. Cada entrada se almacena como un nuevo objeto junto con su código hash. Este artículo podría darte una idea.
Estás viendo 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 normalmente no importa para colecciones tan pequeñas. Generalmente 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, entonces puede intentar crear una Lista/HashSet híbrido, pero lo hará realizando muchas pruebas de rendimiento empíricas, sin hacer preguntas sobre SO.
El uso de HashSet<> o List<> depende de cómo necesita acceder a su colección . Si necesita garantizar el orden de los artículos, utilice una Lista. Si no lo hace, utilice un HashSet. Deje que Microsoft se preocupe por la implementación de sus objetos y algoritmos hash.
Un HashSet accederá a 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 enumerarse (complejidad de O(n)).
