Julia: tipe khusus

Pada artikel ini, kami akan mempertimbangkan untuk menambahkan tipe data khusus ke program Julia dan kelebihan fungsi standar untuk pekerjaan mudah dengan tipe baru.

Apa itu tipe khusus

Rahasia yang mengerikan - batas antara tipe data "pengguna" dan "bawaan" di Julia praktis tidak ada. Dalam program Julia apa pun, Anda dapat menentukan tipe data Anda sendiri, dan bekerja dengannya hampir tidak berbeda dengan bekerja dengan data bawaan baik dalam hal penulisan kode atau dalam hal kecepatan eksekusi kode ini (halo, Python). Tipe data input dapat berupa primitif atau komposit. Yang terakhir juga dibagi menjadi tipe abstrak dan konkret.

Selanjutnya kami akan mempertimbangkan contoh jenis beton komposit, karena objek spesifik dalam memori adalah tipe spesifik, dan objek abstrak hanya diperlukan untuk membangun hierarki.

Jenis komposit ditentukan oleh kata kunci struct dan mutable struct . Dalam kasus pertama, jenis yang tidak dapat diubah dibuat:

 #    x  y struct Point x y end 

Objek bertipe Point dapat diubah, mis. nilai bidang dalam objek sekali dibuat tidak dapat diubah.

 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 

Tetapi Anda dapat membuat jenis yang bisa berubah:

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

Untuk efisiensi, anotasi jenis dapat ditambahkan ke bidang struktur dan struktur itu sendiri. Sebagai contoh:

 struct ParametricPoint{T<:Real} x::T y::T end 

Ini berarti bahwa tipe ParametricPoint parameterkan menurut tipe T dan bahwa bidang x dan y sekarang harus nilai dari tipe yang sama T Perilaku tersebut adalah sebagai berikut:

 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} 

Selanjutnya, mari kita lihat contoh yang sedikit lebih kompleks dari jenis wadah untuk melihat metode apa yang ada di perpustakaan standar untuk bekerja dengan jenis seperti itu.

Antrian dua arah

Kami akan membuat antrian dua arah dari node tipe DequeNode , yang akan menyertakan catatan data dan tautan ke elemen antrian sebelumnya dan selanjutnya. Tipe DequeNode harus bisa berubah, karena tautan harus ditulis ulang.

 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 

Dalam hal ini, konstruktor internal diperlukan, karena secara default, ketika membangun objek, Anda harus meneruskan nilai semua bidang dengan argumen. Karena tipe ini merujuk sendiri, tidak mungkin bagi konstruktor standar untuk membuat objek pertama dari tipe ini. Oleh karena itu, kami membuat konstruktor khusus yang membuat simpul antrian yang merujuk pada dirinya sendiri.

Antrian itu sendiri dapat direpresentasikan sebagai simpul "input" fiktif yang tidak mengandung data apa pun. Tautan next akan menunjuk ke elemen pertama dari antrian, dan selanjutnya ke yang terakhir. Untuk antrian kosong, kedua tautan menunjuk ke simpul input. Organisasi semacam itu menyederhanakan prosedur untuk menambah dan menghapus node.

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

Konstruktor internal tidak lagi diperlukan untuk struktur antrian itu sendiri.

Menambahkan Item

Prosedur standar untuk antrian adalah menambahkan elemen ke awal dan akhir, dan mengekstraksi elemen dari awal dan akhir. Untuk prosedur ini, pustaka standar sudah memiliki fungsi yang Anda hanya perlu menambahkan metode untuk bekerja dengan tipe lain:

• push!(collection, element) - tambahkan elemen ke koleksi (untuk koleksi yang dipesan - di akhir)
• pushfirst!(collection, element) - tambahkan elemen ke awal koleksi yang dipesan
• pop!(collection) - hapus item dari koleksi (untuk koleksi yang dipesan - dari akhir)
• popfirst!(collection) - menghapus item pertama dari koleksi yang dipesan

Semua fungsi ini ada di modul Base , dan Anda perlu menambahkan metode baru untuk itu. Selain itu, kami akan menulis fungsi untuk memeriksa apakah koleksi tidak kosong - 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 

Fungsi push!() Membuatnya hampir sepele untuk menulis konstruktor antrian berdasarkan koleksi yang berubah-ubah:

 function Deque(itr) d = Deque{eltype(itr)}() for elt in itr push!(d, elt) end return d end #        Deque(args...) = Deque(args) 

Sekarang tipe baru hampir dapat digunakan sebagai antrian jika kita hanya perlu menambah dan menghapus operasi dan kita tidak memerlukan fungsi seperti peek() (lihat elemen di kepala atau ekor antrian tanpa menghapusnya). Untuk akses non-destruktif ke elemen, lebih mudah untuk mendefinisikan fungsi iterasi di atas wadah.

Iterasi

Julia mendukung konsep iterator untuk melintasi elemen kontainer. Untuk iterasi, Anda perlu mendefinisikan fungsi tunggal - iterate(container, state) , di mana state menentukan status iterator saat ini. Secara khusus, for x in collection konstruk for x in collection adalah gula sintaksis untuk sesuatu seperti ini:

 let nextstate = iterate(collection) while nextstate ≢ nothing (x, state) = nextstate <- > nextstate = iterate(collection, state) end end 

Fungsi iterate() mengambil wadah dan "keadaan iterator" sebagai argumen, dan mengembalikan tupel dari elemen wadah dan keadaan iterator berikutnya, atau nothing jika wadah telah berakhir.
Untuk antrian, masuk akal untuk mengambil simpul antrian, yang telah dicapai oleh iterasi, sebagai "status":

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

Sekarang elemen-elemen dari antrian dapat disortir dengan for :

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

Nilai tambah yang besar adalah bahwa banyak fungsi perpustakaan Julia standar ditulis menggunakan antarmuka umum, khususnya, iterasi. Dengan demikian, secara otomatis memeriksa apakah suatu elemen milik suatu wadah ditentukan secara otomatis:

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

Kami juga menemukan bahwa metode first() , yang mengembalikan elemen pertama koleksi, mulai berfungsi. Untuk melengkapi gambar, kami melengkapi metode last() untuk mendapatkan elemen terakhir dan mengulanginya dalam urutan terbalik:

 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 

Jadi, antarmuka antrian sebagai struktur data sekarang sepenuhnya ditentukan

Struktur cetakan

Meskipun antrian berfungsi penuh sebagai struktur data, pada cetakan itu masih merupakan kekacauan tak berbentuk:

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

Tambahkan metode untuk mencetak antrian dalam bentuk yang lebih manusiawi. Output dari struktur ke terminal dikontrol oleh fungsi Base.show() , yang akan kita overload:

 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}()) 

Akses dan ubah berdasarkan indeks

Pada prinsipnya, antrian juga dapat digunakan sebagai wadah dengan akses menurut indeks. Mengambil dan mengubah nilai berdasarkan indeks dikontrol oleh fungsi getindex() dan setindex!() . Kami menerapkan metode yang diperlukan untuk antrian.

 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 

Ini juga berguna untuk menambahkan fungsi untuk memasukkan elemen ke dalam insert!() tempat arbitrary insert!() Dan untuk menghapus elemen dari posisi arbitrer:

 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 

Lainnya

Seperti yang telah disebutkan, sejumlah fungsi pustaka standar ditulis menggunakan iterator, yang memungkinkan mereka untuk bekerja secara otomatis dengan tipe apa pun yang fungsi iterate() didefinisikan. Secara khusus, fungsi seperti map() , collect() dan metode pengurangan seperti sum() atau minimum() .
Misalnya, fungsi untuk menemukan panjang antrian dapat ditulis sebagai

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

Kesimpulan

Seperti yang Anda lihat, membuat tipe data Anda sendiri di Julia dan mengatur pekerjaan yang nyaman dengannya sangat sederhana. Karena penggunaan pemrograman umum di perpustakaan standar, biasanya cukup untuk mendefinisikan beberapa fungsi dasar, dan sejumlah yang tergantung akan bekerja secara otomatis. Jadi, dengan mendefinisikan push!(container, element) untuk menambahkan elemen tunggal, Anda dapat menemukan push!(container, elements...) akan berfungsi untuk menambahkan sejumlah argumen sembarang. Setelah mendefinisikan iterator, secara umum kami secara otomatis mendapatkan semua fungsi perpustakaan standar untuk bekerja dengan wadah abstrak.

Selamat melakukan peretasan!