2

Eu estava lendo um artigo no DevMedia sobre os principais algoritmos de ordenação.

No artigo são comparados quatro algoritmos desse tipo, bubble sort, selection sort, quick sort e insertion sort.

Bem, pensei que o hardware não fosse relevante para comparar algoritmos entre si, porque, pelo meu raciocínio, eles estariam sendo testados no mesmo computador, porém, li sobre branch prediction, logo depois, então a dúvida surgiu: o hardware é importante para medir comparativamente algoritmos de ordenação?

Mas, acho que a pergunta seria melhor respondida se eu soubesse a resposta para a origem da dúvida: as diferentes CPUs (sigla em inglês para Unidade Central de Processamento) podem implementar branch prediction de tal forma que o algoritmo A seja mais eficiente que o algoritmo B em uma CPU e menos eficiente em outra?

1
  • 1
    O processador é tão complexo que ninguém nem deve saber esta resposta, somente testando mesmo. Porém estes algoritmos de ordenação são tão diferentes que é altamente improvável que o hardware influencie no resultado de comparação que você está tentando medir. O importante é usar o mesmo hardware para medição. 31/12/2016 às 7:23

1 Resposta 1

3

Há controvérsias. Isso pode ser visto nessa pergunta. Leia tudo, inclusive os comentários, tem coisa muito boa ali, inclusive mostrando como as coisas ocorrem de fato na prática.

Me parece que entende que medir a complexidade de algoritmo não é medir a velocidade dele. Há uma relação entre ambos, mas não é tão direta assim.

É claro que é impossível pegar muitos dados e ter um O(n^m) mais rápido que um O(1) em qualquer hardware.

O algoritmo, da maneira como as pessoas fazem, não leva em consideração condições de hardware.

O mais comum é classificar a eficiência dentro de um ambiente neutro. Em geral não considera-se otimizações.

Imagine rodar isso em um computador sobrecarregado. Toda teoria evapora. Imagina um computador que gasta mais tempo fazendo swap em disco do que no cálculo. De que adianta saber na teoria qual a eficiência do algoritmo?

Na teoria pode-se considerar o hardware. Pode-se adicionar variáveis que considere essas condições. Mas é muito raro ter vantagem em saber isso. Em geral isso é feito em ambiente acadêmico ou de análise muito específica e quando está se fazendo algo que terá muita utilização em algo que potencialmente precisa de muita performance. Então há casos para considerar todas variáveis. No dia a dia você faz uma análise de eficiência superficial para escolher o algoritmo correto e faz testes reais de velocidade com dados típicos e extremos para ver o que acontece de fato em condições reais. Costuma dar resultados mais adequados do ponto de vista de engenharia, ainda que do ponto de vista científico não seja necessariamente o melhor.

Eu já vi gente dizendo que existem cálculos nesse sentido, mas nunca vi alguém os mostrando. Eu sei que eles existem, mas estão bem escondidos :)

Dito tudo isso, a minha experiência mostra que cache faz mais diferença do que branch prediction na maioria dos casos. Algoritmos que possuem menos branches podem ser mais eficientes em máquinas mais simples.

Um algoritmo que deve manipular dados em disco pode ser o mais adequado, enquanto que os mesmo dados em memória outro algoritmo pode ser mais adequado. Imagine que um cache L1 ou até mesmo registradores pudessem comportar todos os dados a serem processados como poderia haver melhoria.

Lembrando que para poucos dados (N baixo), na prática, tanto faz qual o algoritmo usado.

Veja isto Algoritmos de ordenação de memória externa e interna.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .