Einführung
Julia bietet, wie die meisten Programmiersprachen, eine reiche Vielfalt an Sammlungstypen.
Manche sind von Natur aus geordnet (darunter Vectors und höherdimensionale Arrays), sodass wir über die Position auf ihre Elemente zugreifen können.
Andere Sammlungen sind ungeordnet (Sets, Dicts), und auf ihre Elemente muss über einen Schlüssel oder einen Wert zugegriffen werden.
Im einfachsten Fall nehmen wir an, wir haben einen Vector aus Ints und wollen ihn in aufsteigender Reihenfolge sortieren.
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
Einfach!
Die Funktion sort() hat einen offensichtlichen Namen und gibt scheinbar den sortierten Vector zurück.
War nur ein Scherz!
Zu diesem Zeitpunkt im Lehrplan vermutest du vielleicht (zu Recht), dass es Feinheiten gibt, die wir besprechen müssen.
Mutierende und nicht-mutierende Funktionen
Was ist v, nachdem sort(v) ausgeführt wurde?
julia> v
4-element Vector{Int64}:
3
2
4
1
julia> issorted(v)
false
Der ursprüngliche Vektor ist unverändert.
sort() ist eine nicht-mutierende Funktion, die eine Kopie ihrer Eingabe zurückgibt.
Das ist in vielen Kontexten ein gutes Design: Wir haben eine reine Funktion, deren Verhalten leicht nachzuvollziehen ist, selbst in parallelem, verteiltem Code.
Andererseits: Angenommen, wir hätten ein Array mit einer Milliarde Strings und wollten es sortieren.
Das Sortieren ist wahrscheinlich langsam.
Außerdem müssen wir alles kopieren (langsam!) und genug Speicher reservieren (mehrere Gigabyte!), um die Kopie zu speichern.
Vergleiche diesen recht ähnlichen Code:
# 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
Jetzt wird der eingegebene Vector an Ort und Stelle sortiert, ohne zu kopieren, und die ursprüngliche Reihenfolge ist endgültig verloren.
Das kann effizient sein, es kann fehlerhaft sein und zu unerwarteten Nebenwirkungen führen, und es kann für andere, die deinen Code nutzen, verwirrend sein.
Wähle mit Bedacht!
sort!() ist eine „mutierende Funktion“, und nach (sehr strenger) Konvention hängt man an jede Funktion, die ihre Eingaben mutiert, ein ! an ihren Namen an, als Warnung an Programmierer.
Sortierindex-Array
Wenn es sich bei den zu sortierenden Elementen um große Objekte handelt, kann es einfacher sein, mit ihrem Positionsindex zu arbeiten.
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"
Da langs ein Vector ist, ist jeder Index eine Ganzzahl im Bereich 1:length(langs).
Die Ausgabe von sortperm() ist eine Permutation dieser Ganzzahlen, die einer Sortierung des eingegebenen Vektors entspricht.
Anleitung
Du wurdest als Assistenz-Produktionsingenieur in einem Unternehmen eingestellt, das Quilts für Schildkröten herstellt.
Über den Tag verteilt gehen Bestellungen ein, jeweils bestehend aus einem Kundennamen oder einer Kundennummer und einer Bestellmenge.
Diese werden dann am Morgen bearbeitet, bevor die Produktion des Tages beginnt.
Du darfst mit vollem Lohn nach Hause gehen, sobald alle Bestellungen des Tages erfüllt sind, also gibt es einen Anreiz, den Arbeitstag so weit wie möglich zu verkürzen.
Da jede Bestellung von einer einzigen Maschine bearbeitet wird, lässt sich durch die Planung der größten Bestellungen zuerst der Aufwand für den Start eines Auftrags auf die kleineren Bestellungen abwälzen, was die gesamte Produktionszeit verkürzt.
Deshalb hast du beschlossen, einige Sortierfunktionen bereitzustellen, die bei dieser Beschleunigung der Planung helfen, damit du nach Hause gehen kannst, um einen Pullover für deine Schildkröte zu stricken.
1. Sortiere die Mengen!
Wie erwähnt, muss das Array der Mengen vom größten zum kleinsten Wert sortiert werden.
Da diese Arrays potenziell sehr groß sind, sollten sie in-place sortiert werden.
Um alles korrekt im Blick zu behalten, musst du außerdem das Array der Kunden passend zu den Mengen sortieren können, also wird eine Sortierpermutation der Mengen benötigt.
Schreibe eine Funktion sortquantity!(qty), die einen Vector aus Integer-Mengen entgegennimmt.
Diese Funktion sortiert die Eingabe qty in-place in absteigender Reihenfolge und gibt eine Sortierpermutation dieser Reihenfolge zurück.
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. Sortiere die Kunden
Wie oben erwähnt, musst du die Kunden in einer festgelegten Reihenfolge im Blick behalten.
Schreibe eine Funktion sortcustomer(cust, srtperm), die einen Vector von Kunden cust und einen Vector als Sortierpermutation srtperm entgegennimmt.
Diese Funktion gibt ein neues Array zurück, in dem die Kunden in der durch die Sortierpermutation vorgegebenen Reihenfolge stehen.
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. Der Produktionsplan!
Jetzt kannst du alles zusammenbringen, um diese Schildkröten warm zu halten!
Du kannst die Mengen und Kunden jetzt richtig sortieren, aber du musst die ursprüngliche Reihenfolge für den Versand wiederherstellen können.
Das geht mit einer inversen Sortierpermutation.
Schreibe eine Funktion production_schedule!(cust, qty), die einen Vector von Kunden und einen Vector von Mengen entgegennimmt.
Diese Funktion sortiert die Mengen in-place in absteigender Reihenfolge.
Sie gibt einen neuen Vector von Kunden zurück, der in derselben Reihenfolge wie die Mengen sortiert ist, sowie eine inverse Sortierpermutation, mit der sich die sortierten Vektoren in ihre ursprüngliche Reihenfolge zurücksetzen lassen.
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])
Lernübung
