Bevezetés
A Julia, mint a legtöbb programozási nyelv, a gyűjteménytípusok széles választékát kínálja.
Némelyikük eleve rendezett (köztük a Vectors és a többdimenziós Arrays), így az elemeket pozíció szerint érhetjük el.
Más gyűjtemények rendezetlenek (Sets, Dicts), és az elemeiket kulcs vagy érték alapján érhetjük el.
A legegyszerűbb esetben tegyük fel, hogy van egy Vectorunk Ints-ből, és növekvő sorrendbe szeretnénk rendezni.
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
Egyszerű!
A sort() függvénynek kézenfekvő a neve, és látszólag a rendezett Vector-t adja vissza.
Csak vicceltem!
A tantervben ezen a ponton talán már (helyesen) sejted, hogy akadnak olyan árnyalatok, amelyeket meg kell beszélnünk.
Módosító és nem módosító függvények
Mi lesz v értéke a sort(v) lefuttatása után?
julia> v
4-element Vector{Int64}:
3
2
4
1
julia> issorted(v)
false
Az eredeti vektor változatlan marad.
A sort() egy nem módosító függvény, amely a bemenetének egy másolatát adja vissza.
Sok helyzetben ez jó tervezési döntés: van egy tiszta függvényünk, amelynek a viselkedése könnyen átlátható, még párhuzamos, elosztott kódban is.
Másrészt tegyük fel, hogy van egy egymilliárd stringből álló tömbünk, és rendezni szeretnénk.
A rendezés valószínűleg lassú.
Ráadásul mindent le kell másolnunk (lassú!), és elegendő memóriát kell lefoglalnunk (több gigabájtnyit!) a másolat tárolásához.
Hasonlítsd össze ezzel a nagyon hasonló kóddal:
# 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
Most a bemeneti Vector helyben rendeződik, másolás nélkül, és az eredeti sorrend véglegesen elvész.
Ez lehet hatékony, de lehet hibás, váratlan mellékhatásokat okozhat, és összezavarhatja azokat, akik a kódodat használják.
Válassz körültekintően!
A sort!() egy „módosító függvény”, és egy (nagyon erős) konvenció szerint minden függvény nevének a végére ! kerül, ha módosítja a bemeneteit, figyelmeztetésül a programozóknak.
Rendezési indexek tömbje
Ha a rendezendő elemek nagy objektumok, könnyebb lehet a pozíciós indexükkel dolgozni.
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"
Mivel a langs egy Vector, minden index egy egész szám az 1:length(langs) intervallumban.
A sortperm() kimenete ezeknek az egészeknek egy permutációja, ami megfelel a bemeneti vektor egy rendezésének.
Utasítások
Segédgyártási mérnökként vettek fel egy olyan cégnél, amely teknősöknek készít paplant.
A megrendelések a nap folyamán folyamatosan érkeznek: egy vásárlónév vagy -szám, valamint egy rendelési mennyiség.
Ezeket aztán reggel dolgozzák fel, még az aznapi gyártás megkezdése előtt.
Amint az aznapi összes megrendelést teljesítették, teljes fizetéssel mehetsz haza, így érdekünkben áll a lehető legjobban lerövidíteni a munkanapot.
Mivel minden megrendelést egyetlen gép végez el, a legnagyobb megrendelések előre ütemezésével a munkaindítás többletköltsége a kisebb megrendelésekre tolható, ami lerövidíti a teljes gyártási időt.
Ezért úgy döntöttél, hogy írsz néhány rendezőfüggvényt, amelyek segítenek felgyorsítani ezt az ütemezést, hogy hazaérhess pulóvert kötni a teknősödnek.
1. Rendezd a mennyiségeket!
Ahogy már említettük, a mennyiségek tömbjét a legnagyobbtól a legkisebbig kell rendezni.
Mivel ezek a tömbök potenciálisan nagyok lehetnek, helyben kell rendezni őket.
Ahhoz, hogy mindent helyesen követhess, a vásárlók tömbjét is a mennyiségekhez igazodva kell tudnod rendezni, ezért szükség lesz a mennyiségek egy rendezési permutációjára.
Írj egy sortquantity!(qty) függvényt, amely Integer típusú mennyiségek Vector-ját veszi át.
Ez a függvény helyben rendezi a bemeneti qty tömböt csökkenő sorrendbe, és visszaadja ennek a sorrendnek a rendezési permutációját.
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. Rendezd a vásárlókat
Ahogy fentebb említettük, a vásárlókat egy meghatározott sorrendben kell nyilvántartanod.
Írj egy sortcustomer(cust, srtperm) függvényt, amely egy cust vásárlókból álló Vector-t és egy srtperm rendezési permutációt tartalmazó Vector-t vesz át.
Ez a függvény egy új tömböt ad vissza, amelyben a vásárlók a rendezési permutáció által előírt sorrendben szerepelnek.
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. Gyártási ütemterv!
Most már mindent összerakhatsz, hogy segíts melegen tartani azokat a teknősöket!
A mennyiségeket és a vásárlókat már megfelelően tudod rendezni, de a szállításhoz vissza kell tudnod állítani az eredeti sorrendet.
Erre egy inverz rendezési permutációval van lehetőség.
Írj egy production_schedule!(cust, qty) függvényt, amely egy vásárlókból álló Vector-t és egy mennyiségekből álló Vector-t vesz át.
Ez a függvény helyben rendezi a mennyiségeket csökkenő sorrendbe.
Visszaad egy új, a mennyiségekkel azonos sorrendbe rendezett vásárlókból álló Vector-t, valamint egy inverz rendezési permutációt, amellyel a rendezett vektorok visszaállíthatók az eredeti sorrendjükbe.
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])
Tanulófeladat
