Introduzione
Julia, come la maggior parte dei linguaggi di programmazione, offre una grande varietà di tipi di collezione.
Alcune sono intrinsecamente ordinate (tra cui i Vectors e gli Arrays a più dimensioni), quindi possiamo accedere agli elementi in base alla posizione.
Altre collezioni non sono ordinate (Sets, Dicts) e per accedere agli elementi bisogna usare una chiave o un valore.
Nel caso più semplice, supponiamo di avere un Vector di Ints e di volerlo ordinare in ordine crescente.
julia> v = [3, 2, 4, 1]
4-element Vector{Int64}:
3
2
4
1
julia> sort(v)
4-element Vector{Int64}:
1
2
3
4
# sort descending
julia> sort(v, rev=true)
4-element Vector{Int64}:
4
3
2
1
Semplice!
La funzione sort() ha un nome ovvio e, a quanto pare, restituisce il Vector ordinato.
Scherzavo!
A questo punto del programma, forse sospetti (giustamente) che ci siano delle sfumature da discutere.
Funzioni mutanti e non mutanti
Dopo aver eseguito sort(v), cos'è v?
julia> v
4-element Vector{Int64}:
3
2
4
1
julia> issorted(v)
false
Il vettore originale non è cambiato.
sort() è una funzione non mutante che restituisce una copia del suo input.
In molti contesti è una buona scelta progettuale: abbiamo una funzione pura il cui comportamento è facile da capire e prevedere, anche in codice parallelo e distribuito.
D'altra parte, supponiamo di avere un array di un miliardo di stringhe e di volerlo ordinare.
L'ordinamento è probabilmente lento.
Inoltre, dobbiamo copiare tutto (lento!) e allocare abbastanza memoria (diversi gigabyte!) per conservare la copia.
Confronta con questo codice molto simile:
# v is as previously
julia> issorted(v)
false
julia> sort!(v)
4-element Vector{Int64}:
1
2
3
4
julia> v
4-element Vector{Int64}:
1
2
3
4
julia> issorted(v)
true
Ora il Vector di input viene ordinato sul posto, senza copiarlo, e l'ordine originale va perso per sempre.
Può essere efficiente, può essere pieno di bug e causare effetti collaterali inattesi, può confondere le altre persone che usano il codice.
Scegli con attenzione!
sort!() è una «funzione mutante» e, per convenzione (molto forte), qualsiasi funzione che muta i suoi input ha un ! aggiunto al nome, come avvertimento per chi programma.
Ordinare con un array di indici
Se gli elementi da ordinare sono oggetti di grandi dimensioni, può essere più semplice lavorare con il loro indice di posizione.
julia> langs = ["Julia", "C++", "Python", "Elixir"]
4-element Vector{String}:
"Julia"
"C++"
"Python"
"Elixir"
julia> inxs = sortperm(langs) # => Integers
4-element Vector{Int64}:
2
4
1
3
julia> langs[inxs] # sort the entire vector
4-element Vector{String}:
"C++"
"Elixir"
"Julia"
"Python"
julia> langs[inxs[1:2]] # slice the indices
2-element Vector{String}:
"C++"
"Elixir"
Poiché langs è un vettore, ogni indice è un intero nell'intervallo 1:length(langs).
L'output di sortperm() è una permutazione di questi interi, che corrisponde a un ordinamento del vettore di input.
Istruzioni
Sei stato assunto come assistente ingegnere di produzione in un'azienda che produce trapunte per tartarughe.
Gli ordini arrivano nel corso della giornata sotto forma di un nome o un numero di cliente e di una quantità ordinata.
Vengono poi elaborati la mattina, prima che inizi la produzione della giornata.
Puoi andare a casa con lo stipendio pieno non appena tutti gli ordini della giornata sono stati evasi, quindi conviene accorciare il più possibile la giornata lavorativa.
Dato che ogni ordine è gestito da una sola macchina, programmare prima gli ordini più grandi permette di scaricare l'overhead di avvio di un lavoro sugli ordini più piccoli: il tempo di produzione totale si accorcia.
Perciò hai deciso di scrivere alcune funzioni di ordinamento per velocizzare questa pianificazione, così puoi tornare a casa a lavorare a maglia un maglione per la tua tartaruga.
1. Ordina le quantità!
Come accennato, l'array delle quantità dovrà essere ordinato dal più grande al più piccolo.
Dato che questi array possono essere molto grandi, vanno ordinati in place.
Per tenere traccia di tutto correttamente, dovrai anche poter ordinare l'array dei clienti in modo che corrisponda alle quantità: servirà quindi una permutazione di ordinamento delle quantità.
Scrivi una funzione sortquantity!(qty) che prende un Vector di quantità Integer.
Questa funzione ordina in place l'input qty in ordine decrescente e restituisce la permutazione di ordinamento corrispondente.
julia> qty = [8, 9, 5, 6]
4-element Vector{Int64}:
8
9
5
6
julia> sortquantity!(qty)
4-element Vector{Int64}:
2
1
4
3
julia> qty # original vector is sorted in-place
4-element Vector{Int64}:
9
8
6
5
2. Ordina i clienti
Come detto sopra, devi tenere traccia dei clienti in un ordine ben definito.
Scrivi una funzione sortcustomer(cust, srtperm) che prende un Vector di clienti cust e un Vector con la permutazione di ordinamento srtperm.
Questa funzione restituisce un nuovo array con i clienti nell'ordine indicato dalla permutazione di ordinamento.
julia> cust = ["a", "b", "c"]
3-element Vector{String}:
"a"
"b"
"c"
julia> sortcustomer(cust, [2, 3, 1])
3-element Vector{String}:
"b"
"c"
"a"
julia> cust # original vector remains unsorted
3-element Vector{String}:
"a"
"b"
"c"
3. Programma di produzione!
Ora puoi mettere tutto insieme per aiutare quelle tartarughe a stare al caldo!
Ora sai ordinare correttamente le quantità e i clienti, ma devi anche poter recuperare l'ordine originale per la spedizione.
Puoi farlo con una permutazione di ordinamento inversa.
Scrivi una funzione production_schedule!(cust, qty) che prende un Vector di clienti e un Vector di quantità.
Questa funzione ordina le quantità in place in ordine decrescente.
Restituisce un nuovo Vector di clienti ordinati nello stesso ordine delle quantità e una permutazione di ordinamento inversa che può essere usata per riportare gli array ordinati al loro ordine originale.
julia> cust, qty = ["a", "b", "c"], [2, 3, 1]
(["a", "b", "c"], [2, 3, 1])
julia> orderedcust, invperm = production_schedule!(cust, qty)
(["b", "a", "c"], [2, 1, 3])
julia> qty # has been sorted in-place
3-element Vector{Int64}:
3
2
1
julia> orderedcust[invperm], qty[invperm] # inverse permutation gives original ordering
(["a", "b", "c"], [2, 3, 1])
Esercizio di apprendimento
