En este artículo, consideraremos agregar un tipo de datos personalizado al programa Julia y sobrecargar las funciones estándar para un trabajo conveniente con el nuevo tipo.
¿Qué es un tipo personalizado?
Un terrible secreto: la frontera entre los tipos de datos "usuario" y "incorporado" en Julia está prácticamente ausente. En cualquier programa de Julia, puede definir sus propios tipos de datos, y trabajar con ellos casi no es diferente de trabajar con los datos integrados, ya sea en términos de escritura de código o en términos de velocidad de ejecución de este código (hola, Python). Los tipos de datos de entrada pueden ser primitivos o compuestos. Estos últimos también se dividen en tipos abstractos y concretos.
Además consideraremos un ejemplo de tipos de concreto compuesto, ya que Los objetos específicos en la memoria son tipos específicos, y los objetos abstractos solo se necesitan para construir una jerarquía.
Los tipos compuestos están definidos por las palabras clave struct y mutable struct . En el primer caso, se crea un tipo inmutable:
Los objetos de tipo Point inmutables, es decir El valor del campo en el objeto una vez creado no se puede cambiar.
julia> p = Point(2, 3) Point(2, 3) julia> px 2 julia> py 3 julia> px = 4 ERROR: setfield! immutable struct of type Point cannot be changed
Pero puedes hacer un tipo mutable:
mutable struct MutablePoint x y end julia> mp = MutablePoint(3, 4) MutablePoint(3, 4) julia> mp.y = 2 2 julia> mp MutablePoint(3, 2)
Para mayor eficiencia, se pueden agregar anotaciones de tipo a los campos de estructura y a la estructura misma. Por ejemplo:
struct ParametricPoint{T<:Real} x::T y::T end
Esto significa que el tipo ParametricPoint parametrizado por el tipo T y que los campos x e y ahora deberían ser valores del mismo tipo T El comportamiento será el siguiente:
julia> ParametricPoint(1, 1) ParametricPoint{Int64}(1, 1) julia> ParametricPoint{Float64}(1, 1) ParametricPoint{Float64}(1.0, 1.0) julia> ParametricPoint{Rational}(1, 1) ParametricPoint{Rational}(1//1, 1//1)
A continuación, veamos un ejemplo un poco más complejo de un tipo de contenedor para ver qué métodos hay en la biblioteca estándar para trabajar con dichos tipos.
Cola de dos vías
Haremos una cola bidireccional a partir de nodos del tipo DequeNode , que incluirá un registro de datos y enlaces a los elementos anteriores y siguientes de la cola. El tipo DequeNode debe ser mutable, porque los enlaces deberán reescribirse.
mutable struct DequeNode{T} data::T prev::DequeNode{T} next::DequeNode{T}
En este caso, se necesitan constructores internos, porque de forma predeterminada, al construir un objeto, debe pasar los valores de todos los campos con argumentos. Dado que el tipo es autoreferenciado, sería imposible para un constructor estándar crear el primer objeto de este tipo. Por lo tanto, creamos constructores especiales que crean un nodo de cola que se refiere a sí mismo.
La cola en sí misma puede representarse como un nodo de "entrada" ficticio que no contiene ningún dato. Su next enlace apuntará al primer elemento de la cola y prev al último. Para una cola vacía, ambos enlaces apuntan al nodo de entrada. Dicha organización simplifica los procedimientos para agregar y eliminar nodos.
struct Deque{T} entry::DequeNode{T} end Deque{T}() where T = Deque{T}(DequeNode{T}()) Deque() = Deque{Any}()
Ya no se necesita un constructor interno para la estructura de la cola misma.
Agregar elementos
Los procedimientos estándar para una cola son agregar un elemento al principio y al final, y extraer elementos del principio y del final. Para estos procedimientos, la biblioteca estándar ya tiene funciones a las que solo necesita agregar métodos para trabajar con otro tipo:
push!(collection, element) : agrega un elemento a la colección (para una colección ordenada, al final)pushfirst!(collection, element) : agrega un elemento al comienzo de una colección ordenadapop!(collection) : elimina un elemento de la colección (para una colección ordenada, desde el final)popfirst!(collection) : elimina el primer elemento de una colección ordenada
Todas estas funciones están en el módulo Base , y debe agregarle nuevos métodos. Además, escribiremos una función para verificar si la colección no está vacía: Base.isempty(collection) .
Base.isempty(deq::Deque) = deq.entry.prev ≡ deq.entry function Base.push!(deq::Deque{T}, elt) where T tail = deq.entry.prev new_item = DequeNode{T}(elt) new_item.prev, new_item.next = tail, deq.entry tail.next = deq.entry.prev = new_item return deq end function Base.pushfirst!(deq::Deque{T}, elt) where T head = deq.entry.next new_item = DequeNode{T}(elt) new_item.prev, new_item.next = deq.entry, head head.prev = deq.entry.next = new_item return deq end function Base.pop!(deq::Deque) !isempty(deq) || throw(ArgumentError("deque must be non-empty")) last = deq.entry.prev last.prev.next = deq.entry deq.entry.prev = last.prev return last.data end function Base.popfirst!(deq::Deque) !isempty(deq) || throw(ArgumentError("deque must be non-empty")) first = deq.entry.next first.next.prev = deq.entry deq.entry.next = first.next return first.data end
La función push!() Hace que sea casi trivial escribir un constructor de colas basado en una colección arbitraria:
function Deque(itr) d = Deque{eltype(itr)}() for elt in itr push!(d, elt) end return d end
Ahora el nuevo tipo casi se puede usar como una cola, si solo necesitamos agregar y quitar operaciones y no necesitamos una función como peek() (mira el elemento en la cabecera o cola de la cola sin extraerlo). Para el acceso no destructivo a los elementos, es conveniente definir la función de iteración sobre el contenedor.
Iteración
Julia admite el concepto de iteradores para atravesar elementos contenedores. Para la iteración, debe definir una sola función: iterate(container, state) , donde el state determina el estado actual del iterador. En particular, la construcción for x in collection es azúcar sintáctico para algo como esto:
let nextstate = iterate(collection) while nextstate ≢ nothing (x, state) = nextstate <- > nextstate = iterate(collection, state) end end
La función iterate() toma un contenedor y un "estado iterador" como argumento, y devuelve una tupla del elemento contenedor y el siguiente estado iterador, o nothing si el contenedor ha finalizado.
Para una cola, es lógico tomar el nodo de la cola, que la iteración ha alcanzado, como el "estado":
function Base.iterate(deq::Deque{T}, state::DequeNode{T}=deq.entry) where T nextstate = state.next nextstate ≡ deq.entry ? nothing : (nextstate.data, nextstate) end
Ahora los elementos de la cola se pueden ordenar con un bucle for :
julia> for x in Deque(1:10) println(x); end 1 2 3 4 5 6 7 8 9 10
Una gran ventaja es que muchas de las funciones de la biblioteca estándar de Julia se escriben utilizando interfaces generalizadas, en particular, la iteración. Por lo tanto, la comprobación automática de si un elemento pertenece a un contenedor se determina automáticamente:
julia> 5 ∈ Deque(3:10) true julia> 100 ∈ Deque(-5:5) false
También encontramos que el método first() , que devuelve el primer elemento de la colección, comenzó a funcionar. Para completar la imagen, complementamos el método last() para obtener el último elemento e iterar en el orden inverso:
function Base.iterate(r::Base.Iterators.Reverse{Deque{T}}, state::DequeNode{T}=r.itr.entry) where T nextstate = state.prev nextstate ≡ r.itr.entry ? nothing : (nextstate.data, nextstate) end function Base.last(deq::Deque) isempty(deq) && throw(ArgumentError("deque must be non-empty")) deq.entry.prev.data end julia> for x in Iterators.reverse(Deque(1:10)) println(x); end 10 9 8 7 6 5 4 3 2 1
Entonces, la interfaz de la cola como estructura de datos ahora está completamente definida
Estructura de impresión
Aunque la cola funciona completamente como una estructura de datos, en la impresión todavía representa un desastre sin forma:
julia> Deque() Deque{Any}(DequeNode{Any}(
Agregue un método para imprimir la cola en una forma más humana. La salida de la estructura al terminal está controlada por la función Base.show() , que sobrecargaremos:
function Base.show(io::IO, deq::Deque{T}) where T print(io, "Deque{", T, "}(") next = iterate(deq) if next ≢ nothing item, state = next show(io, item) next = iterate(deq, state) while next ≢ nothing item, state = next print(io, ", ") show(io, item) next = iterate(deq, state) end end print(io, ")") end
Acceso y cambio por índice
En principio, una cola también se puede utilizar como contenedor con acceso por índice. Las getindex() y setindex!() Controlan la recuperación y el cambio de un valor por índice. Implementamos los métodos necesarios para la cola.
function Base.getindex(deq::Deque, i::Integer) i > 0 || throw(BoundsError(deq, i)) next = iterate(deq) for idx in 1:i-1 next ≡ nothing && throw(BoundsError(deq, i)) _, state = next next = iterate(deq, state) end if next ≡ nothing throw(BoundsError(deq, i)) else return next[1] end end function Base.setindex!(deq::Deque, val, i::Integer) i > 0 || throw(BoundsError(deq, i)) next = iterate(deq) for idx in 1:i-1 next ≡ nothing && throw(BoundsError(deq, i)) _, state = next next = iterate(deq, state) end if next ≡ nothing throw(BoundsError(deq, i)) else record = next[2] record.data = val return val end end
¡También es útil agregar la función de insertar un elemento en un lugar arbitrario insert!() Y eliminar un elemento de una posición arbitraria:
function Base.insert!(deq::Deque{T}, i::Integer, val) where T i > 0 || throw(BoundsError(deq, i)) next = iterate(deq) for idx in 1:i-1 next ≡ nothing && throw(BoundsError(deq, i)) _, state = next next = iterate(deq, state) end if next ≡ nothing push!(deq, val) else record = next[2] new_node = DequeNode{T}(val) new_node.prev, new_node.next = record.prev, record record.prev = record.prev.next = new_node deq end end function Base.deleteat!(deq::Deque, i::Integer) i > 0 || throw(BoundsError(deq, i)) next = iterate(deq) for idx in 1:i-1 next ≡ nothing && throw(BoundsError(deq, i)) _, state = next next = iterate(deq, state) end if next ≡ nothing throw(BoundsError(deq, i)) else record = next[2] record.prev.next, record.next.prev = record.next, record.prev end end
Otros
Como ya se mencionó, una serie de funciones de la biblioteca estándar se escriben utilizando iteradores, lo que les permite trabajar automáticamente con cualquier tipo para el que se define la función iterate() . En particular, las funciones como map() , collect() y métodos de reducción como sum() o minimum() .
Por ejemplo, una función para encontrar la longitud de una cola se puede escribir como
Base.length(deq::Deque) = sum(x->1, deq) julia> length(Deque(1, 1, 2, 3, 5, 8, 13)) 7
Conclusión
Como puede ver, crear su propio tipo de datos en Julia y organizar un trabajo conveniente con él es muy simple. Debido al uso de programación generalizada en la biblioteca estándar, generalmente es suficiente definir varias funciones básicas, y varias dependientes funcionarán automáticamente. Entonces, al definir push!(container, element) para agregar un solo elemento, puede encontrar que push!(container, elements...) funcionará para agregar un número arbitrario de argumentos. Una vez definido un iterador, en general obtenemos automáticamente todas las funciones de la biblioteca estándar para trabajar con un contenedor abstracto.
¡Feliz pirateo!