Existe alguma vantagem em usar o mapa sobre unordered_map no caso de chaves triviais?

371

Uma conversa recente sobre unordered_mapC ++ me fez perceber que eu deveria usar unordered_mapna maioria dos casos em que usei mapantes, devido à eficiência da pesquisa ( amortizado O (1) vs. O (log n) ). Na maioria das vezes eu uso um mapa, eu uso intou std::stringcomo o tipo de chave; portanto, não tenho problemas com a definição da função hash. Quanto mais eu pensava sobre isso, mais percebia que não encontrava nenhuma razão para usar um std::mapover a std::unordered_mapno caso de chaves com tipos simples - observei as interfaces e não encontrei nenhuma diferenças significativas que impactariam meu código.

Daí a pergunta: existe alguma razão real para usar std::mapmais std::unordered_mapno caso de tipos simples, como inte std::string?

Estou perguntando do ponto de vista estritamente de programação - sei que não é totalmente considerado padrão e que pode causar problemas com a portabilidade.

Além disso, espero que uma das respostas corretas possa ser "é mais eficiente para conjuntos menores de dados" devido a uma sobrecarga menor (isso é verdade?) - portanto, gostaria de restringir a pergunta a casos em que a quantidade de chaves não é trivial (> 1 024).

Edit: duh, esqueci o óbvio (obrigado GMan!) - sim, os mapas estão ordenados, é claro - eu sei disso e estou procurando por outros motivos.

Kornel Kisielewicz
fonte
22
Eu gosto de fazer esta pergunta em entrevistas: "Quando a classificação rápida é melhor que a classificação por bolhas?" A resposta para a pergunta fornece informações sobre a aplicação prática da teoria da complexidade e não apenas declarações simples em preto e branco, como O (1) é melhor que O (n) ou O (k) é equivalente a O (logn) etc. ..
42
@ Beh, eu acho que você quis dizer "quando é o tipo de bolha melhor do que o tipo rápido": P
Kornel Kisielewicz 04/02/10
2
Um ponteiro inteligente seria uma chave trivial?
thomthom
Aqui é um dos casos em que mapa é aquele vantajoso: stackoverflow.com/questions/51964419/...
anilbey

Respostas:

399

Não esqueça que mapmantém seus elementos ordenados. Se você não pode desistir disso, obviamente não pode usar unordered_map.

Outra coisa a ter em mente é que unordered_mapgeralmente usa mais memória. mapapenas possui alguns indicadores de manutenção da casa e memória para cada objeto. Por outro lado, unordered_mappossui uma grande matriz (pode ser bastante grande em algumas implementações) e, em seguida, memória adicional para cada objeto. Se você precisa estar ciente da memória, mapdeve provar melhor, porque falta uma grande variedade.

Então, se você precisar de pura recuperação de pesquisa, eu diria que unordered_mapé o caminho a percorrer. Mas sempre existem trocas e, se você não pode pagar, não pode usá-lo.

Apenas por experiência pessoal, encontrei uma enorme melhoria no desempenho (medida, é claro) ao usar em unordered_mapvez de mapem uma tabela de consulta de entidade principal.

Por outro lado, achei muito mais lento inserir e remover repetidamente elementos. É ótimo para uma coleção relativamente estática de elementos, mas se você estiver fazendo muitas inserções e exclusões, o hashing + bucketing parece somar. (Observe, isso ocorreu em várias iterações.)

GManNickG
fonte
3
Mais uma coisa sobre a grande (r) propriedade do bloco de memória de unordered_map vs. map (ou vetor versus lista), o heap de processo padrão (falando Windows aqui) é serializado. Alocar blocos (pequenos) em grandes quantidades em um aplicativo multithread é muito caro.
ROAR
4
RA: Você pode controlar um pouco isso com seu próprio tipo de alocador combinado com qualquer contêiner, se achar que isso é importante para qualquer programa em particular.
9
Se você conhece o tamanho unordered_mape reserva isso no início - você ainda paga uma multa de muitas inserções? Digamos, você está inserindo apenas uma vez quando criou a tabela de pesquisa - e depois apenas lê a partir dela.
thomthom
3
@thomthom Tanto quanto posso dizer, não deve haver penalidade em termos de desempenho. A razão pela qual o desempenho é atingido é devido ao fato de que, se a matriz crescer muito, ela fará uma nova revisão de todos os elementos. Se você chamar de reserva, ele poderá refazer ahassa dos elementos existentes, mas se você o chamar no início, não haverá penalidade, pelo menos de acordo com cplusplus.com/reference/unordered_map/unordered_map/reserve
Richard Fung
6
Tenho certeza de que, na memória, é o contrário. Supondo o fator de carga 1.0 padrão para um contêiner não ordenado: você tem um ponteiro por elemento para o balde e um ponteiro por elemento para o próximo elemento no balde; portanto, você acaba com dois ponteiros e dados por cada elemento. Para um contêiner ordenado, por outro lado, uma implementação típica da árvore RB terá: três ponteiros (esquerda / direita / pai) mais um bit de cor que, devido ao alinhamento, leva adiante uma palavra. São quatro ponteiros, mais dados por cada elemento.
Yakov Galka
126

Se você quiser comparar a velocidade de suas implementações std::mape de suas std::unordered_mapimplementações, use o projeto sparsehash do Google, que possui um programa time_hash_map para cronometrá-las. Por exemplo, com o gcc 4.4.2 em um sistema Linux x86_64

$ ./time_hash_map
TR1 UNORDERED_MAP (4 byte objects, 10000000 iterations):
map_grow              126.1 ns  (27427396 hashes, 40000000 copies)  290.9 MB
map_predict/grow       67.4 ns  (10000000 hashes, 40000000 copies)  232.8 MB
map_replace            22.3 ns  (37427396 hashes, 40000000 copies)
map_fetch              16.3 ns  (37427396 hashes, 40000000 copies)
map_fetch_empty         9.8 ns  (10000000 hashes,        0 copies)
map_remove             49.1 ns  (37427396 hashes, 40000000 copies)
map_toggle             86.1 ns  (20000000 hashes, 40000000 copies)

STANDARD MAP (4 byte objects, 10000000 iterations):
map_grow              225.3 ns  (       0 hashes, 20000000 copies)  462.4 MB
map_predict/grow      225.1 ns  (       0 hashes, 20000000 copies)  462.6 MB
map_replace           151.2 ns  (       0 hashes, 20000000 copies)
map_fetch             156.0 ns  (       0 hashes, 20000000 copies)
map_fetch_empty         1.4 ns  (       0 hashes,        0 copies)
map_remove            141.0 ns  (       0 hashes, 20000000 copies)
map_toggle             67.3 ns  (       0 hashes, 20000000 copies)
Blair Zajac
fonte
2
Parece mapa não ordenada bate o mapa na maior parte do operations.Event na inserção ...
Michael IV
7
sparsehash não existe mais. foi excluído ou removido.
User9102d82
11
@ User9102d82 Editei a pergunta para se referir a um link de waybackmachine .
andreee 15/05/19
Apenas para garantir que outras pessoas notem os outros números além do tempo: Esses testes foram feitos com objetos de 4 bytes / estruturas de dados, também conhecido como int. Se você armazenar algo que exija hash mais pesado ou maior (tornando as operações de cópia mais pesadas), o mapa padrão poderá rapidamente ter uma vantagem!
AlexGeorg
82

Eu ecoaria aproximadamente o mesmo ponto que GMan fez: dependendo do tipo de uso, std::mappode ser (e geralmente é) mais rápido que std::tr1::unordered_map(usando a implementação incluída no VS 2008 SP1).

Existem alguns fatores complicadores a serem lembrados. Por exemplo, em std::map, você está comparando chaves, o que significa que você só olha o suficiente no início de uma chave para distinguir entre os sub-ramos direito e esquerdo da árvore. Na minha experiência, quase a única vez em que você olha para uma chave inteira é se estiver usando algo como int que possa comparar em uma única instrução. Com um tipo de chave mais típico, como std :: string, você costuma comparar apenas alguns caracteres.

Uma função de hash decente, por outro lado, sempre olha para a chave inteira . IOW, mesmo que a pesquisa da tabela seja de complexidade constante, o hash em si tem uma complexidade aproximadamente linear (embora no comprimento da chave, não no número de itens). Com cadeias longas como chaves, um std::mappode concluir uma pesquisa antes unordered_mapmesmo de iniciar sua pesquisa.

Segundo, embora existam vários métodos de redimensionar tabelas de hash, a maioria deles é bem lenta - ao ponto de que, a menos que as pesquisas sejam consideravelmente mais frequentes do que inserções e exclusões, std :: map geralmente será mais rápido que std::unordered_map.

Obviamente, como mencionei no comentário da sua pergunta anterior, você também pode usar uma tabela de árvores. Isso tem vantagens e desvantagens. Por um lado, limita o pior caso ao de uma árvore. Também permite inserção e exclusão rápidas, porque (pelo menos quando eu fiz isso) eu usei um tamanho fixo de tabela. A eliminação de todo o redimensionamento de tabelas permite manter sua tabela de hash muito mais simples e geralmente mais rápida.

Outro ponto: os requisitos para o hash e os mapas baseados em árvore são diferentes. O hash obviamente requer uma função de hash e uma comparação de igualdade, onde os mapas ordenados requerem uma comparação menor que a. É claro que o híbrido que mencionei requer ambos. Obviamente, para o caso comum de usar uma string como chave, isso não é realmente um problema, mas alguns tipos de chaves são mais adequados para pedidos do que para hash (ou vice-versa).

Jerry Coffin
fonte
2
O redimensionamento de hash pode ser reduzido pela dynamic hashingtécnica, que consiste em ter um período de transição em que cada vez que você insere um item, você também refaz koutros itens. Claro, isso significa que durante a transição você tem que procurar 2 mesas diferentes ...
Matthieu M.
2
"Com cadeias longas como chaves, um std :: map pode terminar uma pesquisa antes que um unordered_map inicie sua pesquisa." - se a chave não estiver presente na coleção. Se estiver presente, é claro que o comprimento total precisa ser comparado para confirmar a partida. Mas, da mesma forma, é unordered_mapnecessário confirmar uma correspondência de hash com uma comparação completa; portanto, tudo depende de quais partes do processo de pesquisa você está contrastando.
Steve Jessop
2
geralmente você pode substituir a função hash com base no conhecimento dos dados. por exemplo, se os seus longos cordões variar mais nos últimos 20 bytes do que no primeiro 100, apenas hash a última 20.
Erik Aronesty
56

Fiquei intrigado com a resposta de @Jerry Coffin, que sugeriu que o mapa ordenado exibisse aumentos de desempenho em seqüências longas, depois de alguma experimentação (que pode ser baixada do pastebin ), descobri que isso parece válido apenas para coleções de seqüências aleatórias, quando o mapa é inicializado com um dicionário classificado (que contém palavras com quantidades consideráveis ​​de sobreposição de prefixos), essa regra é quebrada, provavelmente devido ao aumento da profundidade da árvore necessária para recuperar o valor. Os resultados são mostrados abaixo, a primeira coluna numérica é o tempo de inserção e o segundo é o tempo de busca.

g++ -g -O3 --std=c++0x   -c -o stdtests.o stdtests.cpp
g++ -o stdtests stdtests.o
gmurphy@interloper:HashTests$ ./stdtests
# 1st number column is insert time, 2nd is fetch time
 ** Integer Keys ** 
 unordered:      137      15
   ordered:      168      81
 ** Random String Keys ** 
 unordered:       55      50
   ordered:       33      31
 ** Real Words Keys ** 
 unordered:      278      76
   ordered:      516     298
Gearoid Murphy
fonte
2
Obrigado pelo teste. Para garantir que não estamos medindo ruído, mudei-o para realizar cada operação várias vezes (e inseri o contador em vez de 1 no mapa). Eu o executei em um número diferente de teclas (de 2 a 1000) e até ~ 100 teclas no mapa, std::mapgeralmente supera o desempenho std::unordered_map, especialmente para teclas inteiras, mas ~ 100 teclas parece que perde a vantagem e std::unordered_mapcomeça a ganhar. Inserir uma sequência já ordenada em uma std::mapé muito ruim, você terá o pior cenário possível (O (N)).
Andreas Magnusson
30

Gostaria apenas de salientar que ... existem muitos tipos de unordered_maps.

Consulte o artigo da Wikipedia no mapa de hash. Dependendo de qual implementação foi usada, as características em termos de pesquisa, inserção e exclusão podem variar bastante.

E é isso que mais me preocupa com a adição do unordered_mapSTL: eles terão que escolher uma implementação específica, pois duvido que Policyseguirão adiante e, portanto, ficaremos presos a uma implementação para o uso médio e nada para os outros casos ...

Por exemplo, alguns mapas de hash têm reformulação linear, onde, em vez de reformular todo o mapa de hash de uma só vez, uma parte é reformulada em cada inserção, o que ajuda a amortizar o custo.

Outro exemplo: alguns mapas de hash usam uma lista simples de nós para um bucket, outros usam um mapa, outros não usam nós, mas encontram o slot mais próximo e, por último, alguns usam uma lista de nós, mas reordenam para que o último elemento acessado está na frente (como uma coisa de cache).

Então, no momento, eu prefiro o std::mapou talvez um loki::AssocVector(para conjuntos de dados congelados).

Não me entenda mal, eu gostaria de usar o std::unordered_mape eu posso no futuro, mas é difícil "confiar" na portabilidade de um contêiner quando você pensa em todas as maneiras de implementá-lo e nos vários desempenhos resultantes disto.

Matthieu M.
fonte
17
+1: ponto válido - a vida era mais fácil quando eu estava usando minha própria implementação - pelo menos eu sabia onde era
ruim
25

Diferenças significativas que realmente não foram adequadamente mencionadas aqui:

  • mapmantém os iteradores para todos os elementos estáveis, no C ++ 17 você pode até mover elementos de um mappara o outro sem invalidar os iteradores para eles (e, se implementado corretamente, sem qualquer alocação em potencial).
  • map horários para operações únicas são geralmente mais consistentes, pois nunca precisam de grandes alocações.
  • unordered_mapo uso std::hashconforme implementado no libstdc ++ é vulnerável ao DoS se alimentado com entrada não confiável (ele usa o MurmurHash2 com uma semente constante - não que a propagação realmente ajude, consulte https://emboss.github.io/blog/2012/12/14/ quebrando-sopro-hash-inundando-dos-recarregado / ).
  • A encomenda permite pesquisas de faixa eficientes, por exemplo, repete todos os elementos com a tecla ≥ 42.
user1531083
fonte
14

As tabelas de hash têm constantes mais altas que as implementações comuns de mapas, que se tornam significativas para pequenos contêineres. O tamanho máximo é 10, 100 ou talvez 1.000 ou mais? As constantes são as mesmas de sempre, mas O (log n) está próximo de O (k). (Lembre-se de que a complexidade logarítmica ainda é muito boa.)

O que faz uma boa função de hash depende das características dos seus dados; portanto, se eu não pretendo olhar para uma função de hash personalizada (mas certamente posso mudar de idéia mais tarde, e facilmente, já que digitei muito perto de tudo) e mesmo que os padrões sejam escolhidos para executar decentemente para muitas fontes de dados, encontro as instruções natureza do mapa para ser uma ajuda suficiente inicialmente, que eu ainda padronizo para mapear, em vez de uma tabela de hash nesse caso.

Além disso, dessa forma, você não precisa nem pensar em escrever uma função de hash para outros tipos (geralmente UDT) e apenas escrever op <(que você deseja de qualquer maneira).


fonte
@ Roger, você conhece a quantidade aproximada de elementos nos quais unordered_map é mapeado? Eu provavelmente vou escrever um teste para ele, porém, de qualquer maneira ... (+1)
kornel kisielewicz
11
@Kornel: Não é preciso muito; meus testes foram com cerca de 10.000 elementos. Se quisermos um gráfico realmente preciso, você pode analisar uma implementação de mape uma de unordered_map, com certa plataforma e determinado tamanho de cache, e fazer uma análise complexa. : P
GManNickG
Depende dos detalhes da implementação, dos parâmetros de ajuste em tempo de compilação (fáceis de suportar se você estiver escrevendo sua própria implementação) e até da máquina específica usada para os testes. Assim como nos outros contêineres, o comitê define apenas os requisitos gerais.
13

Razões foram dadas em outras respostas; aqui está outro.

As operações std :: map (árvore binária balanceada) são amortizadas O (log n) e, na pior das hipóteses, O (log n). As operações std :: unordered_map (tabela de hash) são amortizadas O (1) e, na pior das hipóteses, O (n).

Como isso ocorre na prática é que a tabela de hash "soluça" de vez em quando com uma operação O (n), que pode ou não ser algo que seu aplicativo pode tolerar. Se não puder tolerá-lo, você preferiria std :: map sobre std :: unordered_map.

Don Hatch
fonte
12

Sumário

Assumindo que a encomenda não é importante:

  • Se você for criar uma tabela grande uma vez e fazer muitas consultas, use std::unordered_map
  • Se você for criar uma tabela pequena (pode ter menos de 100 elementos) e fazer muitas consultas, use std::map. Isso ocorre porque as leituras são O(log n).
  • Se você vai mudar muito de mesa, então pode ser std::map uma boa opção.
  • Se você estiver em dúvida, basta usar std::unordered_map.

Contexto histórico

Na maioria dos idiomas, o mapa não ordenado (também conhecido como dicionários baseados em hash) é o mapa padrão; no entanto, em C ++, você recebe o mapa ordenado como mapa padrão. Como isso aconteceu? Algumas pessoas assumem erroneamente que o comitê C ++ tomou essa decisão com sua sabedoria única, mas a verdade é infelizmente mais feia do que isso.

Acredita- se que o C ++ tenha acabado com o mapa ordenado como padrão, porque não há muitos parâmetros sobre como eles podem ser implementados. Por outro lado, as implementações baseadas em hash têm muito o que falar. Portanto, para evitar bloqueios na padronização, eles apenas se deram bem com o mapa ordenado. Por volta de 2005, muitos idiomas já tinham boas implementações de implementação baseada em hash e, portanto, era mais fácil para o comitê aceitar novas std::unordered_map. Em um mundo perfeito, std::mapteria sido desordenado e teríamos std::ordered_mapcomo tipo separado.

atuação

Abaixo dois gráficos devem falar por si ( fonte ):

insira a descrição da imagem aqui

insira a descrição da imagem aqui

Shital Shah
fonte
Dados interessantes; Quantas plataformas você incluiu em seus testes?
precisa
11
por que devo usar std :: map para tabela pequena ao fazer muitas consultas, pois std :: unordered_map sempre tem um desempenho melhor que std :: map de acordo com as 2 imagens postadas aqui?
Ricky
O gráfico mostra o desempenho para 0,13M ou mais elementos. Se você tiver elementos pequenos (pode ser <100), então O (log n) poderá se tornar menor que o mapa não-ordenado.
Shital Shah
10

Eu fiz recentemente um teste que faz 50000 mesclar e classificar. Isso significa que, se as chaves da string forem as mesmas, mescle a string de bytes. E a saída final deve ser classificada. Portanto, isso inclui uma pesquisa para cada inserção.

Para a mapimplementação, são necessários 200 ms para concluir o trabalho. Para o unordered_map+ map, são necessários 70 ms para unordered_mapinserção e 80 ms para mapinserção. Portanto, a implementação híbrida é 50 ms mais rápida.

Devemos pensar duas vezes antes de usar o map. Se você só precisa classificar os dados no resultado final do seu programa, uma solução híbrida pode ser melhor.

Wendong
fonte
0

Pequena adição a todos os itens acima:

Melhor uso map, quando você precisar obter elementos por intervalo, pois eles são classificados e você pode simplesmente iterá-los de um limite para outro.

Denis Sablukov
fonte
-1

De: http://www.cplusplus.com/reference/map/map/

"Internamente, os elementos em um mapa são sempre classificados por sua chave, seguindo um critério específico de ordem fraca estrita, indicado por seu objeto de comparação interna (do tipo Compare).

os contêineres de mapa geralmente são mais lentos que os contêineres unordered_map para acessar elementos individuais por sua chave, mas permitem a iteração direta em subconjuntos com base em seu pedido ".

Kunal Bansal
fonte