SubArrays

نوع SubArray في جوليا هو حاوية تشفر "عرض" من والد AbstractArray. توثق هذه الصفحة بعض مبادئ التصميم وتنفيذ SubArrays.

أحد الأهداف الرئيسية في التصميم هو ضمان أداء عالي لعرض كل من IndexLinear و IndexCartesian المصفوفات. علاوة على ذلك، يجب أن تكون العروض لمصفوفات IndexLinear هي نفسها IndexLinear بقدر ما هو ممكن.

Index replacement

اعتبر إنشاء شرائح ثنائية الأبعاد من مصفوفة ثلاثية الأبعاد:

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.839622  0.711389
 0.967143  0.103929

julia> S2 = view(A, 1, :, 2:3)
3×2 view(::Array{Float64, 3}, 1, :, 2:3) with eltype Float64:
 0.839622  0.711389
 0.789764  0.806704
 0.566704  0.962715

view يقوم بإسقاط الأبعاد "الفردية" (التي يتم تحديدها بواسطة Int)، لذا فإن كل من S1 و S2 هما SubArrays ثنائية الأبعاد. وبالتالي، فإن الطريقة الطبيعية لفهرسة هذه هي باستخدام S1[i,j]. لاستخراج القيمة من المصفوفة الأصلية A، فإن النهج الطبيعي هو استبدال S1[i,j] بـ A[i,1,(2:3)[j]] و S2[i,j] بـ A[1,i,(2:3)[j]].

الميزة الرئيسية في تصميم SubArrays هي أنه يمكن تنفيذ استبدال الفهارس هذا دون أي تكلفة زمنية.

SubArray design

Type parameters and fields

تُعبر الاستراتيجية المعتمدة أولاً وقبل كل شيء عن نفسها في تعريف النوع:

struct SubArray{T,N,P,I,L} <: AbstractArray{T,N}
    parent::P
    indices::I
    offset1::Int       # for linear indexing and pointer, only valid when L==true
    stride1::Int       # used only for linear indexing
    ...
end

SubArray لديه 5 معلمات نوع. الأولان هما نوع العنصر القياسي والأبعاد. الثالث هو نوع 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)

تخزين هذه القيم يسمح باستبدال الفهارس، ووجود الأنواع مشفرة كمعلمات يسمح بالانتقال إلى خوارزميات فعالة.

Index translation

يتطلب تنفيذ ترجمة الفهرس القيام بأشياء مختلفة لأنواع SubArray المختلفة. على سبيل المثال، بالنسبة لـ S1، يجب تطبيق مؤشرات i,j على البعدين الأول والثالث من المصفوفة الأصلية، بينما بالنسبة لـ S2، يجب تطبيقها على البعدين الثاني والثالث. أبسط نهج للفهرسة سيكون إجراء تحليل النوع في وقت التشغيل:

parentindices = Vector{Any}()
for thisindex in S.indices
    ...
    if isa(thisindex, Int)
        # Don't consume one of the input indices
        push!(parentindices, thisindex)
    elseif isa(thisindex, AbstractVector)
        # Consume an input index
        push!(parentindices, thisindex[inputindex[j]])
        j += 1
    elseif isa(thisindex, AbstractMatrix)
        # Consume two input indices
        push!(parentindices, thisindex[inputindex[j], inputindex[j+1]])
        j += 2
    elseif ...
end
S.parent[parentindices...]

لسوء الحظ، سيكون هذا كارثيًا من حيث الأداء: كل وصول إلى عنصر سيخصص ذاكرة، ويتضمن تشغيل الكثير من الشيفرات ذات الأنواع السيئة.

النهج الأفضل هو إرسال الطلبات إلى طرق محددة للتعامل مع كل نوع من الفهارس المخزنة. هذا ما تفعله reindex: إنها ترسل الطلبات بناءً على نوع الفهرس المخزن الأول وتستهلك العدد المناسب من فهارس الإدخال، ثم تتكرر على الفهارس المتبقية. في حالة S1، يتوسع هذا إلى

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

لكل زوج من الفهارس (i,j) (باستثناء CartesianIndex ومصفوفات منها، انظر أدناه).

هذا هو جوهر SubArray؛ تعتمد طرق الفهرسة على reindex للقيام بترجمة الفهرس. أحيانًا، يمكننا تجنب التوجيه وجعلها أسرع حتى.

Linear indexing

يمكن تنفيذ الفهرسة الخطية بكفاءة عندما يحتوي المصفوفة بالكامل على خطوة واحدة تفصل بين العناصر المتعاقبة، بدءًا من بعض الإزاحة. هذا يعني أنه يمكننا حساب هذه القيم مسبقًا وتمثيل الفهرسة الخطية ببساطة كإضافة وضرب، مما يتجنب التوجيه لـ 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 Vector{Int64}:
 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 Vector{Int64}:
 2
 3
 2

ثم A[2:2:4,:] لا يحتوي على خطوة موحدة، لذا لا يمكننا ضمان فهرسة خطية فعالة. نظرًا لأننا يجب أن نستند في هذا القرار فقط على الأنواع المشفرة في معلمات SubArray، فإن S = view(A, 2:2:4, :) لا يمكنه تنفيذ فهرسة خطية فعالة.

A few details

لاحظ أن دالة Base.reindex غير متعلقة بأنواع مؤشرات الإدخال؛ فهي تحدد ببساطة كيف وأين يجب إعادة فهرسة المؤشرات المخزنة. إنها لا تدعم فقط مؤشرات الأعداد الصحيحة، بل تدعم أيضًا الفهرسة غير القياسية. هذا يعني أن وجهات النظر لا تحتاج إلى مستويين من التوجيه؛ يمكنها ببساطة إعادة حساب المؤشرات في مصفوفة الأصل!
من المؤمل أنه بحلول الآن أصبح من الواضح إلى حد ما أن دعم الشرائح يعني أن الأبعاد، التي تحددها المعلمة N، ليست بالضرورة متساوية مع أبعاد المصفوفة الأصلية أو طول مجموعة indices. كما أن الفهارس المقدمة من قبل المستخدم ليست بالضرورة متوافقة مع الإدخالات في مجموعة indices (على سبيل المثال، قد يتوافق الفهرس الثاني المقدم من قبل المستخدم مع البعد الثالث من المصفوفة الأصلية، والعنصر الثالث في مجموعة indices).
ما قد يكون أقل وضوحًا هو أن أبعاد مصفوفة الوالد المخزنة يجب أن تكون متساوية مع عدد المؤشرات الفعالة في مجموعة indices. بعض الأمثلة:
```
A = reshape(1:35, 5, 7) # A 2d parent Array
S = view(A, 2:7)         # A 1d view created by linear indexing
S = view(A, :, :, 1:1)   # Appending extra indices is supported
```
ببساطة، قد تعتقد أنه يمكنك فقط تعيين S.parent = A و S.indices = (:,:,1:1)، لكن دعم ذلك يعقد بشكل كبير عملية إعادة الفهرسة، خاصةً لعرض العروض. ليس فقط أنك بحاجة إلى إرسال الأنواع الخاصة بالفهارس المخزنة، ولكن عليك أيضًا فحص ما إذا كان الفهرس المعطى هو الأخير و"دمج" أي فهارس مخزنة متبقية معًا. هذه ليست مهمة سهلة، والأسوأ من ذلك: إنها بطيئة لأنها تعتمد ضمنيًا على الفهرسة الخطية.
لحسن الحظ، هذه هي بالضبط الحسابات التي يقوم بها ReshapedArray، ويفعل ذلك بشكل خطي إذا كان ذلك ممكنًا. وبالتالي، يضمن view أن يكون مصفوفة الأصل بالأبعاد المناسبة للفهارس المعطاة من خلال إعادة تشكيلها إذا لزم الأمر. يضمن مُنشئ SubArray الداخلي أن يتم الوفاء بهذا الثابت.
CartesianIndex والمصفوفات منها تلقي عائقًا كبيرًا في مخطط reindex. تذكر أن reindex ببساطة يوزع بناءً على نوع الفهارس المخزنة لتحديد عدد الفهارس الممررة التي يجب استخدامها وأين يجب أن تذهب. ولكن مع CartesianIndex، لم يعد هناك تطابق واحد لواحد بين عدد المعاملات الممررة وعدد الأبعاد التي تشير إليها. إذا عدنا إلى المثال أعلاه لـ Base.reindex(S1, S1.indices, (i, j))، يمكنك أن ترى أن التوسع غير صحيح لـ i, j = CartesianIndex(), CartesianIndex(2,1). يجب أن يتخطى CartesianIndex() تمامًا ويعيد:
```
(CartesianIndex(2,1)[1], S1.indices[2], S1.indices[3][CartesianIndex(2,1)[2]])
```
بدلاً من ذلك، نحصل على:
```
(CartesianIndex(), S1.indices[2], S1.indices[3][CartesianIndex(2,1)])
```
يتطلب القيام بذلك بشكل صحيح دمج الإرسال على كل من الفهارس المخزنة والممررة عبر جميع تركيبات الأبعاد بطريقة غير قابلة للحل. وبالتالي، يجب ألا يتم استدعاء reindex أبدًا باستخدام فهارس CartesianIndex. لحسن الحظ، يمكن التعامل مع الحالة العددية بسهولة من خلال تسطيح معلمات CartesianIndex إلى أعداد صحيحة عادية. ومع ذلك، لا يمكن تقسيم مصفوفات CartesianIndex بسهولة إلى قطع متعامدة. قبل محاولة استخدام reindex، يجب على view التأكد من عدم وجود مصفوفات من CartesianIndex في قائمة المعلمات. إذا كانت هناك، يمكنها ببساطة "تجنب" ذلك عن طريق تجنب حساب reindex تمامًا، وبناء SubArray متداخلة مع مستويين من التوجيه بدلاً من ذلك.