Desempenho do HashSet vs. List

É claro que um desempenho de pesquisa da class HashSet genérica é maior que da class List genérica. Basta comparar a chave baseada em hash com a abordagem linear na class List .

No entanto, o cálculo de uma chave hash pode levar alguns ciclos de CPU, portanto, para uma pequena quantidade de itens, a pesquisa linear pode ser uma alternativa real ao HashSet .

Minha pergunta: onde está o break-even?

Para simplificar o cenário (e para ser justo), vamos assumir que a class List usa o método Equals() do elemento para identificar um item.

Muitas pessoas estão dizendo que, quando você chega ao tamanho em que a velocidade é realmente uma preocupação, o HashSet sempre vai bater o List , mas isso depende do que você está fazendo.

Digamos que você tenha uma List que sempre tenha, em média, 5 itens nela. Em um grande número de ciclos, se um único item for adicionado ou removido em cada ciclo, talvez seja melhor usar uma List .

Eu fiz um teste para isso na minha máquina e, bem, tem que ser muito pequeno para obter uma vantagem de List . Para uma lista de strings curtas, a vantagem desapareceu após o tamanho 5, para objects após o 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 estão os dados exibidos como um gráfico:

insira a descrição da imagem aqui

Aqui está o código:

 static void Main(string[] args) { int times = 10000000; for (int listSize = 1; listSize < 10; listSize++) { List list = new List(); HashSet hashset = new HashSet(); 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 list = new List(); HashSet hashset = new HashSet(); 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(); } 

Você está olhando para isto errado. Sim, uma pesquisa linear de uma lista irá superar um HashSet para um pequeno número de itens. Mas a diferença de desempenho geralmente não importa para collections pequenas. Geralmente são as grandes collections com as quais você tem que se preocupar, e é aí que você pensa em termos de Big-O . No entanto, se você tiver medido um gargalo real no desempenho do HashSet, poderá tentar criar um List / HashSet híbrido, mas fará isso realizando muitos testes de desempenho empíricos, sem fazer perguntas sobre o SO.

É essencialmente inútil comparar duas estruturas de desempenho que se comportam de maneira diferente. Use a estrutura que transmite a intenção. Mesmo se você disser que sua List não teria duplicatas e a ordem de iteração não importa se é comparável a um HashSet , ainda é uma má escolha usar List porque é relativamente menos tolerante a falhas.

Dito isto, vou inspecionar alguns outros aspectos do desempenho,

 +------------+--------+-------------+-----------+----------+----------+-----------+ | Collection | Random | Containment | Insertion | Addition | Removal | Memory | | | access | | | | | | +------------+--------+-------------+-----------+----------+----------+-----------+ | List | O(1) | O(n) | O(n) | O(1)* | O(n) | Lesser | | HashSet | 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 since it involves cost of precomputing hash code before storing it.

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

Se usar um HashSet <> ou List <> se resume a como você precisa acessar sua coleção . Se você precisa garantir a ordem dos itens, use uma lista. Se você não fizer isso, use um HashSet. Deixe a Microsoft se preocupar com a implementação de seus algoritmos e objects de hash.

Um HashSet acessará itens sem precisar enumerar a coleção (complexidade de O (1) ou próximo a ela), e como uma lista garante a ordem, ao contrário de um HashSet, alguns itens precisarão ser enumerados (complexidade de O (n)).

Apenas pensei em conversar com alguns benchmarks para diferentes cenários para ilustrar as respostas anteriores:

  1. Algumas (12 – 20) strings pequenas (comprimento entre 5 e 10 caracteres)
  2. Muitas (~ 10K) pequenas cadeias de caracteres
  3. Algumas strings longas (comprimento entre 200 e 1000 caracteres)
  4. Muitas cordas longas (~ 5K)
  5. Alguns inteiros
  6. Muitos (~ 10K) inteiros

E para cada cenário, procurando valores que aparecem:

  1. No começo da lista (“começo”, índice 0)
  2. Perto do começo da lista (“início”, índice 1)
  3. No meio da lista (“meio”, contagem de índice / 2)
  4. Perto do final da lista (“atrasado”, índice de contagem 2)
  5. No final da lista (“fim”, índice de contagem 1)

Antes de cada cenário, gerava listas aleatórias de strings aleatórias e, depois, alimentava cada lista com um hashset. Cada cenário foi executado 10.000 vezes, essencialmente:

(pseudocódigo de teste)

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

Saída de Amostra

Testado no Windows 7, 12 GB Ram, 64 bits, 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 ponto de equilíbrio dependerá do custo de calcular o hash. Cálculos de hash podem ser triviais, ou não … 🙂 Há sempre a class System.Collections.Specialized.HybridDictionary para ajudá-lo a não se preocupar com o ponto de equilíbrio.

A resposta, como sempre, é ” depende “. Eu suponho das tags que você está falando sobre c #.

Sua melhor aposta é determinar

  1. Um dataset
  2. Requisitos de uso

e escreva alguns casos de teste.

Também depende de como você classifica a lista (se ela estiver ordenada), que tipo de comparações precisam ser feitas, quanto tempo a operação “Compare” leva para o object específico na lista, ou até mesmo como você pretende usar a lista. coleção.

Geralmente, o melhor para escolher não se baseia tanto no tamanho dos dados com os quais você está trabalhando, mas na maneira como você pretende acessá-los. Você tem cada dado associado a uma string específica ou a outros dados? Uma coleção baseada em hash seria provavelmente a melhor. A ordem dos dados que você está armazenando é importante ou você precisará acessar todos os dados ao mesmo tempo? Uma lista regular pode ser melhor então.

Adicional:

Claro, meus comentários acima assumem que ‘desempenho’ significa access a dados. Outra coisa a considerar: o que você está procurando quando diz “performance”? O valor individual de desempenho é procurado? É o gerenciamento de conjuntos de valores grandes (10000, 100000 ou mais)? É o desempenho de preencher a estrutura de dados com dados? Removendo dados? Acessando bits individuais de dados? Substituindo valores? Iterando os valores? Uso de memory? Velocidade de cópia de dados? Por exemplo, se você acessar dados por um valor de string, mas seu principal requisito de desempenho for o uso mínimo de memory, talvez haja problemas de design conflitantes.

Você pode usar um HybridDictionary que detecta automaticamente o ponto de interrupção e aceita valores nulos, tornando-o essencialmente o mesmo que um HashSet.

Depende. Se a resposta exata realmente importa, faça alguns perfis e descubra. Se você tem certeza de que nunca terá mais do que um certo número de elementos no conjunto, vá com uma lista. Se o número for ilimitado, use um HashSet.

Depende do que você está fazendo. Se suas chaves forem inteiras, você provavelmente não precisará de muitos itens antes que o HashSet seja mais rápido. Se você estiver digitando em uma string, ela será mais lenta e depende da string de input.

Certamente você poderia fazer um benchmark com facilidade?

Um fator que você não leva em conta é a robustez da function GetHashcode (). Com uma function de hash perfeita, o HashSet terá, claramente, um melhor desempenho de pesquisa. Mas, como a function hash diminui, o tempo de pesquisa do HashSet também.

Depende de muitos fatores … Implementação de listas, arquitetura de CPU, JVM, semântica de loop, complexidade do método equals, etc … No momento em que a lista fica grande o suficiente para efetivamente benchmark (mais de 1000 elementos), binário baseado em Hash as pesquisas superam as pesquisas lineares, e a diferença só aumenta a partir daí.

Espero que isto ajude!