Seu algoritmo favorito e a lição que ele lhe ensinou [fechado]

https://stackoverflow.com/questions/26301

09-06-2019
|

Pergunta

Qual algoritmo lhe ensinou mais sobre programação ou sobre um recurso específico da linguagem?

Todos nós já tivemos aqueles momentos em que, de repente, sabemos, apenas sabemos, que aprendemos uma lição importante para o futuro, baseada na compreensão final de um algoritmo escrito por um programador alguns degraus acima na escada evolutiva.Quais ideias e códigos tiveram o toque mágico em você?

Solução

“Iterar é humano, recorrer é divino” - citado em 1989 na faculdade.

P.S.Postado por Woodgnome enquanto aguarda o convite para participar

Outras dicas

Algoritmos gerais:

Quicksort (e sua análise de complexidade média) mostra que randomizar sua entrada pode ser uma coisa boa!;
árvores equilibradas (Árvores AVL por exemplo), uma maneira elegante de equilibrar os custos de pesquisa/inserção;
Dijkstra e Ford-Fulkerson algoritmos em gráficos (gosto do fato do segundo ter muitas aplicações);
a família LZ* de algoritmos de compressão (LZW por exemplo), a compactação de dados parecia mágica para mim até que eu a descobri (há muito tempo :));
o FFT, onipresente (reutilizado em tantos outros algoritmos);
o simples algoritmo, onipresente também.

Relacionado a números:

Algoritmo de Euclides para calcular o mdc de dois inteiros:um dos primeiros algoritmos, simples e elegante, poderoso, tem muitas generalizações;
multiplicação rápida de inteiros (Cooley-Tukey por exemplo);
Iterações de Newton para inverter/encontrar uma raiz, um meta-algoritmo muito poderoso.

Relacionado à teoria dos números:

Assembleia Geral Anualalgoritmos relacionados (exemplos):leva a algoritmos muito simples e elegantes para calcular pi (e muito mais!), embora a teoria seja bastante profunda (Gauss introduziu funções elípticas e formas modulares a partir dela, então pode-se dizer que deu origem à geometria algébrica...);
o peneira de campo numérico (para fatoração de inteiros): muito complicado, mas um resultado teórico bastante bom (isso também vale para o AKS algoritmo, que provou que PRIMES está em P).

Também gostei de estudar computação quântica (Curto e Deutsch-Josza algoritmos, por exemplo):isso ensina você a pensar fora da caixa.

Como você pode ver, sou um pouco inclinado a algoritmos orientados para matemática :)

Algoritmo de caminhos mais curtos de todos os pares Floyd-Warshall

procedure FloydWarshall ()
   for k := 1 to n
     for i := 1 to n
        for j := 1 to n
          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

Veja por que é legal:quando você aprende sobre o problema do caminho mais curto em seu curso de teoria dos grafos, provavelmente começa com o algoritmo de Dijkstra que resolve solteiro-source caminho mais curto.É bastante complicado no começo, mas depois você supera e entende completamente.

Então o professor diz: "Agora queremos resolver o mesmo problema, mas por TODOS fontes".Você pensa consigo mesmo: “Oh Deus, isso vai ser um problema muito mais difícil! Vai ser pelo menos N vezes mais complicado que o algoritmo de Dijkstra!!!".

Então o professor lhe dá Floyd-Warshall.E sua mente explode.Então você começa a se surpreender com o quão simples é o algoritmo.É apenas um loop triplamente aninhado.Ele usa apenas um array simples para sua estrutura de dados.

A parte mais reveladora para mim é a seguinte constatação:digamos que você tenha uma solução para o problema A.Então você tem um “superproblema” B maior que contém o problema A.A solução do problema B pode de fato ser mais simples do que a solução do problema A.

Ordenação rápida.Isso me mostrou que a recursão pode ser poderosa e útil.

Este pode parecer trivial, mas foi uma revelação para mim na época.Eu estava na minha primeira aula de programação (VB6) e o Prof tinha acabado de nos ensinar sobre números aleatórios e deu as seguintes instruções:"Crie uma máquina de loteria virtual.Imagine uma bola de vidro cheia de 100 bolas de pingue-pongue marcadas de 0 a 99.Escolha-os aleatoriamente e exiba seu número até que todos tenham sido selecionados, sem duplicatas."

Todos os outros escreveram seus programas assim:Escolha uma bola, coloque seu número em uma “lista já selecionada” e depois escolha outra bola.Verifique se já está selecionada, se sim escolha outra bola, se não coloque seu número na "lista de já selecionadas" etc....

É claro que no final eles estavam fazendo centenas de comparações para encontrar as poucas bolas que ainda não haviam sido escolhidas.Foi como jogar as bolas de volta na jarra depois de selecioná-las.Minha revelação foi jogar as bolas fora depois de colhê-las.

Eu sei que isso parece óbvio, mas foi nesse momento que a "chave de programação" foi acionada na minha cabeça.Este foi o momento em que a programação deixou de tentar aprender uma língua estrangeira estranha e passou a tentar resolver um quebra-cabeça divertido.E uma vez que fiz essa conexão mental entre programação e diversão, realmente não havia como me parar.

A codificação Huffman seria minha, eu originalmente fiz minha própria versão idiota, minimizando o número de bits para codificar o texto de 8 para menos, mas não tinha pensado no número variável de bits dependendo da frequência.Então encontrei a codificação huffman descrita em um artigo de uma revista e ela me abriu muitas novas possibilidades.

Algoritmo de desenho de linha de Bresenham me interessou pela renderização de gráficos em tempo real.Isso pode ser usado para renderizar polígonos preenchidos, como triângulos, para coisas como renderização de modelos 3D.

Análise de descida recursiva - Lembro-me de ter ficado muito impressionado como um código tão simples poderia fazer algo aparentemente tão complexo.

Classificação rápida em Haskell:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Embora eu não soubesse escrever Haskell na época, entendi esse código e com ele a recursão e o algoritmo quicksort.Apenas fez um clique e lá estava...

O algoritmo iterativo para Fibonacci, porque para mim ele acertou em cheio o fato de que o código mais elegante (neste caso, a versão recursiva) não é necessariamente o mais eficiente.

Para elaborar: A abordagem "fib(10) = fib(9) + fib(8)" significa que fib(9) será avaliada como fib(8) + fib(7).Portanto, a avaliação de fib(8) (e, portanto, fib7, fib6) será avaliada duas vezes.

O método iterativo (curr = prev1 + prev2 em um forloop) não arboriza dessa maneira, nem ocupa tanta memória, pois são apenas 3 variáveis transitórias, em vez de n quadros na pilha de recursão.

Costumo me esforçar por um código simples e elegante quando estou programando, mas esse é o algoritmo que me ajudou a perceber que esse não é o fim de tudo para escrever um bom software e que, em última análise, os usuários finais não o fazem. não me importo com a aparência do seu código.

Por alguma razão eu gosto do Transformada Schwartziana

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
                @unsorted;

Onde foo($) representa uma expressão de uso intensivo de computação que leva $ (cada item da lista por vez) e produz o valor correspondente que deve ser comparado.

Minimáximo me ensinou que os programas de xadrez não são inteligentes, eles podem apenas pensar em mais jogadas à frente do que você.

Não sei se isso se qualifica como um algoritmo ou apenas um hack clássico.Em ambos os casos, ajudou-me a começar a pensar fora da caixa.

Troque 2 inteiros sem usar uma variável intermediária (em C++)

void InPlaceSwap (int& a, int &b) {
     a ^= b;
     b ^= a;
     a ^= b;
}

Ordenação rápida:Até chegar à faculdade, nunca havia questionado se o Bubble Sort de força bruta era a maneira mais eficiente de classificar.Parecia intuitivamente óbvio.Mas ser exposto a soluções não óbvias como o Quicksort me ensinou a ignorar as soluções óbvias para ver se algo melhor está disponível.

Para mim, é o algoritmo de heapsort fraco porque mostra (1) o quanto uma estrutura de dados escolhida com sabedoria (e os algoritmos que trabalham nela) pode influenciar o desempenho e (2) que coisas fascinantes podem ser descobertas mesmo em sistemas antigos e bem conhecidos. coisas.(weak-heapsort é a melhor variante de todos os tipos de heap, que foi comprovado oito anos depois.)

Este é lento :)

Aprendi muito sobre C e computadores em geral, entendendo Dispositivo Duffs e Trocas XOR

EDITAR:

@Jasão Z, essa é minha troca XOR :) legal, não é?

Por alguma razão, o Bubble Sort sempre se destacou para mim.Não porque seja elegante ou bom, apenas porque tinha/tem um nome bobo, suponho.

Eu não tenho um favorito - há tantos lindos para escolher - mas um que sempre achei intrigante é o Fórmula Bailey-Borwein-Plouffe (BBP), que permite calcular um dígito arbitrário de pi sem conhecimento sobre os dígitos anteriores.

RSA me apresentou ao mundo da aritmética modular, que pode ser usada para resolver a surpreendente número de interessante problemas!

Não me ensinou muito, mas o Algoritmo Johnson-Trotter nunca deixa de me surpreender.

Diagramas de decisão binária, embora formalmente não seja um algoritmo, mas uma estrutura de dados, leva a soluções elegantes e mínimas para vários tipos de problemas lógicos (booleanos).Eles foram inventados e desenvolvidos para minimizar a contagem de portas no design de chips e podem ser vistos como um dos fundamentos da revolução do silício.Os algoritmos resultantes são incrivelmente simples.

O que eles me ensinaram:

uma representação compacta de qualquer o problema é importante;Pequeno é bonito
um pequeno conjunto de restrições/reduções aplicadas recursivamente pode ser usado para realizar isso
para problemas com simetrias, a transformação para uma forma canônica deve ser o primeiro passo a considerar
nem toda obra literária é lida.Knuth descobriu o BDD vários anos após sua invenção/introdução.(e passou quase um ano investigando-os)

Para mim, a simples troca na Kelly & Pohl's Um livro sobre C para demonstrar a chamada por referência me surpreendeu quando o vi pela primeira vez.Eu olhei para isso e os ponteiros se encaixaram.Literalmente...

void swap(int *p, int *q)
{
   int temp;

   temp = *p;
   *p = *q;
   *q = temp;
}

O Algoritmo das Torres de Hanói é um dos algoritmos mais bonitos.Mostra como você pode usar a recursão para resolver um problema de uma forma muito mais elegante do que o método iterativo.

Alternativamente, o algoritmo de recursão para a série de Fibonacci e o cálculo de potências de um número demonstram a situação inversa do algoritmo recursivo sendo usado por causa da recursão em vez de fornecer um bom valor.

O algoritmo iterativo para Fibonacci, porque para mim ele acertou em cheio o fato de que o código mais elegante (neste caso, a versão recursiva) não é necessariamente o mais eficiente.

O método iterativo (curr = prev1 + prev2 em um forloop) não arboriza dessa maneira, nem ocupa tanta memória, pois são apenas 3 variáveis transitórias, em vez de n quadros na pilha de recursão.

Você sabe que fibonacci possui uma solução de formato fechado que permite o cálculo direto do resultado em um número fixo de etapas, certo?Ou seja, (phiⁿ - (1 - fi)ⁿ) /sqrt(5).Sempre me pareceu algo notável que isso rendesse um número inteiro, mas isso acontece.

phi é a proporção áurea, claro;(1 + quadrado(5)) / 2.

Um algoritmo que gera uma lista de primos comparando cada número com a lista atual de primos, adicionando-o se não for encontrado e retornando a lista de primos no final.Alucinante de várias maneiras, entre as quais a ideia de usar o resultado parcialmente concluído como critério de pesquisa principal.

Armazenar dois ponteiros em uma única palavra para uma lista duplamente vinculada me ensinou a lição de que você pode realmente fazer coisas muito ruins em C (com as quais um GC conservador terá muitos problemas).

O maior orgulho que tive de uma solução foi escrever algo muito semelhante ao pacote DisplayTag.Isso me ensinou muito sobre design, manutenção e reutilização de código.Eu o escrevi bem antes do DisplayTag, e ele foi firmado em um acordo de NDA, então não pude abri-lo, mas ainda posso falar com entusiasmo sobre isso em entrevistas de emprego.

Mapear/Reduzir.Dois conceitos simples que se encaixam para facilitar a paralelização de uma série de tarefas de processamento de dados.

Oh...e é apenas a base da indexação massivamente paralela:

http://labs.google.com/papers/mapreduce.html

Não é o meu favorito, mas o Algoritmo de Miller Rabin pois testar a primalidade me mostrou que estar certo quase o tempo todo é bom o suficiente quase o tempo todo.(ou seja,Não desconfie de um algoritmo probabilístico só porque ele tem probabilidade de estar errado.)

@Krishna Kumar

A solução bit a bit é ainda mais divertida que a solução recursiva.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow