Вступ
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() - функція без мутації, яка повертає копію свого входу.
У багатьох випадках це вдале рішення: у нас є чиста функція, поведінку якої легко зрозуміти, навіть у паралельному чи розподіленому коді.
З іншого боку, уявімо масив із мільярда рядків тексту (англ. string), який ми хочемо відсортувати.
Сортування, ймовірно, буде повільним.
До того ж нам доведеться скопіювати все (повільно!) і виділити достатньо памʼяті (кілька гігабайтів!), щоб зберегти копію.
Порівняймо з дуже схожим кодом:
# 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 відсортовано на місці, без копіювання, і початковий порядок втрачено назавжди.
Це може бути ефективно, може породжувати помилки й несподівані побічні ефекти, може заплутати інших людей, які працюють з нашим кодом.
Обираймо ретельно!
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 є вектором, кожен індекс - ціле число в діапазоні 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])
Навчальна вправа
