Introdução
A Julia, como a maioria das linguagens de programação, oferece uma grande variedade de tipos de coleções.
Algumas são intrinsecamente ordenadas (incluindo os Vectors e os Arrays de dimensões superiores), por isso podemos aceder aos elementos pela posição.
Outras coleções não são ordenadas (Sets, Dicts), e os elementos têm de ser acedidos pela chave ou pelo valor.
No caso mais simples, imagina que temos um Vector de Ints e queremos ordená-lo por ordem 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
Simples!
A função sort() tem um nome óbvio e, aparentemente, devolve o Vector ordenado.
Estou a brincar!
A esta altura do programa, talvez suspeites (com razão) que há nuances de que precisamos de falar.
Funções que modificam vs. funções que não modificam
Depois de correres sort(v), o que é o v?
julia> v
4-element Vector{Int64}:
3
2
4
1
julia> issorted(v)
false
O vetor original fica inalterado.
A sort() é uma função que não modifica os seus argumentos e devolve uma cópia do valor de entrada.
É um bom design em muitos contextos: temos uma função pura, cujo comportamento é fácil de analisar, mesmo em código paralelo e distribuído.
Por outro lado, imagina que tínhamos um array com mil milhões de strings e queríamos ordená-lo.
A ordenação é provavelmente lenta.
Além disso, temos de copiar tudo (lento!) e alocar memória suficiente (vários gigabytes!) para guardar a cópia.
Compara com este código bastante semelhante:
# 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
Agora, o Vector de entrada é ordenado no local, sem cópias, e a ordem original perde-se definitivamente.
Isto pode ser eficiente, pode ter bugs e provocar efeitos secundários inesperados, pode ser confuso para outras pessoas que usem o teu código.
Escolhe com cuidado!
A sort!() é uma «função que modifica os argumentos» e, por convenção (muito forte), qualquer função que modifique os seus argumentos tem um ! acrescentado ao nome, como aviso para quem programa.
Array de índices de ordenação
Se os elementos a ordenar forem objetos grandes, pode ser mais fácil trabalhar com o seu índice de posição.
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"
Como langs é um vetor, cada índice é um número inteiro no intervalo 1:length(langs).
O resultado de sortperm() é uma permutação desses números inteiros, que corresponde à ordenação do vetor de entrada.
Instruções
Foste contratado como Engenheiro de Produção Assistente numa empresa que produz colchas para tartarugas.
Ao longo do dia chegam encomendas com o nome ou o número de um cliente e uma quantidade. Estas são depois processadas de manhã, antes de começar a produção do dia.
Podes ir para casa com o ordenado completo assim que todas as encomendas do dia estiverem prontas, por isso há um incentivo para encurtar o dia de trabalho tanto quanto possível.
Como cada encomenda é tratada por uma única máquina, agendar primeiro as encomendas maiores permite passar o custo de arranque de uma tarefa para as encomendas mais pequenas, encurtando o tempo total de produção.
Por isso, decidiste criar algumas funções de ordenação para ajudar a acelerar este agendamento, para poderes ir para casa tricotar uma camisola para a tua tartaruga.
1. Ordena as quantidades!
Como já vimos, o array de quantidades tem de ser ordenado da maior para a mais pequena.
Dado o tamanho potencialmente grande destes arrays, devem ser ordenados no local.
Para manteres tudo corretamente organizado, também tens de conseguir ordenar o array de clientes de forma a corresponder às quantidades, por isso vais precisar de uma permutação de ordenação das quantidades.
Escreve uma função sortquantity!(qty) que recebe um Vector de quantidades Integer.
Esta função ordena o qty de entrada no local, por ordem decrescente, e devolve uma permutação de ordenação desta ordenação.
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. Ordena os clientes
Como foi dito acima, tens de manter os clientes numa ordem definida.
Escreve uma função sortcustomer(cust, srtperm) que recebe um Vector de clientes cust e um Vector com a permutação de ordenação srtperm.
Esta função devolve um novo array com os clientes na ordem indicada pela permutação de ordenação.
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. Plano de produção!
Agora podes juntar tudo para ajudar a manter essas tartarugas quentinhas!
Já consegues ordenar corretamente as quantidades e os clientes, mas precisas de recuperar a ordenação original para a expedição.
Isso pode ser feito com uma permutação de ordenação inversa.
Escreve uma função production_schedule!(cust, qty) que recebe um Vector de clientes e um Vector de quantidades.
Esta função ordena as quantidades no local, por ordem decrescente.
Devolve um novo Vector de clientes ordenado na mesma ordem que as quantidades e uma permutação de ordenação inversa que pode ser usada para repor a ordenação original dos vetores ordenados.
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])
Exercício de aprendizagem
