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:
- A quantidade de memória necessária para armazenar o código do algoritmo.
- A quantidade de memória necessária para os dados de entrada .
- A quantidade de memória necessária para quaisquer dados de saída .
- Alguns algoritmos, como classificação, geralmente reorganizam os dados de entrada e não precisam de nenhum espaço adicional para os dados de saída. Essa propriedade é conhecida como operação " no local ".
- A quantidade de memória necessária como espaço de trabalho durante o cálculo.
- Isso inclui variáveis locais e qualquer espaço de pilha necessário para rotinas chamadas durante um cálculo; este espaço de pilha pode ser significativo para algoritmos que usam técnicas recursivas .
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:
- O processador registra , a mais rápida das tecnologias de memória de computador com a menor quantidade de espaço de armazenamento. A maioria da computação direta em computadores modernos ocorre com operandos de origem e destino em registradores antes de serem atualizados para o cache, memória principal e memória virtual, se necessário. Em um núcleo de processador , normalmente existem cerca de centenas de bytes ou menos de disponibilidade de registro, embora um arquivo de registro possa conter mais registros físicos do que registros arquitetônicos definidos na arquitetura do conjunto de instruções.
- A memória cache é a segunda memória mais rápida e a segunda menor disponível na hierarquia de memória. Os caches estão presentes em CPUs, GPUs, unidades de disco rígido e periféricos externos e são normalmente implementados em RAM estática . Os caches de memória têm vários níveis ; os níveis mais baixos são maiores, mais lentos e normalmente compartilhados entre os núcleos do processador em processadores multi-core . Para processar operandos na memória cache, uma unidade de processamento deve buscar os dados do cache, realizar a operação em registradores e gravar os dados de volta no cache. Isso opera em velocidades comparáveis (cerca de 2-10 vezes mais lentas) com a CPU ou unidade lógica aritmética da GPU ou unidade de ponto flutuante se no cache L1 . É cerca de 10 vezes mais lento se houver uma falha de cache L1 e deve ser recuperado e gravado no cache L2 , e mais 10 vezes mais lento se houver uma falha de cache L2 e ele deve ser recuperado de um cache L3 , se presente.
- A memória física principal é mais frequentemente implementada em RAM dinâmica (DRAM). A memória principal é muito maior (normalmente gigabytes em comparação com ≈8 megabytes ) do que um cache de CPU L3, com latências de leitura e gravação tipicamente 10-100 vezes mais lentas. A partir de 2018, a RAM é cada vez mais implementada no chip dos processadores, como memória CPU ou GPU .
- A memória virtual é mais frequentemente implementada em termos de armazenamento secundário , como um disco rígido , e é uma extensão da hierarquia da memória que tem espaço de armazenamento muito maior, mas latência muito maior, normalmente cerca de 1000 vezes mais lenta do que uma perda de cache para um valor na RAM . Embora originalmente motivado para criar a impressão de maior quantidade de memória disponível do que a realmente disponível, a memória virtual é mais importante no uso contemporâneo por sua compensação de tempo-espaço e permitindo o uso de máquinas virtuais . As perdas de cache da memória principal são chamadas de falhas de página e incorrem em enormes penalidades de desempenho nos programas.
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
- David May FRS, um cientista da computação britânico e atualmente professor de Ciência da Computação na University of Bristol e fundador e CTO da XMOS Semiconductor , acredita que um dos problemas é que existe uma dependência da lei de Moore para resolver ineficiências. Ele apresentou uma 'alternativa' à lei de Moore (lei de maio ) declarada da seguinte forma:
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
- Análise de algoritmos - como determinar os recursos necessários para um algoritmo
- Codificação aritmética - uma forma de codificação de entropia de comprimento variável para compressão de dados eficiente
- Matriz associativa - uma estrutura de dados que pode se tornar mais eficiente usando árvores Patricia ou matrizes Judy
- Benchmark - um método para medir tempos de execução comparativos em casos definidos
- Melhor, pior e médio caso - considerações para estimar os tempos de execução em três cenários
- Algoritmo de pesquisa binária - uma técnica simples e eficiente para pesquisar matrizes classificadas
- Tabela de ramificação - uma técnica para reduzir o comprimento do caminho de instrução, o tamanho do código de máquina (e muitas vezes também a memória)
- Comparação de paradigmas de programação - considerações de desempenho específicas do paradigma
- Otimização do compilador - otimização derivada do compilador
- Complexidade computacional de operações matemáticas
- Teoria da complexidade computacional
- Desempenho do computador - métricas de hardware de computador
- Compressão de dados - reduzindo a largura de banda de transmissão e armazenamento em disco
- Índice de banco de dados - uma estrutura de dados que melhora a velocidade das operações de recuperação de dados em uma tabela de banco de dados
- Codificação de entropia - codificando dados de forma eficiente usando a frequência de ocorrência de strings como um critério para substituição
- Coleta de lixo - liberação automática de memória após o uso
- Computação verde - um movimento para implementar tecnologias 'mais verdes', consumindo menos recursos
- Algoritmo de Huffman - um algoritmo para codificação de dados eficiente
- Melhorando o desempenho do código gerenciado - Biblioteca MSDN da Microsoft
- Localidade de referência - para evitar atrasos de armazenamento em cache causados por acesso à memória não local
- Otimização de loop
- Gerenciamento de memória
- Otimização (ciência da computação)
- Análise de desempenho - métodos de medição do desempenho real de um algoritmo em tempo de execução
- Computação em tempo real - outros exemplos de aplicativos críticos para o tempo
- Análise de tempo de execução - estimativa de tempos de execução esperados e escalabilidade de um algoritmo
- Multithreading simultâneo
- Algoritmo de classificação § Comparação de algoritmos
- Execução especulativa ou execução ansiosa
- Previsão de filial
- Super-threading
- Código encadeado - semelhante à tabela de método virtual ou tabela de ramificação
- Tabela de método virtual - tabela ramificada com ponteiros atribuídos dinamicamente para despacho