Quais algoritmos são usados com mais frequência?
Escreva um único algoritmo por resposta, tente manter sua resposta curta (uma ou duas linhas).
ds.algorithms
big-list
Kaveh
fonte
fonte
Respostas:
A transformação rápida de Fourier é o problema algorítmico resolvido na maioria das vezes por dia por sistemas de computador reais? Tem que estar perto. Então, eu nomearia o algoritmo Cooley-Tukey FFT .
fonte
Multiplicação.
Talvez um dos algoritmos não inteiramente triviais mais antigos e um problema resolvido com mais frequência do que a FFT.
fonte
Algoritmos de caminho mais curto de Dijkstra e Bellman-Ford . Existem pelo menos 35.000 sistemas autônomos (AS) ativos na Internet a partir de 2010. Cada AS está executando um protocolo de roteamento de estado de link (Dijkstra) ou um protocolo de roteamento de vetor de distância (Bellman-Ford). Os roteadores em um AS normalmente atualizam suas tabelas periodicamente a cada poucos minutos, digamos 10.
Assim, o número de execuções de Dijkstra e Bellman-Ford por dia é de pelo menos 5 milhões. E isso é apenas dos roteadores.
Não contamos os cálculos de caminho mais curto do Google Maps e os gostos que devem ser responsáveis por 10 vezes mais. Meio bilhão de execuções por dia não é exagero.
fonte
Ordenação rápida
fonte
Pesquisa binária
fonte
Eu acho que o algoritmo mais usado é o Parity Check (ou talvez o CRC ou algum tipo de código de correção de erros), porque eles aparecem em todos os acessos à RAM.
fonte
Algoritmo Simplex - isso ainda não é competitivo com os melhores métodos de pontos interiores? Nesse caso, tem que ser muito utilizado.
fonte
De maneira mais geral, você deve considerar os ganhadores do prêmio Kanellakis em busca de idéias que tenham peso teórico e prático.
fonte
Correspondência de expressão regular por conversão para autômatos finitos - acredito que grep funcione nessas linhas.
fonte
Primeira pesquisa de profundidade (DFS)
fonte
É difícil pensar em algoritmos mais amplamente utilizados do que aqueles nas implementações modernas do TCP : ou seja , evitar congestionamentos , retransmitir rapidamente . Embora isso dependa de como se determina o que atende aos critérios de um algoritmo ...
fonte
Eliminação Gaussiana Isso ainda é usado na prática, certo? Caso contrário, substitua pelo que for usado com mais frequência para resolver sistemas lineares ...
fonte
SHA-1 (e funções de hash em geral). Provavelmente vença a maioria dos outros algoritmos em termos de número de execuções.
fonte
Algoritmos relacionados à árvore B + são usados para os materiais do banco de dados
fonte
Algoritmos de agendamento. Eles são usados por todos os dispositivos e servidores de usuários em todo o mundo. Várias variações estão sendo usadas. Encontrei muitas referências para "fila de feedback multinível"
fonte
Essa resposta interpreta "com mais frequência" em termos de ciclos reais da CPU.
Quando eu estava aprendendo computação nos anos 70, lembro-me de ler que a grande maioria dos ciclos de computadores (leia-se: mainframe) eram dedicados à classificação. Os aplicativos de negócios exigem uma ampla classificação para análise e geração de relatórios. Não imagino que isso tenha mudado muito, mas é claro que o surgimento de outros aplicativos - e-mail, processamento de texto etc. - deve ter alterado o mix. Essas classificações geralmente são estáveis (não o Quicksort) devido à necessidade de classificar sucessões de campos para criar sub-classificações.
Estritamente falando, porém, o algoritmo usado com mais freqüência é, sem dúvida, o que for executado pelo processo de espera do sistema Windows quando nada mais estiver acontecendo ;-).
fonte
Vetor de matriz de Sprase Multiply
... é o cavalo de batalha computacional por trás da solução de quase todos os sistemas lineares. Como resultado, ele está sendo executado sempre que
A maioria dos FLOPs em qualquer supercomputador ou cluster é gasta dentro de um mat-vec esparso.
fonte
Método de Newton. É usado para calcular raízes quadradas, para divisão de computação. Pode ser usado para fazer programação linear. Mais geralmente, é o cavalo de batalha da otimização (convexa). Ele pode ser usado para resolver equações diferenciais em Física, minimizando a ação / energia.
fonte
Hashing e vermelho-preto árvores.
Eles já estão implementados no STL (hash_map, map), e todo programador sabe que esse contêiner é incrivelmente conveniente sempre que você deseja armazenar algumas informações indexadas por um tipo de dados arbitrário.
fonte
Algoritmos de correção de erros, como Reed-Solomon.
http://en.wikipedia.org/wiki/Error-correcting_code#List_of_error-correcting_codes http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction
fonte
Programação Dinâmica .
Eu acho que o DP é usado "com mais frequência" do que outros algoritmos citados na pesquisa até agora. Eu deduzo "com mais frequência" no sentido de quantas vezes um conceito de algoritmo não trivial foi implementado pelo programador na vida real, e não por quanto tempo uma implementação específica de um algoritmo é invocada.
O DP é versátil e tem muitas faces. Às vezes, eu o usava um pouco subconscientemente e depois percebi que estava fazendo DP.
Obviamente, existem coisas que são ainda mais comuns que o Dynamic Program, mas na maior parte são estruturas de dados (matriz, lista vinculada, hash).
fonte
Correspondência de cadeias, usada o tempo todo no software aplicativo e no nível do banco de dados.
No caso exato, existem vários algoritmos bastante envolvidos (KMP, Boyer-Moore), com alguns que atingem o tempo de execução esperado sublinear. Eles também são interessantes para estudar do ponto de vista do CS.
A correspondência aproximada de cadeias, ou seja, alinhamentos, é provavelmente ainda mais interessante. Você conhece os recursos de "correção automática"? Além disso, as pesquisas em dados de seqüência ruidosa (por exemplo, DNA) são feitas usando alinhamentos.
fonte