Хабрахабр

Julia: пользовательские типы

В этой статье рассмотрим добавление в программу на Julia пользовательского типа данных и перегрузку стандартных функций для удобной работы с новым типом.

Что такое пользовательский тип

В любой программе на Julia можно доопределить собственные типы данных, и работа с ними от работы со встроенными почти ничем не отличается ни с точки зрения написания кода, ни с точки зрения скорости исполнения этого кода (привет, Python). Страшная тайна — граница между "пользовательскими" и "встроенными" типами данных в Julia практически отсутствует. Вторые делятся также на абстрактные и конкретные типы. Вводимые типы данных могут быть либо примитивными, либо составными.

конкретные объекты в памяти относятся к конкретным типам, а абстрактные нужны только для построения иерархии. Далее будем рассматривать пример составных конкретных типов, т.к.

В первом случае создаётся неизменяемый тип: Составные типы определяются ключевыми словами struct и mutable struct.

# структура с полями x и y
struct Point x y
end

значение поля в однажды созданном объекте нельзя изменить. Объекты типа Point неизменяемы, т.е.

julia> p = Point(2, 3)
Point(2, 3) julia> p.x
2 julia> p.y
3 julia> p.x = 4
ERROR: setfield! immutable struct of type Point cannot be changed

Но можно сделать и изменяемый тип:

mutable struct MutablePoint x y
end julia> mp = MutablePoint(3, 4)
MutablePoint(3, 4) julia> mp.y = 2
2 julia> mp
MutablePoint(3, 2)

Например: Для эффективности полям структуры и самой структуре можно добавить аннотации типа.

struct ParametricPoint x::T y::T
end

Поведение будет таким: Это значит, что тип ParametricPoint параметризован типом T и что поля x и y теперь должны быть значениями одного и того же типа T.

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) # ошибка: один из аргументов не приводится к типу T
julia> ParametricPoint{Int}(1, 3.4)
ERROR: InexactError: Int64(3.4) # ошибка: аргументы разных типов
julia> ParametricPoint(1, 1.0)
ERROR: MethodError: no method matching Point(::Int64, ::Float64) # ошибка: тип T должен относиться к действительным числам
julia> ParametricPoint{Any}(1,1)
ERROR: TypeError: in Point, in T, expected T<:Real, got Type{Any}

Далее рассмотрим чуть более сложный пример типа-контейнера, чтобы увидеть, какие методы есть в стандартной библиотеке для работы с такими типами.

Двусторонняя очередь

Тип DequeNode обязательно должен быть изменяемым, т.к. Двустороннюю очередь сделаем из узлов типа DequeNode, которые будут включать запись с данными и ссылки на предыдущий и следующий элементы очереди. ссылки нужно будет перезаписывать.

mutable struct DequeNode{T} data::T prev::DequeNode{T} next::DequeNode{T} # пустой конструктор - возвращает не до конца инициализированную структуру function DequeNode{T}() where T node = new{T}() node.prev = node.next = node return node end # конструктор с начальным значением function DequeNode{T}(x) where T node = new{T}() node.data = x node.prev = node.next = node return node end
end

Поскольку тип задан самореферентно, стандартным конструктором невозможно было бы создать самый первый объект этого типа. Внутренние конструкторы в данном случае нужны, поскольку по умолчанию при конструировании объекта нужно передать аргументами значения всех полей. Поэтому делаем специальные конструкторы, которые создают узел очереди, ссылающийся сам на себя.

Его ссылка next будет указывать на первый элемент очереди, а prev — на последний. Саму очередь можно представить как фиктивный "входной" узел, не содержащий никаких данных. Такая организация упрощает процедуры добавления и удаления узлов. Для пустой очереди обе ссылки указывают на входной узел.

struct Deque{T} entry::DequeNode{T}
end Deque{T}() where T = Deque{T}(DequeNode{T}())
Deque() = Deque{Any}()

Для структуры самой очереди внутренний конструктор уже не требуется.

Добавление элементов

Для этих процедур в стандартной библиотеке уже есть функции, к которым нужно будет только добавить методы работы с ещё одним типом: Стандартными процедурами для очереди являются добавление элемента в начало и в конец и извлечение элементов из начала и конца.

  • push!(collection, element) — добавление элемента в коллекцию (для упорядоченной коллекции — в конец)
  • pushfirst!(collection, element) — добавление элемента в начало упорядоченной коллекции
  • pop!(collection) — удаление элемента из коллекции (для упорядоченной коллекции — из конца)
  • popfirst!(collection) — удаление первого элемента из упорядоченной коллекции

Дополнительно напишем функцию проверки, не пустая ли коллекция — Base.isempty(collection). Все эти функции находятся в модуле Base, в него и нужно добавить новые методы.

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

Функция push!() позволяет почти тривиально написать конструктор очереди на основе произвольной коллекции:

function Deque(itr) d = Deque{eltype(itr)}() for elt in itr push!(d, elt) end return d
end # а ещё конструктор с переменным числом аргументов
Deque(args...) = Deque(args)

Для неразрушающего доступа к элементам удобно определить функцию итерирования по контейнеру. Теперь новым типом уже почти можно пользоваться как очередью, если нам нужны только операции добавления и удаления и не требуется функция типа peek() (посмотреть элемент в голове или хвосте очереди, не извлекая его).

Итерирование

Для итерирования нужно определить единственную функцию — iterate(container, state), где state определяет текущее состояние итератора. В Julia поддерживается концепция итераторов для прохода по элементам контейнера. В частности, конструкция for x in collection — это синтаксический сахар для примерно такого кода:

let nextstate = iterate(collection) while nextstate ≢ nothing (x, state) = nextstate <что-то сделать> nextstate = iterate(collection, state) end
end

Функция iterate() принимает аргументом контейнер и "состояние итератора", а возвращает — либо кортеж из элемента контейнера и следующего состояния итератора, либо nothing, если контейнер закончился.
Для очереди логично в качестве "состояния" взять узел очереди, до которого дошла итерация:

function Base.iterate(deq::Deque{T}, state::DequeNode{T}=deq.entry) where T nextstate = state.next nextstate ≡ deq.entry ? nothing : (nextstate.data, nextstate)
end

Теперь элементы очереди можно перебирать циклом for:

julia> for x in Deque(1:10) println(x); end
1
2
3
4
5
6
7
8
9
10

Таким образом, автоматически доопределяется проверка принадлежности элемента контейнеру: Большим плюсом является то, что многие функции стандартной библиотеки Julia написаны с использованием обобщённых интерфейсов, в частности, итерирования.

julia> 5 ∈ Deque(3:10)
true julia> 100 ∈ Deque(-5:5)
false

Для полноты картины дополним метод last() для получения последнего элемента и итерирование в обратном порядке: Также обнаруживаем, что стал работать метод first(), возвращающий первый элемент коллекции.

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

Итак, интерфейс очереди как структуры данных теперь полностью определён

Распечатка структуры

Хотя очередь полностью функционирует как структура данных, на печати она пока представляет форменное безобразие:

julia> Deque()
Deque{Any}(DequeNode{Any}(#undef, DequeNode{Any}(#= circular reference @-1 =#), DequeNode{Any}(#= circular reference @-1 =#)))

Вывод структуры в терминал контролируется функцией Base.show(), которую и будем перегружать: Добавим метод, чтобы очередь печаталась в более человеческом виде.

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 # Теперь печатается в намного более приятном виде
julia> Deque(1:5)
Deque{Int64}(1, 2, 3, 4, 5)
# очередь из очередей тоже печатается корректно
julia> Deque(Deque(), Deque(), Deque())
Deque{Deque{Any}}(Deque{Any}(), Deque{Any}(), Deque{Any}())

Доступ и изменение по индексу

Получение и изменение значения по индексу контролируются функциями getindex() и setindex!(). В принципе, очередь можно использовать и как контейнер с доступом по индексу. Реализуем нужные методы для очереди.

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

Полезно также добавить функции вставки элемента в произвольное место insert!() и удаления элемента из произвольной позиции:

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

Прочее

В частности, будут работать функции типа map(), collect() и методы редукции, такие как sum() или minimum().
Например, функцию для нахождения длины очереди можно написать так: Как уже было сказано, ряд функций стандартной библиотеки написан с использованием итераторов, что позволяет им автоматически работать с любым типом, для которого определена функция iterate().

Base.length(deq::Deque) = sum(x->1, deq) julia> length(Deque(1, 1, 2, 3, 5, 8, 13))
7

Заключение

Благодаря использованию обобщённого программирования в стандартной библиотеке, обычно достаточно определить несколько основных функций, и ряд зависящих от них станет работать автоматически. Как видим, создать в Julia собственный тип данных и организовать удобную работу с ним весьма просто. Определив итератор, вообще получаем автоматом все функции стандартной библиотеки для работы с абстрактным контейнером. Так, определив push!(container, element) для добавления единственного элемента, можно обнаружить, что будет работать и push!(container, elements...) для добавления произвольного числа аргументов.

Happy Hacking!

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть