Il tuo algoritmo preferito e la lezione che ti ha insegnato [chiuso]

https://stackoverflow.com/questions/26301

09-06-2019
|

Domanda

Quale algoritmo ti ha insegnato di più sulla programmazione o su una caratteristica specifica del linguaggio?

Abbiamo tutti avuto quei momenti in cui all'improvviso sappiamo, sappiamo e basta, di aver imparato un'importante lezione per il futuro basata sulla comprensione finalmente di un algoritmo scritto da un programmatore un paio di gradini sopra la scala evolutiva.Quali idee e codice hanno avuto il tocco magico su di te?

Soluzione

"Iterare è umano, ricorrere divino" - citato nel 1989 al college.

PSInserito da Woodgnome in attesa dell'invito a partecipare

Altri suggerimenti

Algoritmi generali:

Quicksort (e la sua analisi della complessità media), mostra che randomizzare il tuo input può essere una buona cosa!;
alberi equilibrati (Alberi AVL ad esempio), un modo accurato per bilanciare i costi di ricerca/inserimento;
Dijkstra E Ford-Fulkerson algoritmi su grafici (mi piace il fatto che il secondo abbia molte applicazioni);
la famiglia di algoritmi di compressione LZ* (LZW per esempio), la compressione dei dati mi sembrava una specie di magia finché non l'ho scoperta (molto tempo fa :));
IL FFT, onnipresente (riutilizzato in tanti altri algoritmi);
IL semplice algoritmo, anch'esso onnipresente.

Relativo numerico:

Algoritmo di Euclide per calcolare il mcd di due numeri interi:uno dei primi algoritmi, semplice ed elegante, potente, ha moltissime generalizzazioni;
moltiplicazione veloce di numeri interi (Cooley-Tukey Per esempio);
Iterazioni di Newton per invertire/trovare una radice, un meta-algoritmo molto potente.

Relativo alla teoria dei numeri:

Assemblea generale-algoritmi correlati (esempi):porta ad algoritmi molto semplici ed eleganti per calcolare pi greco (e molto altro!), sebbene la teoria sia piuttosto profonda (Gauss ha introdotto da essa le funzioni ellittiche e le forme modulari, quindi si può dire che ha dato vita alla geometria algebrica...);
IL setaccio del campo numerico (per la fattorizzazione di numeri interi): molto complicato, ma un risultato teorico piuttosto carino (questo vale anche per il AKS algoritmo, che ha dimostrato che PRIMES è in P).

Mi è piaciuto anche studiare l'informatica quantistica (Corto E Deutsch-Josza algoritmi ad esempio):questo ti insegna a pensare fuori dagli schemi.

Come puoi vedere, sono un po' prevenuto nei confronti degli algoritmi orientati alla matematica :)

Algoritmo dei percorsi più brevi di Floyd-Warshall per tutte le coppie

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] );

Ecco perché è bello:quando apprendi per la prima volta il problema del cammino minimo nel tuo corso di teoria dei grafi, probabilmente inizi con l'algoritmo di Dijkstra che risolve separare-percorso più breve dell'origine.All'inizio è piuttosto complicato, ma poi lo superi e lo capisci appieno.

Poi l'insegnante dice: "Ora vogliamo risolvere lo stesso problema ma per TUTTO fonti".Pensi tra te e te: "Oh Dio, questo sarà un problema molto più difficile! Sarà almeno N volte più complicato dell'algoritmo di Dijkstra!!!".

Poi l'insegnante ti dà Floyd-Warshall.E la tua mente esplode.Quindi inizi a piangere per quanto sia meravigliosamente semplice l'algoritmo.È solo un ciclo triplo annidato.Utilizza solo un semplice array per la sua struttura dati.

La parte più illuminante per me è la seguente realizzazione:diciamo che hai una soluzione per il problema A.Quindi hai un "superproblema" B più grande che contiene il problema A.La soluzione del problema B potrebbe infatti essere più semplice della soluzione del problema A.

Ordinamento rapido.Mi ha mostrato che la ricorsione può essere potente e utile.

Potrebbe sembrare banale, ma in quel momento per me fu una rivelazione.Ero al mio primo corso di programmazione (VB6) e il Prof ci aveva appena insegnato i numeri casuali e ci aveva dato le seguenti istruzioni:"Crea una macchina della lotteria virtuale.Immagina una pallina di vetro piena di 100 palline da ping pong contrassegnate da 0 a 99.Sceglili a caso e mostra il loro numero finché non sono stati tutti selezionati, senza duplicati."

Tutti gli altri hanno scritto il loro programma in questo modo:Scegli una pallina, inserisci il suo numero in una "lista già selezionata" e poi scegli un'altra pallina.Controlla se è già selezionata, in tal caso scegli un'altra pallina, in caso contrario inserisci il suo numero nella "lista già selezionata" ecc....

Naturalmente alla fine stavano facendo centinaia di confronti per trovare le poche palline che non erano già state scelte.Era come rimettere le palline nel barattolo dopo averle selezionate.La mia rivelazione è stata quella di buttare via le palline dopo averle raccolte.

So che sembra ovvio, ma questo è stato il momento in cui l'"interruttore di programmazione" è stato girato nella mia testa.Questo è stato il momento in cui la programmazione è passata dal tentativo di imparare una strana lingua straniera al tentativo di risolvere un puzzle divertente.E una volta stabilita la connessione mentale tra programmazione e divertimento, più nulla mi ha fermato.

La codifica di Huffman sarebbe stata mia, inizialmente avevo creato la mia versione stupida riducendo al minimo il numero di bit per codificare il testo da 8 a meno, ma non avevo pensato al numero di bit variabile a seconda della frequenza.Poi ho trovato la codifica Huffman descritta in un articolo su una rivista e mi ha aperto tantissime nuove possibilità.

Algoritmo di disegno al tratto di Bresenham mi ha interessato al rendering grafico in tempo reale.Questo può essere utilizzato per eseguire il rendering di poligoni pieni, come i triangoli, per cose come il rendering di modelli 3D.

Analisi di discesa ricorsiva - Ricordo di essere rimasto molto colpito da come un codice così semplice potesse fare qualcosa di così apparentemente complesso.

Ordinamento rapido in Haskell:

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

Sebbene all'epoca non potessi scrivere Haskell, capii questo codice e con esso la ricorsione e l'algoritmo Quicksort.Ha appena fatto clic ed eccolo lì...

L'algoritmo iterativo per Fibonacci, perché per me ha chiarito il fatto che il codice più elegante (in questo caso, la versione ricorsiva) non è necessariamente il più efficiente.

Per elaborare: l'approccio "fib(10) = fib(9) + fib(8)" significa che fib(9) verrà valutato come fib(8) + fib(7).Quindi la valutazione di fib(8) (e quindi fib7, fib6) verrà valutata due volte.

Il metodo iterativo (curr = prev1 + prev2 in un forloop) non si struttura in questo modo, né richiede tanta memoria poiché sono solo 3 variabili transitorie, invece di n frame nello stack di ricorsione.

Tendo a cercare un codice semplice ed elegante quando programmo, ma questo è l'algoritmo che mi ha aiutato a capire che questo non è il punto finale per scrivere un buon software e che alla fine gli utenti finali non lo fanno. Non mi interessa come appare il tuo codice.

Per qualche ragione mi piace il Trasformata di Schwartziana

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

Dove foo($) rappresenta un'espressione ad alta intensità di calcolo che accetta $ (ciascun elemento della lista a turno) e produce il valore corrispondente che deve essere confrontato a sua volta.

Minimassimo mi ha insegnato che i programmi di scacchi non sono intelligenti, possono semplicemente pensare più mosse in anticipo di te.

Non so se questo si qualifica come un algoritmo o semplicemente come un classico hack.In entrambi i casi, mi ha aiutato a iniziare a pensare fuori dagli schemi.

Scambia 2 numeri interi senza utilizzare una variabile intermedia (in C++)

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

Ordinamento rapido:Fino al college, non mi ero mai chiesto se il Bubble Sort con la forza bruta fosse il modo più efficiente per ordinare.Sembrava intuitivamente ovvio.Ma essere esposto a soluzioni non ovvie come Quicksort mi ha insegnato a guardare oltre le soluzioni ovvie per vedere se è disponibile qualcosa di meglio.

Per me è l'algoritmo di ordinamento dell'heap debole perché mostra (1) quanto una struttura dati scelta saggiamente (e gli algoritmi che lavorano su di essa) possono influenzare le prestazioni e (2) che cose affascinanti possono essere scoperte anche in vecchi e ben noti cose.(weak-heapsort è la migliore variante di tutti gli heap sort, che era provato otto anni dopo.)

Questo è lento :)

Ho imparato molto sia sul C che sui computer in generale grazie alla comprensione Dispositivo Duffs E Scambi XOR

MODIFICARE:

@Jason Z, questo è il mio scambio XOR :) bello, non è vero?

Per qualche motivo Bubble Sort mi ha sempre colpito.Non perché sia elegante o bello, solo perché aveva/ha un nome sciocco, suppongo.

Non ho un preferito -- ce ne sono così tanti belli tra cui scegliere -- ma quello che ho sempre trovato intrigante è il Formula Bailey-Borwein-Plouffe (BBP)., che consente di calcolare una cifra arbitraria di pi greco senza conoscere le cifre precedenti.

RSA mi ha fatto conoscere il mondo dell'aritmetica modulare, a cui può essere abituato risolvere UN sorprendente numero Di interessante i problemi!

Non mi ha insegnato molto, ma il Algoritmo di Johnson-Trotter non manca mai di lasciarmi a bocca aperta.

Diagrammi decisionali binari, sebbene formalmente non un algoritmo ma una struttura dati, porta a soluzioni eleganti e minimali per vari tipi di problemi logici (booleani).Sono stati inventati e sviluppati per ridurre al minimo il numero di porte nella progettazione dei chip e possono essere considerati uno dei fondamenti della rivoluzione del silicio.Gli algoritmi risultanti sono sorprendentemente semplici.

Cosa mi hanno insegnato:

una rappresentazione compatta di Qualunque il problema è importante;piccolo è bello
a tal fine è possibile utilizzare un piccolo insieme di vincoli/riduzioni applicati ricorsivamente
per problemi di simmetrie, la trasformazione in una forma canonica dovrebbe essere il primo passo da considerare
non tutti i brani letterari vengono letti.Knuth ha scoperto i BDD diversi anni dopo la loro invenzione/introduzione.(e ho trascorso quasi un anno a indagarli)

Per me, il semplice scambio da Kelly & Pohl Un libro su C dimostrare la chiamata per riferimento mi ha sconvolto quando l'ho visto per la prima volta.L'ho guardato e i puntatori sono scattati in posizione.Alla lettera...

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

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

IL Algoritmo delle Torri di Hanoi è uno degli algoritmi più belli.Mostra come utilizzare la ricorsione per risolvere un problema in un modo molto più elegante rispetto al metodo iterativo.

In alternativa, l’algoritmo ricorsivo per le serie di Fibonacci e le potenze di calcolo di un numero dimostrano la situazione inversa in cui l’algoritmo ricorsivo viene utilizzato per motivi di ricorsione invece di fornire un buon valore.

L'algoritmo iterativo per Fibonacci, perché per me ha chiarito il fatto che il codice più elegante (in questo caso, la versione ricorsiva) non è necessariamente il più efficiente.

Il metodo iterativo (curr = prev1 + prev2 in un forloop) non si struttura in questo modo, né richiede tanta memoria poiché sono solo 3 variabili transitorie, invece di n frame nello stack di ricorsione.

Sai che Fibonacci ha una soluzione in forma chiusa che consente il calcolo diretto del risultato in un numero fisso di passaggi, giusto?Vale a dire, (phi^N - (1 - phi)^N) /qrt(5).Mi sembra sempre piuttosto notevole che questo debba produrre un numero intero, ma lo fa.

phi è la sezione aurea, ovviamente;(1 + quadrato(5)) / 2.

Un algoritmo che genera un elenco di numeri primi confrontando ciascun numero con l'elenco corrente di numeri primi, aggiungendolo se non viene trovato e restituendo l'elenco di numeri primi alla fine.Stravolgente in diversi modi, non ultimo l'idea di utilizzare l'output parzialmente completato come criterio di ricerca principale.

Memorizzare due puntatori in una sola parola per un elenco doppiamente collegato mi ha insegnato la lezione che in C si possono fare davvero cose molto brutte (con le quali un GC conservatore avrà molti problemi).

La cosa più orgogliosa di cui sono stato di una soluzione è stata scrivere qualcosa di molto simile al pacchetto DisplayTag.Mi ha insegnato molto sulla progettazione, la manutenibilità e il riutilizzo del codice.L'ho scritto molto prima di DisplayTag ed era inserito in un accordo NDA, quindi non potevo renderlo open source, ma posso ancora parlarne in modo entusiastico durante i colloqui di lavoro.

Riduci mappa.Due semplici concetti che si combinano per semplificare la parallelizzazione di un sacco di attività di elaborazione dati.

OH...ed è solo la base dell'indicizzazione massivamente parallela:

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

Non il mio preferito, ma il Algoritmo di Miller Rabin perché testare la primalità mi ha mostrato che avere ragione quasi sempre è abbastanza buono quasi sempre.(cioè.Non diffidare di un algoritmo probabilistico solo perché ha una probabilità di sbagliarsi.)

@Krishna Kumar

La soluzione bit a bit è ancora più divertente della soluzione ricorsiva.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow