Introducción
Julia, como la mayoría de los lenguajes de programación, ofrece una gran variedad de tipos de colecciones.
Algunos son intrínsecamente ordenados (entre ellos los Vectors y los Arrays de dimensiones superiores), así que podemos acceder a sus elementos por 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 simple, 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
¡Sencillo!
La función sort() tiene un nombre obvio y, al parecer, devuelve el Vector ordenado.
¡Es broma!
A estas alturas del temario, quizás sospeches (con razón) que hay matices que debemos 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 cambia.
sort() es una función no mutante que devuelve una copia de su argumento.
Es un buen diseño en muchos contextos: tenemos una función pura sobre cuyo comportamiento es fácil razonar, incluso en código paralelo y distribuido.
Por otro lado, supongamos que tenemos un array de mil millones de strings y queremos ordenarlo.
Seguramente el ordenamiento sea lento.
Además, hay que copiar todo (¡lento!) y reservar suficiente memoria (¡varios gigabytes!) para guardar la copia.
Compara este código bastante similar:
# 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 en el lugar, sin copiar nada, y el orden original se pierde de forma permanente.
Puede ser eficiente, también 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 fuerte), toda función que muta sus argumentos lleva un ! al final del nombre, como advertencia para los programadores.
Arreglo de índices de ordenamiento
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 entero en el rango 1:length(langs).
La salida de sortperm() es una permutación de estos enteros, que corresponde a un ordenamiento del vector de entrada.
Instrucciones
Te han contratado como ingeniero asistente de producción en una empresa que fabrica colchas para tortugas.
Los pedidos llegan a lo largo del día como un nombre o 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 completen todos los pedidos del día, así que hay incentivos para acortar la jornada laboral todo lo posible.
Como cada pedido lo maneja una sola máquina, programar primero los pedidos más grandes permite trasladar la sobrecarga de arrancar un trabajo a los pedidos más pequeños, lo que acorta el tiempo total de producción.
Por lo tanto, has decidido crear algunas funciones de ordenamiento que ayuden a acelerar esta programación, para que puedas llegar a casa a tejerle un suéter a tu tortuga.
1. ¡Ordena las cantidades!
Como se mencionó, el array de cantidades deberá ordenarse de mayor a menor.
Debido al tamaño potencialmente grande de estos arrays, deben ordenarse in situ.
Para llevar la cuenta de todo correctamente, también necesitarás poder ordenar el array de clientes para que coincida con las cantidades, así que se necesitará una permutación de ordenamiento de las cantidades.
Escribe una función sortquantity!(qty) que recibe un Vector de cantidades Integer.
Esta función ordena la qty de entrada in situ en orden descendente y devuelve una permutación de ordenamiento 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 dijo antes, necesitas llevar la cuenta de los clientes en un orden definido.
Escribe una función sortcustomer(cust, srtperm) que recibe un Vector de clientes cust y un Vector de permutación de ordenamiento srtperm.
Esta función devuelve un nuevo array con los clientes en el orden que prescribe la permutación de ordenamiento.
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. ¡Programa la producción!
¡Ahora puedes unirlo todo para ayudar a mantener calentitas a esas tortugas!
Ya puedes ordenar las cantidades y los clientes correctamente, pero necesitas poder recuperar el orden original para el envío.
Esto se puede hacer con una permutación de ordenamiento inversa.
Escribe una función production_schedule!(cust, qty) que recibe un Vector de clientes y un Vector de cantidades.
Esta función ordena las cantidades in situ en orden descendente.
Devuelve un nuevo Vector de clientes ordenados en el mismo orden que las cantidades y una permutación de ordenamiento inversa que se puede usar 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
