julia> a = [1 2 3; 4 5 6] 2×3 Matrix{Int64}: 1 2 3 4 5 6 julia> eltype(a) Int64 julia> ndims(a) 2 julia> size(a) (2, 3) julia> size(a, 1) 2 julia> size(a, 2) 3 julia> b = copy(a) 2×3 Matrix{Int64}: 1 2 3 4 5 6 julia> b[1, 1] = 10 10 julia> a 2×3 Matrix{Int64}: 1 2 3 4 5 6 julia> b 2×3 Matrix{Int64}: 10 2 3 4 5 6 julia> Vector{Int}(undef, 5) 5-element Vector{Int64}: 0 0 0 0 0 julia> Matrix{Int}(undef, 3, 4) 3×4 Matrix{Int64}: 0 0 0 0 0 0 0 0 0 0 0 0 julia> Matrix{Float64}(undef, 3, 4) 3×4 Matrix{Float64}: 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 julia> using LinearAlgebra julia> Matrix{Float64}(I, 4, 4) 4×4 Matrix{Float64}: 1.0 0.0 0.0 0.0 0.0 1.0 0.0 0.0 0.0 0.0 1.0 0.0 0.0 0.0 0.0 1.0 julia> rand(3, 3) 3×3 Matrix{Float64}: 0.656057 0.13851 0.624263 0.918642 0.923451 0.218356 0.138388 0.717213 0.786006 julia> randn(3, 3) 3×3 Matrix{Float64}: -1.54448 -0.133406 1.29957 -1.85525 -0.591922 -0.70398 0.422188 0.315499 0.811839 julia> fill(10, 2, 3) 2×3 Matrix{Int64}: 10 10 10 10 10 10 julia> fill!(b, 100) 2×3 Matrix{Int64}: 100 100 100 100 100 100 julia> b 2×3 Matrix{Int64}: 100 100 100 100 100 100 julia> reshape(b, 3, 2) 3×2 Matrix{Int64}: 100 100 100 100 100 100 julia> reshape(b, 1, 6) 1×6 Matrix{Int64}: 100 100 100 100 100 100 julia> reshape(b, 6, 1) 6×1 Matrix{Int64}: 100 100 100 100 100 100 julia> reshape(collect(1:16), 4, 4) 4×4 Matrix{Int64}: 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16
julia> a = [11 12 13 14; 15 16 17 18; 19 20 21 22] 3×4 Matrix{Int64}: 11 12 13 14 15 16 17 18 19 20 21 22 julia> stride(a, 1) 1 julia> stride(a, 2) 3 julia> strides(a) (1, 3) julia> a[1] 11 julia> a[2] 15 julia> a[3] 19 julia> a[12] 22 julia> a[11] 18 julia> a[10] 14 julia> for x = eachindex(a) print(x, " ") end 1 2 3 4 5 6 7 8 9 10 11 12
julia> a = collect(1 : 8) 8-element Vector{Int64}: 1 2 3 4 5 6 7 8 julia> a[3 : 5] 3-element Vector{Int64}: 3 4 5 julia> a[1 : 2 : end] 4-element Vector{Int64}: 1 3 5 7 julia> a[end : -1 : 1] 8-element Vector{Int64}: 8 7 6 5 4 3 2 1 julia> b = a[:] 8-element Vector{Int64}: 1 2 3 4 5 6 7 8 julia> b[1] = 10 10 julia> b[2 : 4] = [11, 12, 13] 3-element Vector{Int64}: 11 12 13 julia> b 8-element Vector{Int64}: 10 11 12 13 5 6 7 8 julia> a 8-element Vector{Int64}: 1 2 3 4 5 6 7 8 julia> b[[3, 2, 1]] 3-element Vector{Int64}: 12 11 10 julia> c = reshape(collect(1 : 16), 4, 4) 4×4 Matrix{Int64}: 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16 julia> c[1 : 3, 2 : 4] 3×3 Matrix{Int64}: 5 9 13 6 10 14 7 11 15 julia> c[[1, 3], [3, 2, 1]] 2×3 Matrix{Int64}: 9 5 1 11 7 3 julia> c[[1, 3], 4] 2-element Vector{Int64}: 13 15 julia> c[2, [1, 3]] 2-element Vector{Int64}: 2 10 julia> c[1 : 2, 1 : 2] = [100 200; 300 400] 2×2 Matrix{Int64}: 100 200 300 400 julia> c 4×4 Matrix{Int64}: 100 200 9 13 300 400 10 14 3 7 11 15 4 8 12 16
julia> a = collect(11 : 18) 8-element Vector{Int64}: 11 12 13 14 15 16 17 18 julia> a[[1 3; 5 6]] 2×2 Matrix{Int64}: 11 13 15 16 julia> a[[1 2; 3 4]] = [1 2; 3 4] 2×2 Matrix{Int64}: 1 2 3 4 julia> a 8-element Vector{Int64}: 1 2 3 4 15 16 17 18 julia> a[[1 2; 3 4]] = [1, 2, 3, 4] 4-element Vector{Int64}: 1 2 3 4 julia> a 8-element Vector{Int64}: 1 3 2 4 15 16 17 18 julia> b = reshape(collect(11:37), 3, 3, 3) 3×3×3 Array{Int64, 3}: [:, :, 1] = 11 14 17 12 15 18 13 16 19 [:, :, 2] = 20 23 26 21 24 27 22 25 28 [:, :, 3] = 29 32 35 30 33 36 31 34 37 julia> c = reshape(collect(1:8), 2, 2, 2) 2×2×2 Array{Int64, 3}: [:, :, 1] = 1 3 2 4 [:, :, 2] = 5 7 6 8 julia> b[c] 2×2×2 Array{Int64, 3}: [:, :, 1] = 11 13 12 14 [:, :, 2] = 15 17 16 18 julia> b[[1 2; 3 4]] 2×2 Matrix{Int64}: 11 12 13 14 julia> d = rand(3, 3) 3×3 Matrix{Float64}: 0.501875 0.775976 0.344637 0.360713 0.184347 0.59974 0.924875 0.371442 0.251967 julia> d[[true, false, true], :] 2×3 Matrix{Float64}: 0.501875 0.775976 0.344637 0.924875 0.371442 0.251967 julia> d[[true false true; false true false; true false true]] 5-element Vector{Float64}: 0.5018752512220828 0.9248752675744198 0.1843468573998286 0.34463739835964713 0.25196665765465065
julia> a = [1 2 3; 4 5 6] 2×3 Matrix{Int64}: 1 2 3 4 5 6 julia> b = [11 12 13; 14 15 16] 2×3 Matrix{Int64}: 11 12 13 14 15 16 julia> cat(a, b, dims=1) 4×3 Matrix{Int64}: 1 2 3 4 5 6 11 12 13 14 15 16 julia> cat(a, b, dims=2) 2×6 Matrix{Int64}: 1 2 3 11 12 13 4 5 6 14 15 16 julia> vcat(a, b) 4×3 Matrix{Int64}: 1 2 3 4 5 6 11 12 13 14 15 16 julia> hcat(a, b) 2×6 Matrix{Int64}: 1 2 3 11 12 13 4 5 6 14 15 16 julia> hvcat((2, 2), 1, 2, 3, 4) 2×2 Matrix{Int64}: 1 2 3 4 julia> hvcat((2, 2, 2), 1, 2, 3, 4, 5, 6) 3×2 Matrix{Int64}: 1 2 3 4 5 6 julia> hvcat((3, 3), 1, 2, 3, 4, 5, 6) 2×3 Matrix{Int64}: 1 2 3 4 5 6 julia> c = reshape(1:8, 2,2,2) 2×2×2 reshape(::UnitRange{Int64}, 2, 2, 2) with eltype Int64: [:, :, 1] = 1 3 2 4 [:, :, 2] = 5 7 6 8 julia> d = reshape(11:18, 2,2,2) 2×2×2 reshape(::UnitRange{Int64}, 2, 2, 2) with eltype Int64: [:, :, 1] = 11 13 12 14 [:, :, 2] = 15 17 16 18 julia> cat(c, d, dims=1) 4×2×2 Array{Int64, 3}: [:, :, 1] = 1 3 2 4 11 13 12 14 [:, :, 2] = 5 7 6 8 15 17 16 18 julia> cat(c, d, dims=2) 2×4×2 Array{Int64, 3}: [:, :, 1] = 1 3 11 13 2 4 12 14 [:, :, 2] = 5 7 15 17 6 8 16 18 julia> cat(c, d, dims=3) 2×2×4 Array{Int64, 3}: [:, :, 1] = 1 3 2 4 [:, :, 2] = 5 7 6 8 [:, :, 3] = 11 13 12 14 [:, :, 4] = 15 17 16 18
view(A, indexing...) @view A[indexing...]
julia> a = reshape(collect(1 : 16), 4, 4) 4×4 Matrix{Int64}: 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16 julia> b = view(a, :, 1) 4-element view(::Matrix{Int64}, :, 1) with eltype Int64: 1 2 3 4 julia> b[1] 1 julia> b[4] 4 julia> b[4] *= 10 40 julia> b 4-element view(::Matrix{Int64}, :, 1) with eltype Int64: 1 2 3 40 julia> a 4×4 Matrix{Int64}: 1 5 9 13 2 6 10 14 3 7 11 15 40 8 12 16 julia> c = @view a[4, :] 4-element view(::Matrix{Int64}, 4, :) with eltype Int64: 40 8 12 16 julia> fill!(c, 0) 4-element view(::Matrix{Int64}, 4, :) with eltype Int64: 0 0 0 0 julia> a 4×4 Matrix{Int64}: 1 5 9 13 2 6 10 14 3 7 11 15 0 0 0 0 julia> d = @view a[3:end, 3:end] 2×2 view(::Matrix{Int64}, 3:4, 3:4) with eltype Int64: 11 15 0 0 julia> d[:,:] = [1 2; 3 4] 2×2 Matrix{Int64}: 1 2 3 4 julia> a 4×4 Matrix{Int64}: 1 5 9 13 2 6 10 14 3 7 1 2 0 0 3 4 julia> parent(b) 4×4 Matrix{Int64}: 1 5 9 13 2 6 10 14 3 7 1 2 0 0 3 4 julia> parentindices(b) (Base.Slice(Base.OneTo(4)), 1) julia> @view a[parentindices(b)...] 4-element view(::Matrix{Int64}, :, 1) with eltype Int64: 1 2 3 0 julia> parent(c) 4×4 Matrix{Int64}: 1 5 9 13 2 6 10 14 3 7 1 2 0 0 3 4 julia> parentindices(c) (4, Base.Slice(Base.OneTo(4))) julia> @view a[parentindices(c)...] 4-element view(::Matrix{Int64}, 4, :) with eltype Int64: 0 0 3 4 julia> parent(d) 4×4 Matrix{Int64}: 1 5 9 13 2 6 10 14 3 7 1 2 0 0 3 4 julia> parentindices(d) (3:4, 3:4) julia> @view a[parentindices(d)...] 2×2 view(::Matrix{Int64}, 3:4, 3:4) with eltype Int64: 1 2 3 4
julia> a = rand(3, 3) 3×3 Matrix{Float64}: 0.774048 0.174833 0.533835 0.527699 0.28474 0.712182 0.0534123 0.160258 0.237476 julia> b = rand(3, 3) 3×3 Matrix{Float64}: 0.0766265 0.595025 0.365214 0.887855 0.233891 0.899877 0.190746 0.0984789 0.438805 julia> a .+ b 3×3 Matrix{Float64}: 0.850675 0.769858 0.899048 1.41555 0.518631 1.61206 0.244159 0.258737 0.676281 julia> a .- b 3×3 Matrix{Float64}: 0.697422 -0.420193 0.168621 -0.360156 0.0508489 -0.187695 -0.137334 0.0617789 -0.201329 julia> a .* b 3×3 Matrix{Float64}: 0.0593126 0.10403 0.194964 0.46852 0.0665981 0.640876 0.0101882 0.015782 0.104205 julia> a ./ b 3×3 Matrix{Float64}: 10.1016 0.293824 1.46171 0.594353 1.2174 0.791421 0.280017 1.62733 0.541188 julia> a .+ 10 3×3 Matrix{Float64}: 10.774 10.1748 10.5338 10.5277 10.2847 10.7122 10.0534 10.1603 10.2375 julia> a .* 10 3×3 Matrix{Float64}: 7.74048 1.74833 5.33835 5.27699 2.8474 7.12182 0.534123 1.60258 2.37476 julia> a .- 10 3×3 Matrix{Float64}: -9.22595 -9.82517 -9.46617 -9.4723 -9.71526 -9.28782 -9.94659 -9.83974 -9.76252 julia> a ./ 10 3×3 Matrix{Float64}: 0.0774048 0.0174833 0.0533835 0.0527699 0.028474 0.0712182 0.00534123 0.0160258 0.0237476 julia> sin.(a) 3×3 Matrix{Float64}: 0.699036 0.173944 0.508838 0.503546 0.280908 0.653487 0.0533869 0.159573 0.23525 julia> square(x) = x * x square (generic function with 1 method) julia> square.(a) 3×3 Matrix{Float64}: 0.599151 0.0305665 0.284979 0.278466 0.0810768 0.507203 0.00285287 0.0256826 0.0563947 julia> a .^ 2 3×3 Matrix{Float64}: 0.599151 0.0305665 0.284979 0.278466 0.0810768 0.507203 0.00285287 0.0256826 0.0563947
julia> a = [1 2; 3 4] 2×2 Matrix{Int64}: 1 2 3 4 julia> b = [5 6; 7 8] 2×2 Matrix{Int64}: 5 6 7 8 julia> c = a * b 2×2 Matrix{Int64}: 19 22 43 50 julia> inv(a) 2×2 Matrix{Float64}: -2.0 1.0 1.5 -0.5 julia> a * inv(a) 2×2 Matrix{Float64}: 1.0 0.0 8.88178e-16 1.0 julia> inv(a) * c 2×2 Matrix{Float64}: 5.0 6.0 7.0 8.0 julia> a \ c 2×2 Matrix{Float64}: 5.0 6.0 7.0 8.0 julia> [1 1; 1 0] ^ 2 2×2 Matrix{Int64}: 2 1 1 1 julia> [1 1; 1 0] ^ 3 2×2 Matrix{Int64}: 3 2 2 1 julia> [1 1; 1 0] ^ 4 2×2 Matrix{Int64}: 5 3 3 2 julia> [1 1; 1 0] ^ 10 2×2 Matrix{Int64}: 89 55 55 34 julia> [1 1; 1 0] ^ 40 2×2 Matrix{Int64}: 165580141 102334155 102334155 63245986 julia> a' 2×2 adjoint(::Matrix{Int64}) with eltype Int64: 1 3 2 4 julia> transpose(a) 2×2 transpose(::Matrix{Int64}) with eltype Int64: 1 3 2 4 julia> [1 2 3; 4 5 6; 7 8 9]' 3×3 adjoint(::Matrix{Int64}) with eltype Int64: 1 4 7 2 5 8 3 6 9 julia> transpose([1 2 3; 4 5 6; 7 8 9]) 3×3 transpose(::Matrix{Int64}) with eltype Int64: 1 4 7 2 5 8 3 6 9
x + y = 100 2x + 4y = 272
julia> [1 1; 2 4] \ [100, 272] 2-element Vector{Float64}: 64.0 36.0
x + y + z = 10 2x + 4y + 6z = 38 2x + 4z = 14
julia> [1 1 1; 2 4 6; 2 0 4] \ [10, 38, 14] 3-element Vector{Float64}: 3.0 5.0 2.0
julia> using LinearAlgebra julia> a = [1 2 3; 4 5 6; 7 8 10] 3×3 Matrix{Int64}: 1 2 3 4 5 6 7 8 10 julia> det(a) -3.0 julia> tr(a) 16 julia> rank(a) 3 julia> diag(a) 3-element Vector{Int64}: 1 5 10 julia> diag(a, 1) 2-element Vector{Int64}: 2 6 julia> diag(a, 2) 1-element Vector{Int64}: 3 julia> diag(a, -1) 2-element Vector{Int64}: 4 8 julia> diag(a, -2) 1-element Vector{Int64}: 7 julia> diagm(0 => [1, 2, 3]) 3×3 Matrix{Int64}: 1 0 0 0 2 0 0 0 3 julia> diagm(1 => [1, 2, 3]) 4×4 Matrix{Int64}: 0 1 0 0 0 0 2 0 0 0 0 3 0 0 0 0 julia> diagm(-1 => [1, 2, 3]) 4×4 Matrix{Int64}: 0 0 0 0 1 0 0 0 0 2 0 0 0 0 3 0 julia> diagm(0 => [1, 1, 1, 1], -1 => [1, 2, 3]) 4×4 Matrix{Int64}: 1 0 0 0 1 1 0 0 0 2 1 0 0 0 3 1 julia> norm([1, 1]) 1.4142135623730951 julia> norm([1, 1, 1]) 1.7320508075688772 julia> dot([1, 2], [3, 4]) 11 julia> dot([1, 2, 3], [4, 5, 6]) 32
# # sort.jl : ファイルのソート # # Copyright 2016-2021 Makoto Hiroi # # 単純挿入ソート function insert_sort!(buff::Vector{T}) where {T} for i = 2 : length(buff) temp = buff[i] j = i - 1 while j > 0 && temp < buff[j] buff[j + 1] = buff[j] j -= 1 end buff[j + 1] = temp end end # 中央値を返す function median3(a, b, c) if a > b if b > c b elseif a < c a else c end else if b < c b elseif a < c c else a end end end # 9 つの中から中央値を選ぶ function median9(buff, low, high) m2 = div(high - low, 2) m4 = div(m2, 2) m8 = div(m4, 2) a = buff[low] b = buff[low + m8] c = buff[low + m4] d = buff[low + m2 - m8] e = buff[low + m2] f = buff[low + m2 + m8] g = buff[high - m4] h = buff[high - m8] i = buff[high] median3(median3(a,b,c), median3(d,e,f), median3(g,h,i)) end # クイックソート function quick_sort!(buff::Vector{T}) where {T} function qsort(low::Int, high::Int) if high - low < 16 return end pivot = median9(buff, low, high) i = low j = high while true while pivot > buff[i]; i += 1; end while pivot < buff[j]; j -= 1; end if i >= j; break; end buff[i], buff[j] = buff[j], buff[i] i += 1 j -= 1 end qsort(low, i - 1) qsort(j + 1, high) end # qsort(1, length(buff)) insert_sort!(buff) end # ファイルのソート function sort(fin) buff = readlines(fin) quick_sort!(buff) for x = buff println(x) end end if length(ARGS) == 0 sort(stdin) elseif length(ARGS) == 1 open(ARGS[1], "r") do fin sort(fin) end else println("usage: julia sort.jl [filename]") end
フィボナッチ数 Fn の漸化式を行列で表すと次のようになります。
F0 = 0 F1 = 1 [Fn Fn-1] = [1 1; 1 0] * [Fn-1 Fn-2]
したがって、Fn を求める問題は行列 [1 1; 1 0] の n 乗を求める問題に帰着します。xn は log2 n 程度の手間で求めることが可能です。Fn を繰り返しで求めると n に比例する時間がかかるので、n が大きくなると行列を使ったほうが速くなると思われます。
リスト : フィボナッチ数 function fibo(n) if n == 0 0 elseif n == 1 1 else f = ([1 1; 1 0] ^ (n - 1)) * [1, 0] f[1] end end for x = 0 : 40 print("$(fibo(x)) ") end
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155
フィボナッチ数列の最初の 2 項を 2, 1 に置き換えた数列の項を「リュカ数 (Lucas number)」といいます。
リスト : リュカ数 function lucas(n) if n == 0 2 elseif n == 1 1 else f = ([1 1; 1 0] ^ (n - 1)) * [1, 2] f[1] end end for x = 0 : 40 print("$(lucas(x)) ") end
2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349 15127 24476 39603 64079 103682 167761 271443 439204 710647 1149851 1860498 3010349 4870847 7881196 12752043 20633239 33385282 54018521 87403803 141422324 228826127
次の漸化式で生成される数列をトリボナッチ数列といいます。
T0 = T1 = 0, T2 = 1 Tn+3 = Tn+2 + Tn+1 + Tn
リスト : トリボナッチ数 function tribo(n) if n == 0 || n == 1 0 elseif n == 2 1 else t = ([1 1 1; 1 0 0; 0 1 0] ^ (n - 2)) * [1, 0, 0] t[1] end end for x = 0 : 30 print("$(tribo(x)) ") end
0 0 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 121415 223317 410744 755476 1389537 2555757 4700770 8646064 15902591
次の漸化式で生成される数列をテトラナッチ数列といいます。
T0 = T1 = T2 = 0, T3 = 1 Tn+4 = Tn+3 + Tn+2 + Tn+1 + Tn
リスト : テトラナッチ数列 function tetra(n) if n == 0 || n == 1 || n == 2 0 elseif n == 3 1 else t = ([1 1 1 1; 1 0 0 0 ; 0 1 0 0; 0 0 1 0] ^ (n - 3)) * [1, 0, 0, 0] t[1] end end for x = 0 : 30 print("$(tetra(x)) ") end
0 0 0 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312 283953 547337 1055026 2033628 3919944 7555935 14564533 28074040
# # list.jl : mutable な連結リスト # # Copyright (C) 2016-2021 Makoto Hiroi # # 抽象型 abstract type List end # セル mutable struct Cell <: List item next :: List end # 終端 # メンバ変数の無い immutable なデータ型を生成すると # シングルトンオブジェクトを返す struct Nil <: List end nil = Nil() # アクセス関数 car(xs::Cell) = xs.item cdr(xs::Cell) = xs.next set_car!(xs::Cell, x) = xs.item = x set_cdr!(xs::Cell, cp::List) = xs.next = cp null(xs::List) = xs == nil # 連結リスト struct LinkedList top :: List LinkedList() = new(Cell(nil, nil)) end # 作業用 function nth_cell(xs::List, n::Int) i = -1 while !null(xs) if i == n; break; end i += 1 xs = cdr(xs) end xs end # 参照 function nth(xs::LinkedList, n::Int) cp = nth_cell(xs.top, n) if null(cp) error("nth: out of range") else car(cp) end end # 更新 function set!(xs::LinkedList, n::Int, x) cp = nth_cell(xs.top, n) if null(cp) error("set!: out of range") else set_car!(cp, x) end end # 挿入 function Base.insert!(xs::LinkedList, n::Int, x) cp = nth_cell(xs.top, n - 1) if null(cp) error("insert!: out of range") else set_cdr!(cp, Cell(x, cdr(cp))) end end # 削除 function Base.delete!(xs::LinkedList, n::Int) cp = nth_cell(xs.top, n - 1) if null(cp) || null(cdr(cp)) error("delete!: out of range") else set_cdr!(cp, cdr(cdr(cp))) end end # 長さ function Base.length(xs::LinkedList) n = 0 cp = cdr(xs.top) while !null(cp) n += 1 cp = cdr(cp) end n end # 空リストか? function Base.isempty(xs::LinkedList) null(cdr(xs.top)) end # 巡回 function Base.foreach(func::Function, xs::LinkedList) cp = cdr(xs.top) while !null(cp) func(car(cp)) cp = cdr(cp) end end # イテレータ function Base.iterate(xs::LinkedList, state = cdr(xs.top)) if null(state) nothing else (car(state), cdr(state)) end end # 表示 function Base.show(io::IO, xs::LinkedList) print(io, "(") cp = cdr(xs.top) while !null(cp) print(car(cp)) cp = cdr(cp) if !null(cp); print(" "); end end print(")") end # # 簡単なテスト # xs = LinkedList() println(isempty(xs)) for x = 1 : 10 insert!(xs, 0, x) end println(xs) println(isempty(xs)) ys = LinkedList() for x = 0 : 9 insert!(ys, x, x) end foreach(x -> print("$x "), ys) println("") for x = 0 : 9 set!(xs, x, nth(xs, x) * 2) end println(xs) println(length(xs)) delete!(xs, 0) println(xs) println(length(xs)) delete!(xs, 8) println(xs) println(length(xs)) delete!(xs, 3) println(xs) println(length(xs)) while !isempty(xs) delete!(xs, 0) println(xs) println(length(xs)) end println(isempty(xs)) # イテレータ for x = ys print("$x ") end println("")
$ julia list.jl true (10 9 8 7 6 5 4 3 2 1) false 0 1 2 3 4 5 6 7 8 9 (20 18 16 14 12 10 8 6 4 2) 10 (18 16 14 12 10 8 6 4 2) 9 (18 16 14 12 10 8 6 4) 8 (18 16 14 10 8 6 4) 7 (16 14 10 8 6 4) 6 (14 10 8 6 4) 5 (10 8 6 4) 4 (8 6 4) 3 (6 4) 2 (4) 1 () 0 true 0 1 2 3 4 5 6 7 8 9
# # dlist.jl : 双方向リスト (mutable) # # Copyright (C) 2016-2021 Makoto Hiroi # import Base: first, last, push!, pop!, pushfirst!, popfirst!, isempty, length, show # 双方向リスト (セル) mutable struct Cell item prev::Cell next::Cell Cell(a) = (x = new(a); x.next = x; x.prev = x) end # 表示 function show(io::IO, head::Cell) xs = head.next print(io, "(") while xs !== head print(io, xs.item) xs = xs.next if xs !== head; print(io, " "); end end print(io, ")") end # 空か? isempty(xs::Cell) = xs.next === xs # 長さ function length(head::Cell) c = 0 xs = head.next while xs !== head c += 1 xs = xs.next end c end # 参照 function first(head::Cell) if isempty(head) error("front: Empty DList") end head.next.item end function last(head::Cell) if isempty(head) error("back: Empty DList") end head.prev.item end # 先頭に挿入 function pushfirst!(xs::Cell, args...) for x = args ys = Cell(x) zs = xs.next ys.prev = xs ys.next = zs zs.prev = ys xs.next = ys end xs end # 先頭要素を取り出す function popfirst!(xs::Cell) if isempty(xs) error("shift!: Empty DList") end ys = xs.next zs = ys.next xs.next = zs zs.prev = xs ys.item end # 末尾に挿入 function push!(xs::Cell, args...) for x = args ys = Cell(x) zs = xs.prev ys.next = xs ys.prev = zs xs.prev = ys zs.next = ys end xs end # 末尾要素を取り出す function pop!(xs::Cell) if isempty(xs) error("shift!: Empty DList") end ys = xs.prev zs = ys.prev xs.prev = zs zs.next = xs ys.item end # スタック mutable struct Stack top::Cell Stack() = new(Cell(nothing)) end isempty(xs::Stack) = isempty(xs.top) length(xs::Stack) = length(xs.top) show(io::IO, xs::Stack) = show(io, xs.top) first(xs::Stack) = last(xs.top) push!(xs::Stack, args...) = push!(xs.top, args...) pop!(xs::Stack) = pop!(xs.top) # キュー mutable struct Queue head::Cell Queue() = new(Cell(nothing)) end isempty(xs::Queue) = isempty(xs.head) length(xs::Queue) = length(xs.head) show(io::IO, xs::Queue) = show(io, xs.head) first(xs::Queue) = first(xs.head) push!(xs::Queue, args...) = push!(xs.head, args...) pop!(xs::Queue) = popfirst!(xs.head) # ディーキュー mutable struct Deque head::Cell Deque() = new(Cell(nothing)) end isempty(xs::Deque) = isempty(xs.head) length(xs::Deque) = length(xs.head) show(io::IO, xs::Deque) = show(io, xs.head) first(xs::Deque) = first(xs.head) last(xs::Deque) = last(xs.head) push!(xs::Deque, args...) = push!(xs.head, args...) pop!(xs::Deque) = pop!(xs.head) popfirst!(xs::Deque) = popfirst!(xs.head) pushfirst!(xs::Deque, args...) = pushfirst!(xs.head, args...)
julia> include("dlist.jl") pushfirst! (generic function with 10 methods) julia> a = Stack() () julia> push!(a, 1, 2, 3, 4, 5) (1 2 3 4 5) julia> first(a) 5 julia> length(a) 5 julia> while !isempty(a); println(pop!(a)); end 5 4 3 2 1 julia> b = Queue() () julia> push!(b, 1, 2, 3, 4, 5) (1 2 3 4 5) julia> first(b) 1 julia> length(b) 5 julia> while !isempty(b); println(pop!(b)); end 1 2 3 4 5 julia> c = Deque() () julia> push!(c, 1, 2, 3, 4, 5) (1 2 3 4 5) julia> first(c) 1 julia> last(c) 5 julia> pushfirst!(c, 1, 2, 3, 4, 5) (5 4 3 2 1 1 2 3 4 5) julia> pop!(c) 5 julia> c (5 4 3 2 1 1 2 3 4) julia> popfirst!(c) 5 julia> c (4 3 2 1 1 2 3 4)