Dans cet article, nous envisagerons d'ajouter un type de données personnalisé au programme Julia et de surcharger les fonctions standard pour un travail pratique avec le nouveau type.
Qu'est-ce qu'un type personnalisé
Un terrible secret - la frontière entre les types de données «utilisateur» et «intégré» dans Julia est pratiquement absente. Dans tout programme Julia, vous pouvez définir vos propres types de données, et travailler avec eux n'est presque pas différent de travailler avec ceux intégrés, que ce soit en termes d'écriture de code ou en termes de vitesse d'exécution de ce code (bonjour, Python). Les types de données d'entrée peuvent être primitifs ou composites. Ces derniers sont également divisés en types abstraits et concrets.
En outre, nous considérerons un exemple de types de béton composite, puisque les objets spécifiques en mémoire sont des types spécifiques, et les objets abstraits ne sont nécessaires que pour construire une hiérarchie.
Les types composites sont définis par les mots struct clés struct et mutable struct . Dans le premier cas, un type immuable est créé:
Les objets de type Point immuables, c'est-à-dire la valeur du champ dans l'objet une fois créé ne peut pas être modifiée.
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
Mais vous pouvez créer un type 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)
Pour plus d'efficacité, des annotations de type peuvent être ajoutées aux champs de structure et à la structure elle-même. Par exemple:
struct ParametricPoint{T<:Real} x::T y::T end
Cela signifie que le type ParametricPoint paramétré par le type T et que les champs x et y doivent maintenant être des valeurs du même type T Le comportement sera le suivant:
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)
Ensuite, regardons un exemple légèrement plus complexe d'un type de conteneur pour voir quelles méthodes se trouvent dans la bibliothèque standard pour travailler avec de tels types.
File d'attente bidirectionnelle
Nous allons créer une file d'attente bidirectionnelle à partir de nœuds de type DequeNode , qui comprendra un enregistrement de données et des liens vers les éléments précédent et suivant de la file d'attente. Le type DequeNode doit être modifiable, car les liens devront être réécrits.
mutable struct DequeNode{T} data::T prev::DequeNode{T} next::DequeNode{T}
Dans ce cas, les constructeurs internes sont nécessaires, car par défaut, lors de la construction d'un objet, vous devez passer les valeurs de tous les champs avec des arguments. Le type étant auto-référencé, il serait impossible pour un constructeur standard de créer le tout premier objet de ce type. Par conséquent, nous créons des constructeurs spéciaux qui créent un nœud de file d'attente qui se réfère à lui-même.
La file d'attente elle-même peut être représentée comme un nœud «d'entrée» fictif qui ne contient aucune donnée. Son lien next pointera vers le premier élément de la file d'attente et prev vers le dernier. Pour une file d'attente vide, les deux liens pointent vers le nœud d'entrée. Une telle organisation simplifie les procédures d'ajout et de suppression de nœuds.
struct Deque{T} entry::DequeNode{T} end Deque{T}() where T = Deque{T}(DequeNode{T}()) Deque() = Deque{Any}()
Un constructeur interne n'est plus requis pour la structure de la file d'attente elle-même.
Ajout d'éléments
Les procédures standard pour une file d'attente sont l'ajout d'un élément au début et à la fin et l'extraction d'éléments du début et de la fin. Pour ces procédures, la bibliothèque standard possède déjà des fonctions auxquelles il vous suffit d'ajouter des méthodes pour travailler avec un autre type:
push!(collection, element) - ajoute un élément à la collection (pour une collection ordonnée - à la fin)pushfirst!(collection, element) - ajoute un élément au début d'une collection ordonnéepop!(collection) - supprime un article de la collection (pour une collection commandée - de la fin)popfirst!(collection) - supprime le premier article d'une collection commandée
Toutes ces fonctions sont dans le module Base , et vous devez lui ajouter de nouvelles méthodes. De plus, nous allons écrire une fonction pour vérifier si la collection n'est pas vide - 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 fonction push!() Rend presque trivial l'écriture d'un constructeur de file d'attente basé sur une collection arbitraire:
function Deque(itr) d = Deque{eltype(itr)}() for elt in itr push!(d, elt) end return d end
Maintenant, le nouveau type peut presque être utilisé comme file d'attente si nous avons seulement besoin d'ajouter et de supprimer des opérations et nous n'avons pas besoin d'une fonction comme peek() (regardez l'élément dans la tête ou la queue de la file d'attente sans le supprimer). Pour un accès non destructif aux éléments, il est pratique de définir la fonction d'itération sur le conteneur.
Itération
Julia prend en charge le concept d'itérateurs pour parcourir les éléments de conteneur. Pour l'itération, vous devez définir une seule fonction - iterate(container, state) , où l' state détermine l'état actuel de l'itérateur. En particulier, la construction for x in collection est du sucre syntaxique pour quelque chose comme ceci:
let nextstate = iterate(collection) while nextstate ≢ nothing (x, state) = nextstate <- > nextstate = iterate(collection, state) end end
La fonction iterate() prend un conteneur et un «état d'itérateur» comme argument, et retourne soit un tuple de l'élément conteneur et du prochain état d'itérateur, soit nothing si le conteneur est terminé.
Pour une file d'attente, il est logique de prendre le nœud de file d'attente atteint par l'itération comme «état»:
function Base.iterate(deq::Deque{T}, state::DequeNode{T}=deq.entry) where T nextstate = state.next nextstate ≡ deq.entry ? nothing : (nextstate.data, nextstate) end
Maintenant, les éléments de la file d'attente peuvent être triés avec une boucle for :
julia> for x in Deque(1:10) println(x); end 1 2 3 4 5 6 7 8 9 10
Un grand avantage est que de nombreuses fonctions de la bibliothèque Julia standard sont écrites à l'aide d'interfaces généralisées, en particulier l'itération. Ainsi, la vérification automatique de l'appartenance d'un élément à un conteneur est automatiquement déterminée:
julia> 5 ∈ Deque(3:10) true julia> 100 ∈ Deque(-5:5) false
Nous constatons également que la méthode first() , qui renvoie le premier élément de la collection, a commencé à fonctionner. Pour compléter l'image, nous complétons la méthode last() pour obtenir le dernier élément et itérer dans l'ordre inverse:
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
Ainsi, l'interface de file d'attente en tant que structure de données est maintenant entièrement définie
Structure d'impression
Bien que la file d'attente fonctionne pleinement comme une structure de données, à l'impression, elle représente toujours un gâchis sans forme:
julia> Deque() Deque{Any}(DequeNode{Any}(
Ajoutez une méthode pour imprimer la file d'attente sous une forme plus humaine. La sortie de la structure vers le terminal est contrôlée par la fonction Base.show() , que nous surchargerons:
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
Accès et modification par index
En principe, une file d'attente peut également être utilisée comme conteneur avec accès par index. La récupération et la modification d'une valeur par index sont contrôlées par les fonctions getindex() et setindex!() . Nous implémentons les méthodes nécessaires pour la file d'attente.
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
Il est également utile d'ajouter la fonction d'insertion d'un élément à un insert!() lieu arbitraire insert!() Et de supprimer un élément d'une position arbitraire:
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
Autre
Comme déjà mentionné, un certain nombre de fonctions de la bibliothèque standard sont écrites à l'aide d'itérateurs, ce qui leur permet de travailler automatiquement avec tout type pour lequel la fonction iterate() est définie. En particulier, des fonctions telles que map() , collect() et des méthodes de réduction telles que sum() ou minimum() .
Par exemple, une fonction pour trouver la longueur d'une file d'attente peut être écrite comme
Base.length(deq::Deque) = sum(x->1, deq) julia> length(Deque(1, 1, 2, 3, 5, 8, 13)) 7
Conclusion
Comme vous pouvez le voir, créer votre propre type de données dans Julia et organiser un travail pratique avec lui est très simple. En raison de l'utilisation de la programmation généralisée dans la bibliothèque standard, il suffit généralement de définir plusieurs fonctions de base, et un certain nombre de fonctions dépendantes fonctionneront automatiquement. Ainsi, en définissant push!(container, element) pour ajouter un seul élément, vous pouvez trouver que push!(container, elements...) fonctionnera pour ajouter un nombre arbitraire d'arguments. Après avoir défini un itérateur, en général, nous obtenons automatiquement toutes les fonctions de la bibliothèque standard pour travailler avec un conteneur abstrait.
Bon piratage!