Εισαγωγή
Η Julia, όπως οι περισσότερες γλώσσες προγραμματισμού, παρέχει μια πλούσια ποικιλία τύπων συλλογών.
Κάποιες έχουν εκ φύσεως σειρά (όπως τα Vectors και τα πολυδιάστατα Arrays), οπότε μπορούμε να προσπελάσουμε τα στοιχεία τους με βάση τη θέση.
Άλλες συλλογές δεν έχουν σειρά (Sets, Dicts) και τα στοιχεία τους πρέπει να προσπελαύνονται με κλειδί ή τιμή.
Στην απλούστερη περίπτωση, ας υποθέσουμε ότι έχουμε ένα Vector από Ints και θέλουμε να το ταξινομήσουμε σε αύξουσα σειρά.
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
Απλό!
Η συνάρτηση sort() έχει προφανές όνομα και, όπως φαίνεται, επιστρέφει τον ταξινομημένο Vector.
Πλάκα κάνω!
Σε αυτό το σημείο του προγράμματος σπουδών, ίσως υποψιάζεσαι (σωστά) ότι υπάρχουν αποχρώσεις που πρέπει να συζητήσουμε.
Τροποποιητικές έναντι μη τροποποιητικών συναρτήσεων
Αφού τρέξεις το sort(v), τι είναι το v;
julia> v
4-element Vector{Int64}:
3
2
4
1
julia> issorted(v)
false
Το αρχικό διάνυσμα παραμένει αμετάβλητο.
Η sort() είναι μια μη τροποποιητική συνάρτηση που επιστρέφει ένα αντίγραφο της εισόδου της.
Αυτός είναι καλός σχεδιασμός σε πολλά πλαίσια: έχουμε μια καθαρή συνάρτηση της οποίας η συμπεριφορά είναι εύκολο να αναλυθεί, ακόμη και σε παράλληλο, κατανεμημένο κώδικα.
Από την άλλη, ας υποθέσουμε ότι είχαμε έναν πίνακα με ένα δισεκατομμύριο συμβολοσειρές και θέλαμε να τον ταξινομήσουμε.
Η ταξινόμηση είναι πιθανώς αργή.
Επιπλέον, πρέπει να αντιγράψουμε τα πάντα (αργό!) και να δεσμεύσουμε αρκετή μνήμη (αρκετά Gigabyte!) για να αποθηκεύσουμε το αντίγραφο.
Σύγκρινε αυτόν τον αρκετά παρόμοιο κώδικα:
# 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
Τώρα ο Vector εισόδου ταξινομείται επιτόπου, χωρίς αντιγραφή, και η αρχική σειρά χάνεται οριστικά.
Αυτό μπορεί να είναι αποδοτικό, μπορεί να έχει bugs και να οδηγήσει σε απροσδόκητες παρενέργειες, μπορεί να μπερδέψει άλλους που χρησιμοποιούν τον κώδικά σου.
Διάλεξε προσεκτικά!
Η sort!() είναι μια "τροποποιητική συνάρτηση" και, κατά (πολύ ισχυρή) σύμβαση, κάθε συνάρτηση που τροποποιεί τα ορίσματά της έχει ένα ! στο τέλος του ονόματός της, ως προειδοποίηση για τους προγραμματιστές.
Πίνακας θέσεων ταξινόμησης
Αν τα στοιχεία που ταξινομούνται είναι μεγάλα αντικείμενα, μπορεί να είναι ευκολότερο να δουλέψεις με τη θέση τους.
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"
Επειδή το langs είναι Vector, κάθε θέση είναι ένας ακέραιος στο διάστημα 1:length(langs).
Η έξοδος της sortperm() είναι μια μετάθεση αυτών των ακεραίων, που αντιστοιχεί σε μια ταξινόμηση του διανύσματος εισόδου.
Οδηγίες
Έχεις προσληφθεί ως Βοηθός Μηχανικός Παραγωγής σε μια εταιρεία που φτιάχνει παπλώματα για χελώνες.
Οι παραγγελίες έρχονται στη διάρκεια της ημέρας ως όνομα ή αριθμός πελάτη και ποσότητα παραγγελίας.
Στη συνέχεια επεξεργάζονται το πρωί, πριν ξεκινήσει η παραγωγή της ημέρας.
Πας σπίτι με πλήρη αμοιβή μόλις εκτελεστούν όλες οι παραγγελίες της ημέρας, οπότε έχεις κίνητρο να συντομεύσεις τη μέρα εργασίας όσο το δυνατόν περισσότερο.
Επειδή κάθε παραγγελία εκτελείται από ένα μόνο μηχάνημα, το να προγραμματίζεις πρώτα τις μεγαλύτερες παραγγελίες επιτρέπει το κόστος εκκίνησης μιας εργασίας να μετακυλιστεί στις μικρότερες παραγγελίες, συντομεύοντας τον συνολικό χρόνο παραγωγής.
Γι' αυτό αποφάσισες να παρέχεις μερικές συναρτήσεις ταξινόμησης που θα βοηθήσουν αυτή την επιτάχυνση του προγραμματισμού, ώστε να πας σπίτι να πλέξεις ένα πουλόβερ για τη χελώνα σου.
1. Ταξινόμησε τις ποσότητες!
Όπως αναφέρθηκε, ο πίνακας των ποσοτήτων θα πρέπει να ταξινομηθεί από τη μεγαλύτερη στη μικρότερη.
Επειδή αυτοί οι πίνακες μπορεί να είναι αρκετά μεγάλοι, θα πρέπει να ταξινομούνται επί τόπου.
Για να παρακολουθείς τα πάντα σωστά, θα πρέπει επίσης να μπορείς να ταξινομήσεις τον πίνακα των πελατών ώστε να ταιριάζει με τις ποσότητες, οπότε θα χρειαστείς μια μετάθεση ταξινόμησης των ποσοτήτων.
Γράψε μια συνάρτηση sortquantity!(qty) που παίρνει ένα Vector από Integer ποσότητες.
Αυτή η συνάρτηση ταξινομεί το qty επί τόπου σε φθίνουσα σειρά και επιστρέφει μια μετάθεση ταξινόμησης αυτής της διάταξης.
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. Ταξινόμησε τον πελάτη
Όπως αναφέρθηκε παραπάνω, χρειάζεται να παρακολουθείς τους πελάτες σε μια καθορισμένη σειρά.
Γράψε μια συνάρτηση sortcustomer(cust, srtperm) που παίρνει ένα Vector πελατών cust και ένα Vector μετάθεσης ταξινόμησης srtperm.
Αυτή η συνάρτηση επιστρέφει έναν νέο πίνακα με τους πελάτες στη σειρά που ορίζει η μετάθεση ταξινόμησης.
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. Πρόγραμμα παραγωγής!
Τώρα μπορείς να τα βάλεις όλα μαζί για να κρατήσεις αυτές τις χελώνες ζεστές!
Μπορείς πλέον να ταξινομήσεις σωστά τις ποσότητες και τους πελάτες, αλλά χρειάζεται να μπορείς να ανακτήσεις την αρχική σειρά για την αποστολή.
Αυτό μπορεί να γίνει με μια αντίστροφη μετάθεση ταξινόμησης.
Γράψε μια συνάρτηση production_schedule!(cust, qty) που παίρνει ένα Vector πελατών και ένα Vector ποσοτήτων.
Αυτή η συνάρτηση ταξινομεί τις ποσότητες επί τόπου σε φθίνουσα σειρά.
Επιστρέφει ένα νέο Vector πελατών ταξινομημένο στην ίδια σειρά με τις ποσότητες και μια αντίστροφη μετάθεση ταξινόμησης που μπορεί να χρησιμοποιηθεί για να επαναφέρει τους ταξινομημένους πίνακες στην αρχική τους σειρά.
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])
Άσκηση εκμάθησης
