Introducción
Julia, como la mayoría de los lenguajes de programación, ofrece una gran variedad de tipos de colecciones.
Algunas tienen un orden inherente (incluidos los Vectors y los Arrays de dimensiones superiores), así que podemos acceder a sus elementos por su posición.
Otras colecciones no tienen orden (Sets, Dicts) y hay que acceder a sus elementos por clave o por valor.
En el caso más sencillo, supongamos que tenemos un Vector de Ints y queremos ordenarlo de forma ascendente.
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
¡Así de simple!
La función sort() tiene un nombre evidente y, al parecer, devuelve el Vector ordenado.
¡Es broma!
A estas alturas del temario, quizá sospeches (con razón) que hay matices que conviene comentar.
Funciones mutantes y no mutantes
Después de ejecutar sort(v), ¿qué es v?
julia> v
4-element Vector{Int64}:
3
2
4
1
julia> issorted(v)
false
El vector original no ha cambiado.
sort() es una función no mutante que devuelve una copia de su entrada.
Es un buen diseño en muchos contextos: tenemos una función pura cuyo comportamiento es fácil de razonar, incluso en código paralelo o distribuido.
En cambio, supongamos que tenemos un array de mil millones de strings y queremos ordenarlo.
Probablemente, la ordenación sea lenta.
Además, tenemos que copiarlo todo (¡lento!) y reservar memoria suficiente (¡varios gigabytes!) para guardar la copia.
Compáralo con este código, muy parecido:
# 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
Ahora el Vector de entrada se ordena in situ, sin copiarlo, y el orden original se pierde para siempre.
Puede ser eficiente, puede tener errores y provocar efectos secundarios inesperados, y puede confundir a otras personas que usen tu código.
¡Elige con cuidado!
sort!() es una «función mutante» y, por convención (muy arraigada), cualquier función que modifique sus entradas lleva un ! al final de su nombre, a modo de advertencia para los programadores.
Ordenar con un array de índices
Si los elementos que se van a ordenar son objetos grandes, puede resultar más fácil trabajar con su índice de posición.
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 es un Vector, cada índice es un número entero en el rango 1:length(langs).
La salida de sortperm() es una permutación de esos números enteros que se corresponde con una ordenación del vector de entrada.
Instrucciones
Te han contratado como ingeniero de producción adjunto en una empresa que fabrica colchas para tortugas.
Los pedidos llegan a lo largo del día como un nombre o un número de cliente y una cantidad de pedido.
Luego se procesan por la mañana, antes de que empiece la producción del día.
Puedes irte a casa con el sueldo completo en cuanto se hayan completado todos los pedidos del día, así que hay incentivos para acortar la jornada laboral todo lo posible.
Como cada pedido lo gestiona una única máquina, programar primero los pedidos más grandes permite trasladar el coste de iniciar un trabajo a los pedidos más pequeños, acortando el tiempo total de producción.
Por lo tanto, has decidido proporcionar algunas funciones de ordenación para ayudar a acelerar esta planificación, de modo que puedas volver a casa a tejer un jersey para tu tortuga.
1. ¡Ordena las cantidades!
Como ya se ha comentado, el array de cantidades tendrá que ordenarse de mayor a menor.
Debido al tamaño potencialmente grande de estos arrays, deben ordenarse in-place.
Para llevar la cuenta de todo correctamente, también tendrás que poder ordenar el array de clientes de forma que coincida con las cantidades, por lo que necesitarás una permutación de ordenación de las cantidades.
Escribe una función sortquantity!(qty) que reciba un Vector de cantidades Integer.
Esta función ordena la qty de entrada in-place en orden descendente y devuelve una permutación de ordenación de este orden.
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 los clientes!
Como se ha dicho antes, tienes que llevar la cuenta de los clientes en un orden definido.
Escribe una función sortcustomer(cust, srtperm) que reciba un Vector de clientes cust y un Vector de permutación de ordenación srtperm.
Esta función devuelve un nuevo array con los clientes en el orden que prescribe la permutación de ordenación.
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. ¡Planifica la producción!
¡Ahora puedes combinarlo todo para ayudar a mantener calentitas a esas tortugas!
Ya puedes ordenar correctamente las cantidades y los clientes, pero necesitas poder recuperar el orden original para el envío.
Esto puede hacerse con una permutación de ordenación inversa.
Escribe una función production_schedule!(cust, qty) que reciba un Vector de clientes y un Vector de cantidades.
Esta función ordena las cantidades in-place en orden descendente.
Devuelve un nuevo Vector de clientes ordenados en el mismo orden que las cantidades y una permutación de ordenación inversa que puede usarse para restaurar los vectores ordenados a su orden original.
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])
Ejercicio de aprendizaje
