Eficiência algorítmica - Algorithmic efficiency

Em ciência da computação , a eficiência algorítmica é uma propriedade de um algoritmo que se relaciona à quantidade de recursos computacionais usados ​​pelo algoritmo. Um algoritmo deve ser analisado para determinar seu uso de recursos e a eficiência de um algoritmo pode ser medida com base no uso de diferentes recursos. A eficiência do algoritmo pode ser considerada análoga à produtividade da engenharia para um processo repetitivo ou contínuo.

Para máxima eficiência, desejamos minimizar o uso de recursos. No entanto, recursos diferentes, como complexidade de tempo e espaço, não podem ser comparados diretamente, de modo que qual dos dois algoritmos é considerado mais eficiente geralmente depende de qual medida de eficiência é considerada mais importante.

Por exemplo, bubble sort e timsort são algoritmos para classificar uma lista de itens do menor ao maior. A classificação por bolha classifica a lista em tempo proporcional ao número de elementos ao quadrado ( consulte a notação Big O ), mas requer apenas uma pequena quantidade de memória extra que é constante em relação ao comprimento da lista ( ). Timsort classifica a lista linear no tempo (proporcional a uma quantidade vezes seu logaritmo) no comprimento da lista ( ), mas tem um requisito de espaço linear no comprimento da lista ( ). Se listas grandes devem ser classificadas em alta velocidade para um determinado aplicativo, timsort é uma escolha melhor; no entanto, se minimizar a área de cobertura da memória da classificação for mais importante, a classificação por bolha é uma escolha melhor.

Fundo

A importância da eficiência com respeito ao tempo foi enfatizada por Ada Lovelace em 1843, aplicando-se ao motor analítico mecânico de Charles Babbage :

"Em quase todos os cálculos, uma grande variedade de arranjos para a sucessão dos processos é possível, e várias considerações devem influenciar as seleções entre eles para os fins de um mecanismo de cálculo. Um objetivo essencial é escolher aquele arranjo que tende a reduzir para um mínimo o tempo necessário para completar o cálculo "

Os primeiros computadores eletrônicos eram severamente limitados pela velocidade das operações e pela quantidade de memória disponível. Em alguns casos, percebeu-se que havia uma compensação de espaço-tempo , em que uma tarefa poderia ser tratada usando um algoritmo rápido que usava bastante memória de trabalho ou usando um algoritmo mais lento que usava muito pouca memória de trabalho . A compensação de engenharia foi então usar o algoritmo mais rápido que caberia na memória disponível.

Os computadores modernos são significativamente mais rápidos do que os primeiros e têm uma quantidade de memória muito maior disponível ( Gigabytes em vez de Kilobytes ). No entanto, Donald Knuth enfatizou que a eficiência ainda é uma consideração importante:

"Em disciplinas de engenharia estabelecidas, uma melhoria de 12%, facilmente obtida, nunca é considerada marginal e acredito que o mesmo ponto de vista deve prevalecer na engenharia de software"

Visão geral

Um algoritmo é considerado eficiente se seu consumo de recursos, também conhecido como custo computacional, estiver em um nível aceitável ou abaixo dele. Grosso modo, 'aceitável' significa: será executado em um período de tempo ou espaço razoável em um computador disponível, normalmente em função do tamanho da entrada. Desde a década de 1950, os computadores viram aumentos dramáticos no poder computacional disponível e na quantidade de memória disponível, de modo que os atuais níveis aceitáveis ​​seriam inaceitáveis ​​até dez anos atrás. Na verdade, graças à duplicação aproximada da capacidade do computador a cada 2 anos , as tarefas que são aceitavelmente eficientes em smartphones modernos e sistemas embarcados podem ter sido inaceitavelmente ineficientes para servidores industriais há 10 anos.

Os fabricantes de computadores frequentemente lançam novos modelos, geralmente com desempenho superior . Os custos de software podem ser bastante altos, portanto, em alguns casos, a maneira mais simples e barata de obter melhor desempenho pode ser simplesmente comprar um computador mais rápido, desde que seja compatível com um computador existente.

Existem muitas maneiras de medir os recursos usados ​​por um algoritmo: as duas medidas mais comuns são a velocidade e o uso da memória; outras medidas podem incluir velocidade de transmissão, uso de disco temporário, uso de disco de longo prazo, consumo de energia, custo total de propriedade , tempo de resposta a estímulos externos, etc. Muitas dessas medidas dependem do tamanho da entrada para o algoritmo, ou seja, quantidade de dados a serem processados. Eles também podem depender da maneira como os dados são organizados; por exemplo, alguns algoritmos de classificação funcionam mal em dados que já estão classificados ou que são classificados na ordem inversa.

Na prática, existem outros fatores que podem afetar a eficiência de um algoritmo, como requisitos de precisão e / ou confiabilidade. Conforme detalhado abaixo, a maneira como um algoritmo é implementado também pode ter um efeito significativo na eficiência real, embora muitos aspectos disso estejam relacionados a problemas de otimização .

Análise teórica

Na análise teórica de algoritmos , a prática normal é estimar sua complexidade no sentido assintótico. A notação mais comumente usado para descrever o consumo de recursos ou "complexidade" é Donald Knuth 's Big O notação , representando a complexidade de um algoritmo como uma função do tamanho da entrada . A notação Big O é uma medida assintótica da complexidade da função, onde aproximadamente significa que o requisito de tempo para um algoritmo é proporcional a , omitindo termos de ordem inferior que contribuem menos do que para o crescimento da função conforme cresce arbitrariamente grande . Essa estimativa pode ser enganosa quando é pequena, mas geralmente é suficientemente precisa quando é grande, pois a notação é assintótica. Por exemplo, a classificação por bolha pode ser mais rápida do que a classificação por mesclagem quando apenas alguns itens devem ser classificados; no entanto, qualquer implementação provavelmente atenderá aos requisitos de desempenho para uma pequena lista. Normalmente, os programadores estão interessados ​​em algoritmos que escalam com eficiência para grandes tamanhos de entrada e a classificação por mesclagem é preferida em vez da classificação por bolha para listas de comprimento encontradas na maioria dos programas intensivos de dados.

Alguns exemplos de notação Big O aplicada à complexidade de tempo assintótica dos algoritmos incluem:

Notação Nome Exemplos
constante Encontrar a mediana de uma lista classificada de medições; Usando uma tabela de pesquisa de tamanho constante ; Usando uma função hash adequada para pesquisar um item.
logarítmico Encontrar um item em uma matriz classificada com uma pesquisa binária ou uma árvore de pesquisa balanceada , bem como todas as operações em um heap Binomial .
linear Encontrar um item em uma lista não classificada ou em uma árvore malformada (pior caso) ou em uma matriz não classificada; Adicionando dois inteiros de n bits por transporte de ondulação .
linear , loglinear ou quase linear Execução de uma transformação rápida de Fourier ; heapsort , quicksort ( melhor e médio caso ) ou merge sort
quadrático Multiplicando dois números de n dígitos por um algoritmo simples ; classificação por bolha (pior caso ou implementação ingênua), classificação Shell , classificação rápida ( pior caso ), classificação por seleção ou classificação por inserção
exponencial Encontrar a solução ótima (não aproximada ) para o problema do caixeiro viajante usando programação dinâmica ; determinar se duas declarações lógicas são equivalentes usando a pesquisa de força bruta

Benchmarking: medição de desempenho

Para novas versões de software ou para fornecer comparações com sistemas concorrentes, às vezes são usados benchmarks , que ajudam a medir o desempenho relativo de um algoritmo. Se um novo algoritmo de ordenação for produzido, por exemplo, ele pode ser comparado com seus predecessores para garantir que pelo menos seja eficiente como antes com dados conhecidos, levando em consideração quaisquer melhorias funcionais. Os benchmarks podem ser usados ​​pelos clientes ao comparar vários produtos de fornecedores alternativos para estimar qual produto será mais adequado aos seus requisitos específicos em termos de funcionalidade e desempenho. Por exemplo, no mundo do mainframe, certos produtos de classificação proprietários de empresas de software independentes, como a Syncsort, competem por velocidade com produtos dos principais fornecedores, como a IBM .

Alguns benchmarks fornecem oportunidades para produzir uma análise comparando a velocidade relativa de várias linguagens compiladas e interpretadas, por exemplo, e The Computer Language Benchmarks Game compara o desempenho de implementações de problemas de programação típicos em várias linguagens de programação.

Até mesmo a criação de benchmarks " faça você mesmo " pode demonstrar o desempenho relativo de diferentes linguagens de programação, usando uma variedade de critérios especificados pelo usuário. Isso é muito simples, como um "roundup de desempenho de nove línguas" por Christopher W. Cowell-Shah demonstra por exemplo.

Questões de implementação

Problemas de implementação também podem afetar a eficiência, como a escolha da linguagem de programação ou a maneira como o algoritmo é realmente codificado, ou a escolha de um compilador para uma determinada linguagem, ou as opções de compilação usadas, ou mesmo o funcionamento sistema que está sendo usado. Em muitos casos, uma linguagem implementada por um intérprete pode ser muito mais lenta do que uma linguagem implementada por um compilador. Veja os artigos sobre compilação just-in-time e linguagens interpretadas .

Existem outros fatores que podem afetar questões de tempo ou espaço, mas que podem estar fora do controle do programador; isso inclui alinhamento de dados , granularidade de dados , localidade de cache , coerência de cache , coleta de lixo , paralelismo de nível de instrução , multi-threading (em nível de hardware ou software), multitarefa simultânea e chamadas de sub - rotina .

Alguns processadores têm recursos para processamento vetorial , o que permite que uma única instrução opere em vários operandos ; pode ou não ser fácil para um programador ou compilador usar esses recursos. Algoritmos projetados para processamento sequencial podem precisar ser completamente reprojetados para fazer uso de processamento paralelo ou podem ser facilmente reconfigurados. À medida que a computação paralela e distribuída cresce em importância no final dos anos 2010, mais investimentos estão sendo feitos em APIs de alto nível eficientes para sistemas de computação paralela e distribuída, como CUDA , TensorFlow , Hadoop , OpenMP e MPI .

Outro problema que pode surgir na programação é que os processadores compatíveis com o mesmo conjunto de instruções (como x86-64 ou ARM ) podem implementar uma instrução de maneiras diferentes, de modo que as instruções que são relativamente rápidas em alguns modelos podem ser relativamente lentas em outros modelos . Isso geralmente apresenta desafios para otimizar compiladores , que devem ter um grande conhecimento da CPU específica e de outro hardware disponível no destino de compilação para otimizar o desempenho de um programa. Em casos extremos, um compilador pode ser forçado a emular instruções não suportadas em uma plataforma de destino de compilação, forçando-o a gerar código ou vincular uma chamada de biblioteca externa para produzir um resultado que de outra forma seria incomputável nessa plataforma, mesmo se for suportado nativamente e mais eficiente em hardware em outras plataformas. Este é frequentemente o caso em sistemas embarcados com respeito à aritmética de ponto flutuante , onde microcontroladores pequenos e de baixa potência muitas vezes carecem de suporte de hardware para aritmética de ponto flutuante e, portanto, requerem rotinas de software computacionalmente caras para produzir cálculos de ponto flutuante.

Medidas de uso de recursos

As medidas são normalmente expressas em função do tamanho da entrada .

As duas medidas mais comuns são:

  • Tempo : quanto tempo o algoritmo leva para ser concluído?
  • Espaço : quanta memória de trabalho (normalmente RAM) é necessária para o algoritmo? Isso tem dois aspectos: a quantidade de memória necessária para o código (uso de espaço auxiliar) e a quantidade de memória necessária para os dados nos quais o código opera (uso de espaço intrínseco).

Para computadores cuja energia é fornecida por uma bateria (por exemplo, laptops e smartphones ), ou para cálculos muito longos / grandes (por exemplo, supercomputadores ), outras medidas de interesse são:

  • Consumo direto de energia : energia necessária diretamente para operar o computador.
  • Consumo de energia indireta : energia necessária para refrigeração, iluminação, etc.

A partir de 2018, o consumo de energia está crescendo como uma métrica importante para tarefas computacionais de todos os tipos e em todas as escalas, desde dispositivos de Internet das coisas incorporados a dispositivos system-on-chip e farms de servidores . Essa tendência costuma ser chamada de computação ecológica .

Medidas menos comuns de eficiência computacional também podem ser relevantes em alguns casos:

  • Tamanho de transmissão : a largura de banda pode ser um fator limitante. A compactação de dados pode ser usada para reduzir a quantidade de dados a serem transmitidos. Exibir uma foto ou imagem (por exemplo, o logotipo do Google ) pode resultar na transmissão de dezenas de milhares de bytes (48K neste caso) em comparação com a transmissão de seis bytes para o texto "Google". Isso é importante para tarefas de computação vinculada a E / S.
  • Espaço externo : espaço necessário em um disco ou outro dispositivo de memória externa; isso pode ser para armazenamento temporário enquanto o algoritmo está sendo executado, ou pode ser o armazenamento de longo prazo necessário para ser transportado para referência futura.
  • Tempo de resposta ( latência ): é particularmente relevante em um aplicativo de tempo real, quando o sistema do computador deve responder rapidamente a algum evento externo .
  • Custo total de propriedade : principalmente se um computador for dedicado a um algoritmo específico.

Tempo

Teoria

Analise o algoritmo, normalmente usando análise de complexidade de tempo para obter uma estimativa do tempo de execução como uma função do tamanho dos dados de entrada. O resultado é normalmente expresso utilizando Big O notação . Isso é útil para comparar algoritmos, especialmente quando uma grande quantidade de dados deve ser processada. Estimativas mais detalhadas são necessárias para comparar o desempenho do algoritmo quando a quantidade de dados é pequena, embora seja provavelmente de menor importância. Algoritmos que incluem processamento paralelo podem ser mais difíceis de analisar .

Prática

Use um benchmark para cronometrar o uso de um algoritmo. Muitas linguagens de programação têm uma função disponível que fornece o uso do tempo da CPU . Para algoritmos de longa execução, o tempo decorrido também pode ser interessante. Os resultados geralmente devem ser calculados em vários testes.

O perfil baseado em execução pode ser muito sensível à configuração de hardware e à possibilidade de outros programas ou tarefas serem executados ao mesmo tempo em um ambiente de multiprocessamento e multiprogramação .

Esse tipo de teste também depende muito da seleção de uma determinada linguagem de programação, compilador e opções de compilador, portanto, os algoritmos que estão sendo comparados devem ser implementados nas mesmas condições.

Espaço

Esta seção se preocupa com o uso de recursos de memória ( registradores , cache , RAM , memória virtual , memória secundária ) enquanto o algoritmo está sendo executado. Quanto à análise de tempo acima, analise o algoritmo, normalmente usando análise de complexidade de espaço para obter uma estimativa da memória de tempo de execução necessária como uma função como o tamanho dos dados de entrada. O resultado é normalmente expresso utilizando Big O notação .

Existem até quatro aspectos do uso de memória a serem considerados:

Os primeiros computadores eletrônicos e os primeiros computadores domésticos tinham quantidades relativamente pequenas de memória de trabalho. Por exemplo, a Calculadora Automática de Armazenamento Eletrônico de Atraso (EDSAC) de 1949 tinha uma memória de trabalho máxima de 1.024 palavras de 17 bits, enquanto o Sinclair ZX80 de 1980 veio inicialmente com 1.024 bytes de memória de trabalho de 8 bits. No final da década de 2010, era normal que os computadores pessoais tivessem entre 4 e 32 GB de RAM, um aumento de mais de 300 milhões de vezes mais memória.

Hierarquia de cache e memória

Os computadores atuais podem ter quantidades relativamente grandes de memória (possivelmente Gigabytes), portanto, ter que espremer um algoritmo em uma quantidade confinada de memória é muito menos problemático do que costumava ser. Mas a presença de quatro categorias diferentes de memória pode ser significativa:

Um algoritmo cujas necessidades de memória cabem na memória cache será muito mais rápido do que um algoritmo que cabe na memória principal, que por sua vez será muito mais rápido do que um algoritmo que tenha que recorrer à memória virtual. Por causa disso, as políticas de substituição de cache são extremamente importantes para a computação de alto desempenho, assim como a programação com reconhecimento de cache e o alinhamento de dados . Para complicar ainda mais o problema, alguns sistemas têm até três níveis de memória cache, com velocidades efetivas variáveis. Diferentes sistemas terão diferentes quantidades desses vários tipos de memória, portanto, o efeito das necessidades de memória do algoritmo pode variar muito de um sistema para outro.

Nos primórdios da computação eletrônica, se um algoritmo e seus dados não cabessem na memória principal, o algoritmo não poderia ser usado. Hoje em dia, o uso de memória virtual parece fornecer muita memória, mas à custa do desempenho. Se um algoritmo e seus dados caberem na memória cache, uma velocidade muito alta pode ser obtida; neste caso, minimizar o espaço também ajudará a minimizar o tempo. Isso é chamado de princípio da localidade e pode ser subdividido em localidade de referência , localidade espacial e localidade temporal . Um algoritmo que não cabe completamente na memória cache, mas que exibe localidade de referência, pode funcionar razoavelmente bem.

Críticas ao estado atual da programação

A eficiência do software cai pela metade a cada 18 meses, compensando a Lei de Moore

May prossegue afirmando:

Em sistemas onipresentes, reduzir pela metade as instruções executadas pode dobrar a vida útil da bateria e os conjuntos de big data trazem grandes oportunidades para melhores softwares e algoritmos: Reduzir o número de operações de N x N para N x log (N) tem um efeito dramático quando N é grande ... para N = 30 bilhões, essa mudança é tão boa quanto 50 anos de melhorias tecnológicas.

  • O autor do software Adam N. Rosenburg, em seu blog " O fracasso do computador digital ", descreveu o estado atual da programação como se aproximando do "horizonte de eventos de software" (aludindo ao " horizonte de eventos de calçados " fictício descrito por Douglas Adams em seu Livro do Guia do Mochileiro das Galáxias ). Ele estima que houve uma perda de 70 dB de fator de produtividade ou "99,99999 por cento, de sua capacidade de entregar as mercadorias", desde os anos 1980 - "Quando Arthur C. Clarke comparou a realidade da computação em 2001 ao computador HAL 9000 em seu livro 2001: Uma Odisséia no Espaço , ele apontou como os computadores eram maravilhosamente pequenos e poderosos, mas como a programação de computadores se tornou decepcionante "

Competições para os melhores algoritmos

As seguintes competições convidam inscrições para os melhores algoritmos com base em alguns critérios arbitrários decididos pelos juízes:

Veja também

Referências

links externos