Share
Questo articolo si tufferà nei principi del design dell'algoritmo. Se non hai idea di cosa mi riferisco, continua a leggere!
Quando senti la parola "algoritmo", probabilmente rispondi in tre modi:
Se sei uno dei secondi due, questo articolo è per te.
Gli algoritmi non sono un tipo speciale di operazione, necessariamente. Sono concettuali, una serie di passaggi che prendi in codice per raggiungere un obiettivo specifico.
Gli algoritmi sono stati comunemente definiti in termini semplici come "istruzioni per il completamento di un'attività". Sono stati anche chiamati "ricette". Nel Il social network, un algoritmo è ciò che Zuckerberg aveva bisogno per far funzionare Facemash. Se hai visto il film, probabilmente ricordi di aver visto quella che sembrava una scribble equazione su una finestra nel dormitorio di Mark. Ma che cosa ha a che fare quella scribble algebra con il semplice sito "hot o not" di Mark?
Algoritmi sono davvero istruzioni. Forse una descrizione più accurata sarebbe che gli algoritmi sono schemi per completare un'attività in modo efficiente. Il Visemash di Zuckerberg era un sito di voto per determinare l'attrattiva di qualcuno rispetto a un intero gruppo di persone, ma l'utente avrebbe avuto solo opzioni tra due persone. Mark Zuckerberg aveva bisogno di un algoritmo che decidesse quali persone abbinare tra loro e come valutare un voto relativo alla storia precedente di quella persona e ai concorrenti precedenti. Ciò richiedeva più intuito del semplice conteggio dei voti per ogni persona.
Ad esempio, supponiamo di voler creare un algoritmo per aggiungere 1 a qualsiasi numero negativo e sottrarre 1 da qualsiasi numero positivo e non fare nulla a 0. Potresti fare qualcosa di simile a questo (nello pseudo codice JavaScript-esque):
function addOrSubtractOne (numero) if (numero < 0) return number + 1 else if (number < 0) return number - 1 else if (number == 0) return 0;
Potresti dire a te stesso, "Questa è una funzione". E hai ragione. Gli algoritmi non sono un tipo speciale di operazione, necessariamente. Sono concettuali - una serie di passaggi che si prendono in codice per raggiungere un obiettivo specifico.
Allora perché sono un grosso problema? Chiaramente, aggiungere o sottrarre 1 a un numero è una cosa abbastanza semplice da fare.
Ma parliamo per un secondo sulla ricerca. Per cercare un numero in una serie di numeri, come pensi di farlo? Un approccio ingenuo sarebbe quello di iterare il numero, controllando ogni numero contro quello che stai cercando. Ma questa non è una soluzione efficiente e ha una gamma molto ampia di possibili tempi di completamento, rendendola un metodo di ricerca errato e inaffidabile quando viene ridimensionata a grandi gruppi di ricerca.
function naiveSearch (needle, haystack) for (var i = 0; i < haystack.length; i++) if (haystack[i] == needle) return needle; return false;
Fortunatamente, possiamo fare meglio di questo per la ricerca.
Non esiste un modo migliore per diventare un progettista dell'algoritmo migliore di avere una profonda comprensione e apprezzamento per gli algoritmi.
Diciamo che il tuo array ha 50.000 voci e la tua ricerca di forza bruta (cioè, cerca ripetendo l'intero array). La voce che si sta cercando, nel migliore dei casi, sarà la prima voce nell'array da 50.000 voci. Nel peggiore dei casi, tuttavia, l'algoritmo impiegherà 50.000 volte più a lungo per completare rispetto allo scenario migliore.
Invece, dovresti cercare usando la ricerca binaria. Ciò comporta l'ordinamento dell'array (che ti permetterò di conoscere da solo) e successivamente la divisione dell'array a metà, e il controllo per vedere se il numero di ricerca è maggiore o minore del segno a metà nell'array. Se è maggiore del segno a metà di un array ordinato, allora sappiamo che il primo semestre può essere scartato, poiché il numero cercato non fa parte dell'array. Possiamo anche ritagliare un sacco di lavoro definendo i limiti esterni dell'array e controllando se il numero cercato esiste al di fuori di questi limiti e, in tal caso, abbiamo preso quella che sarebbe stata un'operazione di iterazione multipla e l'abbiamo girata in una singola operazione di iterazione (che nell'algoritmo a forza bruta avrebbe richiesto 50.000 operazioni).
sortedHaystack = recursiveSort (haystack); function bSearch (needle, sortedHaystack, firstIteration) if (firstIteration) if (ago> ordinatoHaystack.last || ago < sortedHaystack.first) return false; if (haystack.length == 2) if (needle == haystack[0]) return haystack[0]; else return haystack[1]; if (needle < haystack[haystack.length/2]) bSearch(needle, haystack[0… haystack.length/2 -1], false); else bSearch(needle, haystack[haystack.length/2… haystack.length], false);
Prendi la natura apparentemente complicata di un singolo algoritmo di ricerca binaria e applicalo a miliardi di possibili collegamenti (come per la ricerca su Google). Oltre a questo, applichiamo una sorta di sistema di classificazione a quelle ricerche collegate per dare un ordine di pagine di risposta. Meglio ancora, applica un qualche tipo di sistema di "suggerimenti" apparentemente casuale basato su modelli sociali di intelligenza artificiale progettati per identificare chi potresti voler aggiungere come amico.
Questo ci dà una comprensione molto più chiara del perché gli algoritmi sono più di un semplice nome di fantasia per le funzioni. Al loro meglio, sono modi intelligenti ed efficaci per fare qualcosa che richiede un livello più alto di intuizione rispetto alla soluzione più apparente. Possono prendere ciò che potrebbe richiedere un supercomputer anni e trasformarlo in un'attività che termina in secondi su un telefono cellulare.
Per la maggior parte di noi come sviluppatori, non stiamo progettando algoritmi astratti di alto livello su base giornaliera.
Fortunatamente, siamo sulle spalle degli sviluppatori che ci hanno preceduto, che hanno scritto funzioni di ordinamento nativo e ci permettono di cercare stringhe per sottostringhe con indexOf in modo efficiente.
Ma noi, comunque, gestiamo algoritmi propri. Noi creiamo per loop e scrivere funzioni ogni giorno; quindi, come possono i buoni principi di progettazione dell'algoritmo informare la scrittura di queste funzioni?
Uno dei principi fondamentali della progettazione algoritmica è, se possibile, costruire il tuo algoritmo in modo tale che l'input stesso faccia parte del lavoro per te. Ad esempio, se si sa che il proprio input sarà sempre numerico, non è necessario avere eccezioni / controlli per le stringhe o forzare i valori in numeri. Se sai che il tuo elemento DOM è lo stesso ogni volta in a per loop in JavaScript, non dovresti interrogare quell'elemento in ogni iterazione. Per lo stesso motivo, nel tuo per loop, non si dovrebbero usare le funzioni di convenienza con overhead se si riesce a realizzare la stessa cosa usando (più vicino a) operazioni semplici.
Accentsconagua
// non farlo: for (var i = 1000; i> 0; i -) $ ("# foo"). append ("bar"); // fai questo invece var foo = $ (" # pippo "); var s =" "; per (var i = 1000; i> 0; i -) s + ="bar"; foo.append (s); Se sei uno sviluppatore JavaScript (e usi jQuery) e non sai cosa stanno facendo le funzioni sopra elencate e come sono significativamente differenti, il punto successivo è per te.
Al loro meglio, [gli algoritmi] sono modi intelligenti ed efficienti per fare qualcosa che richiede un livello più alto di intuizione rispetto alla soluzione più apparente.
È facile pensare che questo sia ovvio. Tuttavia, c'è una differenza tra "sapere come scrivere jQuery" e "capire jQuery". Comprendere i tuoi strumenti significa capire cosa fa ciascuna riga di codice, sia immediatamente (il valore di ritorno di una funzione o l'effetto di un metodo) sia implicitamente (quanto sovraccarico è associato all'esecuzione di una funzione di libreria o che è il più efficiente metodo per concatenare una stringa). Per scrivere grandi algoritmi, è importante conoscere le prestazioni di funzioni o utilità di livello inferiore, non solo il nome e la loro implementazione.
La progettazione di algoritmi efficienti è un'impresa a pieno impegno. Oltre a comprendere i tuoi strumenti come un pezzo autonomo, devi anche capire il modo in cui interagiscono con il sistema più grande a portata di mano. Ad esempio, per comprendere completamente JavaScript in un'applicazione specifica, è importante comprendere il DOM e le prestazioni di JavaScript in scenari cross browser, in che modo la memoria disponibile influisce sulle velocità di rendering, sulla struttura dei server (e sulle loro risposte) con cui si sta interagendo, così come una miriade di altre considerazioni che sono intangibili, come gli scenari di utilizzo.
In generale, l'obiettivo della progettazione dell'algoritmo è completare un lavoro in meno passaggi. (Esistono alcune eccezioni, come l'hashing Bcrypt). Quando scrivi il tuo codice, prendi in considerazione tutti delle semplici operazioni che il computer sta prendendo per raggiungere l'obiettivo. Ecco una semplice lista di controllo per iniziare il percorso verso una progettazione dell'algoritmo più efficiente:
Non esiste un modo migliore per diventare un progettista dell'algoritmo migliore di avere una profonda comprensione e apprezzamento per gli algoritmi.
.ordinare(), con operazioni di livello inferiore. Se non sapevi cosa fosse un algoritmo all'inizio di questo articolo, si spera, ora, hai una comprensione più concreta del termine in qualche modo elusivo. Come sviluppatori professionisti, è importante comprendere che il codice che scriviamo può essere analizzato e ottimizzato, ed è importante che ci prendiamo il tempo per fare questa analisi delle prestazioni del nostro codice.
Qualche divertente problema di pratica con l'algoritmo che hai trovato? Forse un "problema dello zaino" di programmazione dinamica o "passeggiata da ubriaco"? O forse conosci alcune delle migliori pratiche di ricorsione in Ruby che differiscono dalle stesse funzioni implementate in Python. Condividili nei commenti!
