Neste artigo, consideraremos adicionar um tipo de dados personalizado ao programa Julia e sobrecarregar as funções padrão para um trabalho conveniente com o novo tipo.
O que é um tipo personalizado
Um segredo terrível - a fronteira entre os tipos de dados "usuário" e "interno" em Julia está praticamente ausente. Em qualquer programa Julia, você pode definir seus próprios tipos de dados e trabalhar com eles quase não é diferente de trabalhar com os internos, seja em termos de escrita de código ou em termos de velocidade de execução desse código (Olá, Python). Os tipos de dados de entrada podem ser primitivos ou compostos. Estes últimos também são divididos em tipos abstratos e concretos.
Além disso, consideraremos um exemplo de tipos de concreto composto, uma vez que objetos específicos na memória são tipos específicos e objetos abstratos são necessários apenas para criar uma hierarquia.
Tipos compostos são definidos pelas palavras-chave struct e mutable struct . No primeiro caso, um tipo imutável é criado:
Objetos do tipo Point imutáveis, ou seja, o valor do campo no objeto criado uma vez não pode ser alterado.
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
Mas você pode criar um tipo mutável:
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 maior eficiência, as anotações de tipo podem ser adicionadas aos campos da estrutura e à própria estrutura. Por exemplo:
struct ParametricPoint{T<:Real} x::T y::T end
Isso significa que o tipo ParametricPoint parametrizado pelo tipo T e que os campos y devem agora ser valores do mesmo tipo T O comportamento será o seguinte:
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 seguir, vejamos um exemplo um pouco mais complexo de um tipo de contêiner para ver quais métodos existem na biblioteca padrão para trabalhar com esses tipos.
Fila de mão dupla
DequeNode uma fila de DequeNode a partir dos nós do tipo DequeNode , que incluirão um registro de dados e links para os elementos anteriores e seguintes da fila. O tipo DequeNode deve ser mutável, porque os links precisarão ser reescritos.
mutable struct DequeNode{T} data::T prev::DequeNode{T} next::DequeNode{T}
Nesse caso, são necessários construtores internos, porque, por padrão, ao construir um objeto, você precisa passar os valores de todos os campos com argumentos. Como o tipo é auto-referenciado, seria impossível para um construtor padrão criar o primeiro objeto desse tipo. Portanto, criamos construtores especiais que criam um nó da fila que se refere a si mesmo.
A própria fila pode ser representada como um nó de "entrada" fictício que não contém nenhum dado. Seu next link apontará para o primeiro elemento da fila e prev para o último. Para uma fila vazia, os dois links apontam para o nó de entrada. Essa organização simplifica os procedimentos para adicionar e remover nós.
struct Deque{T} entry::DequeNode{T} end Deque{T}() where T = Deque{T}(DequeNode{T}()) Deque() = Deque{Any}()
Um construtor interno não é mais necessário para a estrutura da própria fila.
Adicionando itens
Os procedimentos padrão para uma fila são adicionar um elemento ao início e final e extrair elementos do início e do fim. Para esses procedimentos, a biblioteca padrão já possui funções às quais você só precisa adicionar métodos para trabalhar com outro tipo:
push!(collection, element) - adiciona um elemento à coleção (para uma coleção ordenada - no final)pushfirst!(collection, element) - adicione um elemento ao início de uma coleção ordenadapop!(collection) - exclui um item da coleção (para uma coleção solicitada - no final)popfirst!(collection) - remove o primeiro item de uma coleção encomendada
Todas essas funções estão no módulo Base e você precisa adicionar novos métodos. Além disso, escreveremos uma função para verificar se a coleção não está vazia - 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
A função push!() Torna quase trivial escrever um construtor de filas com base em uma coleção arbitrária:
function Deque(itr) d = Deque{eltype(itr)}() for elt in itr push!(d, elt) end return d end
Agora, o novo tipo pode quase ser usado como uma fila se precisarmos adicionar e remover operações e não precisarmos de uma função como peek() (observe o elemento no início ou no final da fila sem removê-lo). Para acesso não destrutivo aos elementos, é conveniente definir a função de iteração sobre o contêiner.
Iteração
Julia suporta o conceito de iteradores para atravessar elementos de contêiner. Para a iteração, você precisa definir uma única função - iterate(container, state) , em que state determina o estado atual do iterador. Em particular, o construto for for x in collection é um açúcar sintático para algo como isto:
let nextstate = iterate(collection) while nextstate ≢ nothing (x, state) = nextstate <- > nextstate = iterate(collection, state) end end
A função iterate() pega um contêiner e um "estado do iterador" como argumento e retorna uma tupla do elemento contêiner e do próximo estado do iterador ou nothing se o contêiner tiver terminado.
Para uma fila, é lógico considerar o nó da fila, que a iteração atingiu, como o "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
Agora os elementos da fila podem ser iterados com um loop for :
julia> for x in Deque(1:10) println(x); end 1 2 3 4 5 6 7 8 9 10
Uma grande vantagem é que muitas das funções da biblioteca Julia padrão são escritas usando interfaces generalizadas, em particular iteração. Portanto, a verificação automática se um elemento pertence a um contêiner é determinada automaticamente:
julia> 5 ∈ Deque(3:10) true julia> 100 ∈ Deque(-5:5) false
Também descobrimos que o método first() , que retorna o primeiro elemento da coleção, começou a funcionar. Para completar a figura, complementamos o método last() para obter o último elemento e iterar na ordem inversa:
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
Portanto, a interface da fila como uma estrutura de dados agora está totalmente definida
Estrutura de impressão
Embora a fila funcione totalmente como uma estrutura de dados, na impressão ainda representa uma bagunça sem forma:
julia> Deque() Deque{Any}(DequeNode{Any}(
Adicione um método para imprimir a fila em uma forma mais humana. A saída da estrutura para o terminal é controlada pela função Base.show() , que sobrecarregaremos:
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
Acessar e alterar por índice
Em princípio, uma fila também pode ser usada como um contêiner com acesso por índice. A recuperação e alteração de um valor por índice são controladas pelas getindex() e setindex!() . Implementamos os métodos necessários para a fila.
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
Também é útil adicionar a função de inserir um elemento em uma insert!() local arbitrária insert!() E remover um elemento de uma posição arbitrária:
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
Outros
Como já mencionado, várias funções da biblioteca padrão são gravadas usando iteradores, o que lhes permite trabalhar automaticamente com qualquer tipo para o qual a função iterate() está definida. Em particular, funções como map() , collect() e métodos de redução como sum() ou minimum() .
Por exemplo, uma função para encontrar o comprimento de uma fila pode ser escrita como
Base.length(deq::Deque) = sum(x->1, deq) julia> length(Deque(1, 1, 2, 3, 5, 8, 13)) 7
Conclusão
Como você pode ver, criar seu próprio tipo de dados em Julia e organizar um trabalho conveniente com ele é muito simples. Devido ao uso de programação generalizada na biblioteca padrão, geralmente é suficiente definir várias funções básicas, e várias dependentes funcionarão automaticamente. Portanto, definindo push!(container, element) para adicionar um único elemento, você pode descobrir que push!(container, elements...) funcionará para adicionar um número arbitrário de argumentos. Tendo definido um iterador, em geral, obtemos automaticamente todas as funções da biblioteca padrão para trabalhar com um contêiner abstrato.
Feliz hacking!