部分配列

Julia の SubArray 型は親の AbstractArray に対する "ビュー" として振る舞うコンテナです。このページには SubArray の設計指針と実装に関するドキュメントを示します。

主な設計目標の一つは、IndexLinear 型の配列と IndexCartesian 型の配列の両方に対して高い性能を保証することです。さらに IndexLinear 配列のビューは可能なかぎり IndexLinear であるべきです。

添え字の置換

三次元配列の二次元スライスを作ることを考えます:

julia> A = rand(2,3,4);

julia> S1 = view(A, :, 1, 2:3)
2×2 view(::Array{Float64,3}, :, 1, 2:3) with eltype Float64:
 0.200586  0.066423
 0.298614  0.956753

julia> S2 = view(A, 1, :, 2:3)
3×2 view(::Array{Float64,3}, 1, :, 2:3) with eltype Float64:
 0.200586  0.066423
 0.246837  0.646691
 0.648882  0.276021

view が "シングルトン次元" (Int によって指定される、サイズが 1 の次元) を落とすので、S1 と S2 は両方とも二次元の SubArray となります。使うときは S1[i,j], S2[i,j] のようにします。親の配列 A から値を取り出すときは、S1[i,j] を A[i,1,(2:3)[j]] と置き換え、S[i,j] を A[1,i,(2:3)[j]] と置き換えるのが自然なアプローチです。

SubArray の設計が持つ大きな特徴は、添え字の入れ替えにランタイムのオーバーヘッドが存在しないことです。

SubArray の設計

型パラメータとフィールド

採用された戦略を何よりもまず型の定義によって表されます:

struct SubArray{T,N,P,I,L} <: AbstractArray{T,N}
    parent::P
    indices::I
    offset1::Int       # L==true のときにだけ、線形添え字アクセスとポインタで使われる。
    stride1::Int       # 線形添え字にだけ使われる。
    ...
end

SubArray は五つの型パラメータを持ちます。最初の二つは要素型と次元であり、通常の配列と同じです。次の三つ目のパラメータは親の AbstractArray の型です。最も頻繁に使われるのが四つ目のパラメータであり、これは各次元の添え字の型からなる Tuple です。最後のパラメータ L はディスパッチで使うためだけに存在し、添え字の型が効率的な線形添え字アクセスをサポートするかどうかを表します (後述)。

上記の例で A は Array{Float64, 3} 型の値であり、S1 の型を確認すれば SubArray{Float64, 2, Array{Float64,3}, Tuple{Base.Slice{Base.OneTo{Int64}},Int64,UnitRange{Int64}}, false} となります。S1 を作るときに使われた添え字の型が格納されたタプルのパラメータに特に注目してください。例えば次のようになります:

julia> S1.indices
(Base.Slice(Base.OneTo(2)), 1, 2:3)

これらの値を格納することで添え字の置き換えが可能になり、型をパラメータとしてエンコードすることで効率的なアルゴリズムへのディスパッチが可能になります。

添え字の変換

添え字の変換を行うときは、SubArray の部分具象型それぞれに対して異なる計算が必要です。例えば S1 に対する添え字 (i,j) は親配列の一番目と三番目の次元の添え字として使う必要があり、S2 に対する添え字は二番目の三番目の添え字として使う必要があります。添え字アクセスの最も簡単なアプローチは、型の解析を実行時に行うというものです:

parentindices = Vector{Any}()
for thisindex in S.indices
    ...
    if isa(thisindex, Int)
        # この次元では入力の添え字を使わない。
        push!(parentindices, thisindex)
    elseif isa(thisindex, AbstractVector)
        # 入力の添え字を使う。
        push!(parentindices, thisindex[inputindex[j]])
        j += 1
    elseif isa(thisindex, AbstractMatrix)
        # 入力の添え字を使う。
        push!(parentindices, thisindex[inputindex[j], inputindex[j+1]])
        j += 2
    elseif ...
end
S.parent[parentindices...]

残念ながら、このアプローチは性能が絶望的です。あらゆる要素へのアクセスがメモリをアロケートし、ほとんど型が付かないコードを大量に実行しなけばなりません。

これより優れたアプローチは、保存された添え字の型をそれぞれ処理する特定のメソッドにディスパッチするというものです。reindex 関数がまさにこれを行います: この関数は保存された最初の添え字の型でディスパッチを行い、入力の添え字を適切な個数だけ使い、残りの添え字に対して再帰的に同じ処理を行います。S1 の場合であれば、次のように展開されます1:

Base.reindex(S1.indices, (i, j)) == (i, S1.indices[2], S1.indices[3][j])

ここで i と j は添え字を表す任意の型の値です (ただし後述するように、CartesianIndex および CartesianIndex の配列であってはいけません)。

以上が SubArray のコアです: 添え字アクセスメソッドが reindex を使って添え字の変換を行います。ただし場合よっては、間接的なアクセスを使わずにさらに高速化できる場合があります。

線形添え字アクセス

配列全体が適当なオフセットから始まって任意の連続する二つの要素を分ける単一の歩長を持つなら、線形添え字アクセスを効率的に実装できます。この条件が成り立つときは歩長を事前に計算することで線形添え字アクセスを加算と乗算を使った添え字アクセスに変換できるためです。特に reindex の呼び出しと (より重要なこととして) 時間のかかる格子添え字の計算を完全に省略できます。

SubArray 型に対しては、効率的な線形添え字アクセスが利用可能かどうかは添え字の型だけで決定し、親の配列のサイズのような他の値には影響を受けません。添え字の集合が効率的な線形添え字アクセスをサポートするかどうかは内部の Base.viewindexing 関数で取得できます:

julia> Base.viewindexing(S1.indices)
IndexCartesian()

julia> Base.viewindexing(S2.indices)
IndexLinear()

この真偽値は SubArray の構築時に計算され、効率的な線形添え字アクセスのサポートを表す型パラメータ L に保存されます。これは間に関数を挟むことない SubArray{T,N,A,I,true} への直接的なディスパッチを定義できることを意味します (ただし厳密に言えば必要ではありません)。

この計算は実行時の値に依存しないので、歩長がたまたま同じになるケースを見落とす可能性があります:

julia> A = reshape(1:4*2, 4, 2)
4×2 reshape(::UnitRange{Int64}, 4, 2) with eltype Int64:
 1  5
 2  6
 3  7
 4  8

julia> diff(A[2:2:4,:][:])
3-element Array{Int64,1}:
 2
 2
 2

view(A, 2:2:4, :) で構築されるビューは一様な歩長を持つので、線形添え字アクセスを効率的に行うことができます。しかし、それが可能かどうかは配列のサイズに依存します。例えば、もし一番目の次元のサイズが奇数なら

julia> A = reshape(1:5*2, 5, 2)
5×2 reshape(::UnitRange{Int64}, 5, 2) with eltype Int64:
 1   6
 2   7
 3   8
 4   9
 5  10

julia> diff(A[2:2:4,:][:])
3-element Array{Int64,1}:
 2
 3
 2

となって A[2:2:4,:] は一様な歩長を持たず、効率的な線形添え字アクセスは保証できません。線形添え字アクセスを行うかどうかの判断は SubArray のパラメータにエンコードされた型だけを使って行う必要があることから、S = view(A, 2:2:4, :) には効率的な線形添え字アクセスを実装できません。

さらに詳しい情報

  1. 訳注: 現在のバージョンでは reindex の第一引数に配列を渡さないので、コードを修正した (参照: #30789)。[return]

広告
このページの文章はテキストゆれないくんを使って校正されました。