Por que usar comparações em vez de tempo de execução para comparar dois algoritmos?

19

Percebo que em alguns trabalhos de pesquisa em CS, para comparar a eficiência de dois algoritmos, o número total de comparação de chaves nos algoritmos é usado, em vez dos próprios tempos reais de computação. Por que não podemos comparar qual é o melhor executando os dois programas e contando o tempo total necessário para executar os algoritmos?

tem
fonte
Bem-vinda! Espero que a maioria desses documentos não use tempos de execução. Sei que alguns o fazem, especialmente nas comunidades mais aplicadas e quando os sistemas considerados são muito complexos.
Raphael

Respostas:

14

Esta é realmente uma questão profunda que tem algumas respostas metódicas e pragmáticas. Suponho que você queira saber algo sobre o (s) algoritmo (s) em questão. Se você quiser saber qual algoritmo funciona melhor em uma determinada máquina em determinadas entradas, vá em frente e meça os tempos de execução. Se você deseja comparar a qualidade de um compilador para um determinado algoritmo, vá em frente e meça os tempos de execução. Para aprender algo sobre o algoritmo, não faça isso.

Deixe-me primeiro dar algumas razões pelas quais o uso de tempos de execução não é uma boa ideia.

  1. Generalidade Os
    tempos de execução medidos usando um idioma e um compilador em uma máquina têm pouco significado se você alterar qualquer componente. Mesmo implementações ligeiramente diferentes do mesmo algoritmo podem ter um desempenho diferente, porque você aciona alguma otimização do compilador no caso, mas não no outro.
  2. Previsão
    Então você tem alguns tempos de execução para algumas entradas. O que isso diz sobre o tempo de execução de alguma outra entrada? Em geral, nada.
  3. Significado
    Normalmente, você não fará o benchmark de todas as entradas (de algum tamanho), de modo que restrinja imediatamente sua capacidade de comparar algoritmos: talvez seu conjunto de testes tenha acionado o pior caso em um e o melhor caso no outro algoritmo? Ou talvez suas entradas sejam muito pequenas para exibir o comportamento do tempo de execução .
  4. Medição
    Medir bem os tempos de execução não é trivial. Existe um JIT? Houve contenda, ou seja, você está contando o tempo em que o algoritmo nem sequer foi executado? Você pode reproduzir exatamente o mesmo estado de máquina para outra execução (do outro algoritmo), em particular processos e caches simultâneos? Como é tratada a latência da memória?

Espero que eles o tenham convencido de que os tempos de execução são uma medida horrível para comparar algoritmos e que é necessário algum método abstrato e geral para investigar o tempo de execução do algoritmo.

Para a segunda parte da pergunta. Por que usamos comparações ou operações elementares semelhantes?

  1. Rastreabilidade analítica
    Supondo que você queira fazer uma análise formal, você deve ser capaz de fazê-lo. Contar declarações individuais é muito técnico, às vezes até difícil; algumas pessoas fazem isso mesmo assim (por exemplo, Knuth). Contar apenas algumas instruções - aquelas que dominam o tempo de execução - é mais fácil. Pelo mesmo motivo, geralmente "apenas" investigamos (limites superiores no) pior tempo de execução.

  2. Dominância
    A operação selecionada domina o tempo de execução. Isso não significa que ele contribui com mais tempo de execução - as comparações claramente não, por exemplo, no Quicksort ao classificar números inteiros do tamanho de palavras. Mas eles são executados com mais frequência ; portanto, contando-os, você conta com que frequência as partes mais executadas do algoritmo são executadas. Consequentemente, seu tempo de execução assintótico é proporcional ao número de operações elementares dominantes. É por isso que nos sentimos à vontade usando a notação Landau e a palavra "tempo de execução", mesmo contando apenas comparações.

Observe que pode ser útil contar mais de uma operação. Por exemplo, algumas variantes do Quicksort fazem mais comparações, mas menos trocas do que outras (em média).

Pelo que vale a pena, depois de ter feito toda a teoria, convém revisitar os tempos de execução para verificar se as previsões que sua teoria faz são sólidas. Caso contrário, sua teoria não é útil (na prática) e precisa ser ampliada. A hierarquia de memória é uma das primeiras coisas que você percebe ser importante, mas está ausente nas análises básicas.

Rafael
fonte
1
Lembre-se de que a análise formal também tem seus limites. Por exemplo, o caso médio de distribuições de entrada não uniformes é muitas vezes intratável.
Raphael
10

Isso ocorre porque o tempo total para executar os algoritmos depende do hardware em que é executado, além de outros fatores. Não é confiável comparar dois algoritmos se um estiver sendo executado em um Pentium 4 e o outro em, digamos, um Core i7. Não apenas isso, mas digamos que você executou os dois no mesmo computador. O que quer dizer que ambos têm a mesma quantidade de tempo do processador? O que acontece se algum outro processo tiver uma prioridade mais alta que o processo de um dos algoritmos?

Para superar isso, separamos esse tempo geral para concluir e, em vez disso, comparamos com base em quão bem o algoritmo é dimensionado. Você pode ter notado notações como O (1) ou O (n ^ 2) nos trabalhos de pesquisa. Isso pode exigir um pouco mais de leitura, se você for ver interessados notação Big O .

Chris Howell
fonte
1
Além disso, o tempo de execução real depende do tamanho e do conteúdo da entrada real usada para executar os algoritmos!
Tsuyoshi Ito
7

Como as outras respostas explicam por que analisamos o tempo de execução em termos de número de operações elementares, deixe-me oferecer algumas razões pelas quais as comparações são a métrica correta de muitos algoritmos de classificação (não todos):

  • para muitos algoritmos de classificação, o número de comparações domina o tempo de execução, ou seja, pelo menos, tantas comparações são realizadas quanto qualquer outra operação elementar
  • comparações são caras operação ; pense em como uma rotina de classificação é implementada na biblioteca: a função de classificação recebe uma matriz de elementos e um ponteiro para uma função que compara dois elementos; em geral, chamar e aguardar a execução da função de comparação é mais caro que as operações "internas"; como essa função é fornecida pelo usuário, é mais difícil otimizá-la
  • (isso pode ou não ser um bom motivo para alguns), podemos dizer algo interessante sobre o número de comparações que são suficientes e necessárias para ordenar uma sequência; sabemos como fazer isso na pior das hipóteses e, em média, para várias distribuições, até como projetar um algoritmo que converge para o ideal, pois ele é executado nos itens amostrados de uma distribuição desconhecida ( algoritmos de auto-aperfeiçoamento ); sabemos como fazer isso quando algumas comparações são feitas de graça ( Classificação com informações parciais )
Sasho Nikolov
fonte
1) "pelo menos tantas comparações são realizadas quanto qualquer outra operação elementar" - apenas até um fator constante. 2) "comparações são a operação cara" - que assume uma configuração genérica. Para classificação inteira (que geralmente é analisada), os swaps geralmente são mais caros.
Raphael
certo. op parecia confuso sobre a análise de algoritmos em geral, não queria trazer fatores constantes. eu espero que o fato de que eu estou falando sobre uma configuração genérica é clara a partir da descrição - a rotina de classificação em uma biblioteca padrão não é inteiro de classificação
Sasho Nikolov
além dos papéis que op serra são definitivamente não sobre especializada inteiro algoritmos de ordenação, não há número um contagens de comparações
Sasho Nikolov
@ Rafael Classificar números inteiros pequenos não é um problema comum na prática. Aposto que a maioria das classificações que acontecem no mundo são em strings (de um comprimento ou de outro ). Mesmo para a classificação de números inteiros, não tenho certeza se é preciso que os swaps sejam mais caros - a ramificação é uma operação relativamente cara em um processador high-end moderno, pois a previsão de ramificação seria praticamente inútil na classificação.
Gilles 'SO- stop be evil' -
@Gilles Por si só, os swaps são mais caros do que as comparações com números inteiros do que qualquer plataforma que eu conheça. Custos "secundários", como, por exemplo, previsões errôneas de agências, são definitivamente um fator cujo impacto está sujeito a pesquisas em andamento. (Em relação ao uso na prática, não posso fazer uma declaração qualificada. No entanto, observo que os mantenedores de bibliotecas padrão continuam melhorando os algoritmos de classificação que usam para tipos de dados primitivos, portanto, presumo que eles veem muito uso (ab).)
Raphael