Por que o vetor é mais rápido que o mapa em um teste, mas não o outro?

9

Sempre me disseram que os vetores são rápidos e, nos meus anos de experiência em programação, nunca vi nada para contratar isso. Eu decidi (prematuramente otimizar e) escrever uma classe associativa que era um wrapper fino em torno de um contêiner sequencial (ou seja, ::std::vector e desde a mesma interface como ::std::map . A maioria do código foi muito fácil, e eu consegui trabalhar com pouca dificuldade.

No entanto, nos meus testes de vários tipos de POD (4 a 64 bytes) e std::strings , com contagens variando de oito a duas mil, ::std::map::find foi mais rápido que meu ::associative::find , geralmente em torno de 15% mais rápido, para quase todos os testes. Eu fiz um Curto, auto-contido, correto (Compilable), exemplo que mostra claramente este no ideone Eu verifiquei a implementação do ::std::map::find do MSVC9 e confirmei que ele combina bastante com o código vecfind e ::std::lower_bound , e não posso explicar por que o ::std::map::find corre mais rápido, exceto por uma discussão sobre o Stack Overflow onde as pessoas especularam que o método de busca binária não se beneficia da localização do vetor até a última comparação (não é mais rápido), e requer aritmética de ponteiro que ::std::map nós não exigem, tornando-o mais lento.

Hoje alguém me desafiou sobre isso e forneceu esse código em ideone , que, quando testei, mostrou que o vetor era mais do que o dobro velozes.

Os codificadores do StackOverflow querem me esclarecer sobre essa aparente discrepância? Eu passei por ambos os conjuntos de código, e eles parecem me-equivalentes para mim, mas talvez eu esteja cego de tanto brincar com eles.

(Nota de rodapé: está muito perto de uma das minhas perguntas anteriores , mas meu código tinha vários bugs que foram abordados. Devido a novas informações / código, senti que isso era diferente o suficiente para justificar uma questão separada. Se não, eu vou trabalhar em mesclá-los.)

    
por Mooing Duck 17.02.2012 в 23:19
fonte

4 respostas

1

Eu vejo alguns problemas com o código ( link ) que você postou no ideone.com. (ideone realmente mostra vector como mais rápido, mas uma compilação local com o Visual Studio 11 Developer Preview mostra map mais rápido).

Primeiro, movi a variável de mapa e usei-a para inicializar o vetor para obter a mesma ordem e unicação de elementos, e então eu dei a lower_bound um comparador personalizado que compara apenas first , pois é isso que o mapa fará. Após essas alterações, o Visual Studio 11 mostra o vetor como mais rápido para os mesmos 100.000 elementos (embora o tempo de ideone não mude significativamente). link

Com test_size reduzido para 8, o mapa ainda é mais rápido. Isso não é surpreendente, porque é assim que a complexidade do algoritmo funciona, todas as constantes na função que realmente descrevem o tempo de execução com o pequeno N. Eu tenho que aumentar test_size para cerca de 2700 para o vetor puxar até e depois à frente mapear neste sistema.

    
por bames53 18.02.2012 / 00:55
fonte
2

O que faz você pensar que mapfind() é mais rápido que vecfind() ?

A saída ideone do seu código reporta cerca de 50% a mais de tiques para mapfind() do que para vecfind() . Executando o código aqui (x86_64 linux, g ++ - 4.5.1), mapfind() leva cerca do dobro do tempo que vecfind() .

Aumentando o mapa / vetor por um fator de 10, a diferença aumenta para cerca de 3 ×.

Observe, entretanto, que a soma dos segundos componentes é diferente. O mapa contém apenas um par com qualquer primeiro componente fornecido (com o meu PRNG local, que cria um mapa com dois elementos curtos), enquanto o vector pode conter vários desses pares.

    
por Daniel Fischer 18.02.2012 / 00:19
fonte
2

O número de elementos que você está colocando em seu contêiner de teste é maior que o número de saídas possíveis de rand() na Microsoft, portanto, você está recebendo números repetidos. O vetor classificado irá conter todos eles enquanto o map irá rejeitar as duplicatas. Verifique os tamanhos depois de preenchê-los - o vetor terá 100.000 elementos, o mapa 32768. Como o mapa é muito mais curto, é claro que terá melhor desempenho.

Experimente um multimap para uma comparação comparativa.

    
por Mark Ransom 18.02.2012 / 00:42
fonte
0

Um std :: vector ordenado tem duas vantagens sobre std :: map:

  • Melhor localidade de dados: o vetor armazena todos os dados de forma contígua na memória
  • Área de cobertura de memória menor: o vetor não precisa de muitos dados de escrituração (por exemplo, nenhum objeto de nó de árvore)

Se esses dois efeitos são importantes dependem do cenário. Existem dois fatores que provavelmente terão um grande impacto:

Tipo de dados

É uma vantagem para o std :: vector se os elementos forem tipos primitivos como inteiros. Nesse caso, a localidade realmente ajuda porque todos os dados necessários para a pesquisa estão em um local contíguo na memória.

Se os elementos forem digamos strings, a localidade não ajuda muito. A memória vetorial contígua agora armazena apenas objetos de ponteiros que estão potencialmente em todo o heap.

Tamanho dos dados

Se o std :: vector se encaixar em um nível de cache específico, mas o std :: map não, o std :: vector terá uma vantagem. Isso é especialmente caso você continue repetindo o teste pelos mesmos dados.

    
por Igor ostrovsky 18.02.2012 / 00:17
fonte