Algoritmi di ordinamento sono una difficile combinazione di fondamentale necessario, e profondamente conflittuale. Dai nuovi ingegneri che cercano di impressionare in un’intervista agli ingegneri più anziani alla ricerca di una soluzione per un database in rapida scala, ci sono una miriade di fattori da prendere in considerazione. Qual è la velocità di confronto tra due oggetti? Qual è l’ora dello scambio? Quanto è grande il database? Che tipo di oggetti contiene? È già semi-ordinato? I risultati devono essere stabili?

Ognuna di queste domande può trarre argomenti a favore di un algoritmo o di un altro. I dati di origine sono grandi e complessi? La maggior parte delle lingue è predefinita allo standard, Ordinamento rapido con la sua complessità temporale O (n log n). È più piccolo? L’ordinamento di inserimento fa miracoli su quelli. Per lo più ordinati? Diamine, Bubble Sort potrebbe quasi funzionare per questo. Se vuoi leggere / visualizzare i meriti di ciascuno, dai un’occhiata a questo confronto toptal.com.

Un algoritmo di ordinamento che non troverai su quel sito, o quasi su qualsiasi altro, è Tim Sort. Questo tipo oscuro è attualmente unico per Python e viene utilizzato come algoritmo di ordinamento predefinito. Chiamaarray.sort in Python, e Tim Sort è ciò che viene eseguito. Nonostante questo, è raro trovare ingegneri che conoscono e capiscono Tim Sort. Quindi: che cos’è?

Tim Sort è stato implementato per la prima volta nel 2002 da Tim Peters per l’uso in Python. Presumibilmente proveniva dalla comprensione che la maggior parte degli algoritmi di ordinamento sono nati nelle aule scolastiche e non progettati per l’uso pratico sui dati del mondo reale. Tim Sort sfrutta i modelli comuni nei dati e utilizza una combinazione di Merge Sort e Insertion Sort insieme a una logica interna per ottimizzare la manipolazione di dati su larga scala.

Perché Tim Sorta?

Guardando la figura 2, possiamo immediatamente vedere qualcosa di interessante. Al suo meglio, Tim Sort supera Merge Sort e Quick Sort. Nel peggiore dei casi, funziona a velocità comparabili Merge Sort e in realtà supera Quick Sort. In altre parole, è inaspettatamente veloce.

In termini di spazio, Tim Sort è all’estremità peggiore dello spettro, ma la considerazione dello spazio per la maggior parte degli algoritmi di ordinamento è piuttosto scarsa. O (n) non è troppo ruvido nella maggior parte dei casi; vale la pena notare come una possibile carenza, e l’unico posto in cui Quick Sort supera davvero Tim Sort.

L’elemento finale su cui vengono spesso giudicati gli algoritmi di ordinamento è la stabilità. La stabilità è il concetto che, una volta ordinati, gli oggetti di uguale valore mantengono il loro ordine originale. Ora, si potrebbe chiedere perché ci preoccupiamo di questo. Gli articoli sono di uguale valore-perché ci preoccupiamo di come vengono ordinati?

La risposta semplice è che la stabilità è importante per i tipi impilati. Vale a dire, prima si ordina in base a un criterio, quindi in base a un secondo. Se lo fai in un algoritmo instabile, perdi immediatamente qualsiasi affidabilità dal tuo primo tipo quando esegui il secondo. Per riferimento, l’ordinamento rapido è instabile e l’ordinamento di unione è stabile.

Tim Sort è anche stabile, per non parlare veloce se leggermente pesante(rispetto al solo Ordinamento rapido). Mentre gli algoritmi di ordinamento possono (e dovrebbero) essere giudicati su altre considerazioni, questi sono i tre grandi.

L’implementazione in tre fasi

Tim Sort è complessa, anche per standard algoritmici. L’implementazione è meglio suddivisa in parti.

Binary Search

La prima cosa di cui hai bisogno per implementare un Tim Sort è un metodo di ricerca binario. Questo è solo usato per implementare il tuo ordinamento di inserimento in seguito.

Per riferimento: Algoritmi di ricerca binari

Insertion Sort& Merge Sort

In secondo luogo, è necessario codificare l’ordinamento di inserimento e l’ordinamento di unione. Questi sono algoritmi familiari, e dovrebbero essere nella tasca posteriore della maggior parte degli ingegneri, ma andremo oltre i fondamenti di come funzionano e perché sono preziosi per noi qui.

Insertion Sort è molto semplice algoritmo di ordinamento. Attraversa l’array e ogni volta che incontra un elemento fuori servizio (rigorosamente meno/più dell’elemento precedente), lo sposta nella posizione appropriata nell’array già ordinato. L’ordinamento di inserimento è noto per lavorare molto rapidamente su array già ordinati, così come su array più piccoli. In effetti, possiamo vedere dalla Fig 2 che l’ordinamento di inserimento ha un impressionante tempo di esecuzione del caso migliore di O (n). Tieni presente di andare avanti con Tim Sort: il caso migliore per l’ordinamento di inserimento è un array già ordinato. Potrebbe sembrare sciocco, ma questo sarà rilevante.

Merge Sort invece opera in base a un principio di base: è fin troppo facile unire già ordinato le matrici. Quindi, divide un array iniziale a metà più e più volte finché non è nient’altro che singoli elementi. Quindi ricostruisce lentamente l’array principale unendo quegli elementi in ordine ordinato. Poiché siamo partiti da elementi costitutivi di dimensione uno, è stato molto facile creare array ordinati iniziali. Quindi, è facile unirli. Alla fine, passiamo il tempo O(n log n) e (cosa importante) lo facciamo in un modo che è garantito per essere stabile.

Per esempio implementazioni vedere:

Merge Sort: https://www.geeksforgeeks.org/merge-sort/

Insertion Sort: https://www.geeksforgeeks.org/insertion-sort/

Implementare Tim Sort

La chiave per comprendere l’implementazione di Tim Sort è capire il suo uso di esecuzioni. Tim Sort sfrutta i dati presortati presenti in natura a suo vantaggio. Con presorted intendiamo semplicemente che gli elementi sequenziali sono tutti in aumento o in diminuzione (non ci interessa quale).

Per prima cosa impostiamo una dimensioneminrun. Ciò che intendiamo con questo è che vogliamo garantire che tutte le nostre corse siano almeno di una certa lunghezza. Si prega di notare che non stiamo garantendo che troveremo piste di queste dimensioni — entreremo in questo più tardi. Stiamo semplicemente dicendo che una corsa deve essere almeno di una certa lunghezza.

Quando incontriamo una corsa, la mettiamo da parte. Quando troviamo la corsa più lunga all’interno di un intervallo minrun. Ora abbiamo una struttura dati familiare: un piccolo array ordinato. Se è almenominrun in lunghezza, allora huzzah! Possiamo andare avanti. Se non lo è, mettiamo in gioco l’inserimento.

Potresti ricordare dall’alto che l’ordinamento di inserimento è particolarmente efficace su due tipi di array: quelli piccoli e quelli già ordinati. Quello che abbiamo appena fatto è un piccolo array ordinato. Se non è almenominrun in lunghezza, arriviamo avanti e prendiamo abbastanza altri elementi per completare la corsa, quindi usiamo l’ordinamento di inserimento per spingerli nel nostro array ordinato, veloce e facile. Ovviamente, se una corsa incontra la fine dell’array, puoi lasciarlo un po ‘ corto.

Una volta che hai creato tutte le tue corse (cioè i sottoarray ordinati), utilizzi il tuo Ordinamento di unione per unirle insieme. Nel migliore dei casi l’intero array è già ordinato e Tim Sort è abbastanza intelligente da sapere che non ha bisogno di fare altro. Altre volte, tende ad essere solo estremamente efficiente. Come ulteriore vantaggio, sia l’ordinamento di inserimento che l’ordinamento di unione sono stabili, quindi l’array risultante è stabile.

Per coloro che preferiscono i proiettili:

1. Stabilire una dimensioneminrun che è una potenza di 2 (di solito 32, mai più di 64 o il tuo tipo di inserimento perderà efficienza)
2. Trova una corsa nel primominrun di dati.
3. Se la corsa non è almeno minrun in lunghezza, utilizzare Insertion Sort per afferrare gli elementi successivi o precedenti e inserirli nella corsa fino a quando non è la dimensione minima corretta.
4. Ripetere fino a quando l’intero array è diviso in sottosezioni ordinate.
5. Usa la seconda metà di Merge Sort per unire gli array ordinati.

Conclusione

Tim Sort è potente. È veloce e stabile, ma forse la cosa più importante sfrutta i modelli del mondo reale e li utilizza per costruire un prodotto finale. È per ogni situazione? Probabilmente no. Buona fortuna programmarlo su una lavagna durante un’intervista, e se hai solo bisogno di un semplice algoritmo di ordinamento rapido in un pizzico probabilmente non vuoi preoccuparti di implementare qualcosa di questo complesso. Tuttavia, per gli scienziati di dati scricchiolio numeri è più che la pena dare un’occhiata.

Per i curiosi, è possibile controllare l’intero codice di ordinamento Tim su github.

Grazie

Grazie a tutti i miei lettori. Apprezzo il vostro tempo, e sinceramente spero che hai trovato il contenuto informativo. Se avete domande o risposte non esitate a cadere uno qui sotto.