desempenho HashSet vs. Lista
https://stackoverflow.com/questions/150750
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
É claro que um desempenho de pesquisa da classe HashSet<T> genérico é maior do que da classe List<T> genérico. Basta comparar a chave baseada em hash com a abordagem linear na classe List<T>.
No entanto calcular uma chave de hash pode-se tomar alguns ciclos de CPU, portanto, para uma pequena quantidade de itens a busca linear pode ser uma alternativa real ao HashSet<T>.
A minha pergunta: onde está o break-even
Para simplificar o cenário (e para ser justo) vamos supor que a classe List<T> usa o método Equals() do elemento para identificar um item.
Solução
Um monte de pessoas estão dizendo que uma vez que você chegar ao tamanho onde a velocidade é realmente uma preocupação que HashSet<T> baterá sempre List<T>, mas isso depende do que você está fazendo.
Vamos dizer que você tem um List<T> que só nunca vai ter, em média, 5 itens. Ao longo de um grande número de ciclos, se um único item é adicionado ou removido de cada ciclo, você pode muito bem ser melhor usar um List<T>.
Eu fiz um teste para este na minha máquina, e, bem, ele tem que ser muito, muito pequena para obter uma vantagem de List<T>. Para uma lista de seqüências curtas, a vantagem foi embora depois de tamanho 5, para objetos depois de tamanho 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
Aqui é que os dados apresentados como um gráfico:
Aqui está o 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();
}
Outras dicas
Você está olhando para isso errado. Sim uma pesquisa linear de uma lista irá bater um HashSet para um pequeno número de itens. Mas a diferença de desempenho geralmente não importa para coleções que pequena. É geralmente as grandes coleções que você tem que se preocupar, e é aí que você pensar em termos de Big-O . No entanto, se você tiver medido um verdadeiro gargalo no desempenho HashSet, então você pode tentar criar um híbrido List / HashSet, mas você vai fazer isso através da realização de muitos testes de desempenho empíricos -. Não fazer perguntas sobre SO
É essencialmente inútil para comparar duas estruturas para desempenho que se comportam de forma diferente. Utilizar a estrutura que transmite a intenção. Mesmo se você dizer que seu List<T> não teria duplicatas e ordem de iteração não importa tornando-se comparável a um HashSet<T>, ainda é uma má escolha para uso List<T> porque a sua relativamente menos tolerante a falhas.
Dito isso, eu vou inspecionar alguns outros aspectos do desempenho,
+------------+--------+-------------+-----------+----------+----------+-----------+
| 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.
Se usar um HashSet <> ou List <> resume a como você precisa acessar sua coleção . Se você precisa para garantir a ordem dos itens, usar uma lista. Se você não fizer isso, use um HashSet. Vamos Microsoft preocupação sobre a implementação dos seus algoritmos de hash e objetos.
Um HashSet terá acesso a itens sem ter de enumerar a coleção (complexidade do O (1) ou perto dele), e porque uma Lista garante fim, ao contrário de um HashSet, alguns itens terão de ser enumerados (complexidade de o (n)).
Apenas pensei que eu gritei com alguns pontos de referência para diferentes cenários para ilustrar as respostas anteriores:
- Alguns (12 - 20) pequenos cordões (comprimento entre 5 e 10 caracteres)
- Muitos (~ 10K) pequenas cordas
- Algumas cadeias longas (comprimento entre 200 e 1000 caracteres)
- Muitos (~ 5K) longas cadeias
- Alguns inteiros
- Muitos (~ 10K) inteiros
E para cada cenário, olhando para os valores que aparecem:
- No início da lista ( "start", índice 0)
- Perto do início da lista ( "cedo", índice 1)
- No meio da lista ( "meio", contagem de índice / 2)
- Perto do fim da lista ( "tarde", índice de contagem-2)
- No final da lista ( "end", contagem de 1 index)
Antes de cada cenário que eu gerado aleatoriamente listas de tamanho de seqüências aleatórias, e, em seguida, alimentado cada lista a um hashset. Cada cenário correu 10.000 vezes, essencialmente:
(pseudocódigo teste)
stopwatch.start
for X times
exists = list.Contains(lookup);
stopwatch.stop
stopwatch.start
for X times
exists = hashset.Contains(lookup);
stopwatch.stop
Exemplo de saída
Testado no 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]
O equilíbrio vai depender do custo de computar o hash. cálculos de hash pode ser trivial, ou não ... :-) Há sempre a classe System.Collections.Specialized.HybridDictionary para ajudar você não precisa se preocupar com o ponto de equilíbrio.
A resposta, como sempre, é " Depende ". Presumo das tags que você está falando C #.
Sua melhor aposta é para determinar
- um conjunto de dados
- Os requisitos de uso
e escrever alguns casos de teste.
Ele também depende de como você classificar a lista (se for ordenado em tudo), que tipo de comparações precisam ser feitas, quanto tempo o "Compare" operação leva em um determinado objeto na lista, ou até mesmo como você pretende para usar a coleção.
Geralmente, a melhor opção para escolher não é tanto com base no tamanho dos dados que você está trabalhando, mas sim como você pretende acessá-lo. Você tem cada pedaço de dados associados com uma corda particular, ou outros dados? Uma coleção de hash com base provavelmente seria melhor. É a ordem dos dados que você está armazenando importante, ou você vai precisar acessar todos os dados ao mesmo tempo? Uma lista regular pode ser melhor então.
adicionais:
É claro, meus comentários acima assumem meios 'performance' acesso a dados. Outra coisa a considerar: o que você está procurando quando você diz "performance"? É o desempenho valor individual olhar para cima? É o gerenciamento de grandes (10000, 100000 ou mais) conjuntos de valores? É o desempenho de encher a estrutura de dados com os dados? Remoção de dados? Acessando bits individuais de dados? Substituir valores? Iteração sobre os valores? Uso de memória? Copiar dados de velocidade? Por exemplo, se você acessar dados por um valor da cadeia, mas o seu requisito de desempenho principal é o uso de memória mínima, você pode ter conflitantes questões de design.
Você pode usar um HybridDictionary que detecta automaticamente o ponto de ruptura, e aceita valores nulos, tornando-se essencialmente o mesmo que um HashSet.
Depende. Se a resposta exata realmente importa, fazer alguma perfis e descobrir. Se você tem certeza que você nunca vai ter mais do que um certo número de elementos no conjunto, ir com uma lista. Se o número é ilimitado, usar um HashSet.
Depende do que você está hashing. Se suas chaves são inteiros você provavelmente não precisa de muitos itens antes do HashSet é mais rápido. Se você está digitando-o em uma string, então ele vai ser mais lento, e depende da seqüência de entrada.
Certamente você pode chicotear acima de um ponto de referência muito facilmente?
Um fator a sua não levando em conta é a robustez da função GetHashCode (). Com uma função hash perfeita do HashSet terá claramente melhor pesquisar desempenho. Mas, como a função hash diminui assim que irá procurar o HashSet tempo.
Depende de uma série de fatores ... implementação List, arquitetura de CPU, JVM, a semântica de alça, complexidade do método equals, etc ... No momento em que a lista se torna grande o suficiente para efetivamente referência (1000 elementos), Hash pesquisas binários baseados bater pesquisas lineares mãos para baixo, e a única diferença escalas acima de lá.
Espero que isso ajude!
