Документация Engee

Массивы с пользовательскими индексами

Традиционно массивы в Julia индексируются начиная с 1, в то время как в некоторых других языках нумерация начинается с 0 или даже (например, в Фортране) можно указать произвольный начальный индекс. Хотя стандартная нумерация (например, начиная с 1 в Julia) имеет множество достоинств, некоторые алгоритмы существенно упрощаются, если возможна индексация за пределами диапазона 1:size(A,d) (или 0:size(A,d)-1). Для упрощения таких вычислений в Julia поддерживаются массивы с произвольными индексами.

На этой странице дается ответ на вопрос «Что нужно сделать для поддержки таких массивов в собственном коде?» Для начала давайте рассмотрим простейший случай: если вы знаете, что в вашем коде никогда не придется иметь дело с массивами с нестандартной индексацией, то ответ, скорее всего — ничего. Старый код с традиционными массивами должен работать безо всяких изменений, если в нем используются экспортированные интерфейсы Julia. Если вам кажется более удобным просто запретить использование нетрадиционных массивов с индексацией не от единицы, вы можете добавить:

Base.require_one_based_indexing(arrays...)

где arrays... — это список объектов-массивов, которые нужно проверять на нарушение индексации от единицы.

Универсализация существующего кода

Общий порядок действий следующий:

  • заменяйте size на axes;

  • заменяйте 1:length(A) на eachindex(A) или в некоторых случаях на LinearIndices(A);

  • заменяйте явные выделения памяти, например Array{Int}(undef, size(B)), на similar(Array{Int}, axes(B)).

Подробнее об этом рассказывается ниже.

Возможные опасности

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

function mycopy!(dest::AbstractVector, src::AbstractVector)
    length(dest) == length(src) || throw(DimensionMismatch("vectors must match"))
    # Теперь можно спокойно использовать @inbounds, верно? (Уже нет!)
    for i = 1:length(src)
        @inbounds dest[i] = src[i]
    end
    dest
end

В этом коде неявно предполагается, что векторы индексируются от единицы; если dest будет начинаться не с того же индекса, что и src, есть вероятность аварийного завершения. (Если такое происходит, то, чтобы выяснить причину, попробуйте запустить Julia с параметром --check-bounds=yes.)

Использование axes для проверки границ и перебора в цикле

Метод axes(A) (похожий на size(A)) возвращает кортеж объектов AbstractUnitRange{<:Integer}, определяющих допустимый диапазон индексов по каждому измерению массива A. Если A индексируется нестандартным образом, диапазоны могут начинаться не с единицы. Чтобы получить диапазон для определенного измерения d, используйте вызов axes(A, d).

В модуле Base реализован пользовательский тип диапазона OneTo: OneTo(n) означает то же самое, что и 1:n, но гарантирует (посредством системы типов), что нижний индекс равен 1. Для любого нового типа AbstractArray объект этого типа возвращается по умолчанию функцией axes. Это означает, что данный тип массива использует традиционное индексирование — начиная с единицы.

Обратите внимание, что для проверки границ существуют специальные функции checkbounds и checkindex, которые иногда могут упростить эту задачу.

Линейное индексирование (LinearIndices)

Некоторые алгоритмы удобнее всего (или эффективнее) реализуются посредством линейных индексов A[i], даже если A — многомерный массив. Какими бы ни были собственные индексы массива, линейные индексы всегда имеют диапазон 1:length(A). Однако в случае с одномерными массивами (то есть AbstractVector) возникает неоднозначность: означает ли v[i] линейное индексирование или декартово индексирование с собственными индексами массива?

По этой причине оптимальным решением может быть перебор массива с помощью eachindex(A) или, если индексы должны быть последовательными целыми числами, получение диапазона индексов путем вызова LinearIndices(A). В результате будет возвращено axes(A, 1), если A — это AbstractVector, либо эквивалент 1:length(A) в противном случае.

Согласно этому определению одномерные массивы всегда используют декартово индексирование с собственными индексами массива. В подтверждение этого факта стоит отметить, что функции преобразования индексов выдают ошибку, если форма массива соответствует одномерному массиву с нестандартным индексированием (то есть Tuple{UnitRange}, а не кортеж OneTo). Для массивов со стандартным индексированием эти функции будут работать как обычно.

Вот один из способов переписать mycopy!, используя axes и LinearIndices.

function mycopy!(dest::AbstractVector, src::AbstractVector)
    axes(dest) == axes(src) || throw(DimensionMismatch("vectors must match"))
    for i in LinearIndices(src)
        @inbounds dest[i] = src[i]
    end
    dest
end

Выделение места для хранения с использованием обобщений similar

Место для хранения часто выделяется с помощью Array{Int}(undef, dims) или similar(A, args...). Если результат должен соответствовать индексам какого-либо другого массива, этого не всегда может быть достаточно. Универсальной заменой таким шаблонам является использование similar(storagetype, shape). storagetype означает нужный тип базового, стандартного поведения, например Array{Int}, BitArray или даже dims->zeros(Float32, dims) (в этом случае в памяти размещается массив из одних нулей). shape — это кортеж значений Integer или AbstractUnitRange, определяющий индексы, которые должны использоваться в результате. Обратите внимание: для получения массива из одних нулей, соответствующего индексам A, удобно просто использовать zeros(A).

Разберем пару наглядных примеров. Во-первых, если у A стандартные индексы, то similar(Array{Int}, axes(A)) приведет к вызову Array{Int}(undef, size(A)) и вернет массив. Если A — это тип AbstractArray с нестандартным индексированием, то вызов similar(Array{Int}, axes(A)) должен вернуть что-то похожее по поведению на Array{Int}, но имеющее форму (включая индексы), соответствующую A. (Наиболее очевидной реализацией является размещение в памяти объекта Array{Int}(undef, size(A)) с последующей его инкапсуляцией в тип со сдвигом индексов.)

Также имейте в виду, что вызов similar(Array{Int}, (axes(A, 2),)) разместит в памяти объект AbstractVector{Int} (то есть одномерный массив), соответствующий индексам столбцов A.

Написание пользовательских типов массивов с индексированием не от единицы

Большинство методов, которые потребуется определить, являются стандартными для любого типа AbstractArray; см. раздел Абстрактные массивы. В этом разделе описываются действия, необходимые для определения нестандартного индексирования.

Пользовательские типы AbstractUnitRange

Если вы создаете тип массива с индексированием не от единицы, вам потребуется специализировать функцию axes так, чтобы она возвращала объект UnitRange или (что, возможно, еще лучше) пользовательский объект AbstractUnitRange. Преимуществом пользовательского типа является то, что он сообщает о типе выделения памяти таким функциям, как similar. При написании типа массива с индексированием от нуля, скорее всего, будет лучше начать с создания нового типа AbstractUnitRange — ZeroRange, где ZeroRange(n) эквивалентно 0:n-1.

В общем случае не следует экспортировать ZeroRange из пакета: могут быть другие пакеты, в которых реализован собственный тип ZeroRange, а наличие нескольких отдельных типов ZeroRange, как это ни странно, является преимуществом. ModuleA.ZeroRange указывает на то, что функция similar должна создать ModuleA.ZeroArray, а ModuleB.ZeroRange соответствует типу ModuleB.ZeroArray. Такой подход обеспечивает мирное сосуществование множества разных пользовательских типов массивов.

Обратите внимание: чтобы не писать собственный тип ZeroRange, иногда можно использовать пакет Julia CustomUnitRanges.jl.

Специализация axes

После создания собственного типа AbstractUnitRange необходимо специализировать функцию axes.

Base.axes(A::ZeroArray) = map(n->ZeroRange(n), A.size)

Здесь предполагается, что у ZeroArray есть поле с именем size (реализовать это можно и иными способами).

В некоторых случаях резервное определение axes(A, d).

axes(A::AbstractArray{T,N}, d) where {T,N} = d <= N ? axes(A)[d] : OneTo(1)

может не отвечать вашим потребностям: вам может потребоваться специализировать его так, чтобы оно возвращало что-то, отличное от OneTo(1) при d > ndims(A). Аналогичным образом, в Base есть специальная функция axes1, которая эквивалентна axes(A, 1), но игнорирует проверку ndims(A) > 0 (во время выполнения). (Ее назначение заключается исключительно в повышении производительности.) Определяется она следующим образом.

axes1(A::AbstractArray{T,0}) where {T} = OneTo(1)
axes1(A::AbstractArray) = axes(A)[1]

Если первый случай (одномерный массив) представляет проблему для вашего пользовательского типа массива, реализуйте соответствующую специализацию.

Специализация similar

Для собственного типа ZeroRange необходимо также добавить следующие две специализации similar.

function Base.similar(A::AbstractArray, T::Type, shape::Tuple{ZeroRange,Vararg{ZeroRange}})
    # тело
end

function Base.similar(f::Union{Function,DataType}, shape::Tuple{ZeroRange,Vararg{ZeroRange}})
    # тело
end

Обе они должны реализовывать ваш пользовательский тип массива.

Специализация reshape

При необходимости определите следующий метод.

Base.reshape(A::AbstractArray, shape::Tuple{ZeroRange,Vararg{ZeroRange}}) = ...

Это позволит изменить форму (reshape) массива так, чтобы у него были пользовательские индексы.

Объекты, имитирующие поведение AbstractArray, но не являющиеся его подтипами

Значение метода has_offset_axes зависит от того, определен ли метод axes для объектов, для которых он вызывается. Если по какой-либо причине метод axes не определен для объекта, можно определить следующий метод.

Base.has_offset_axes(obj::MyNon1IndexedArraylikeObject) = true

Это позволит выявить проблему в коде, в котором предполагается индексирование от единицы, и выдать полезное сообщение об ошибке вместо возврата неверных результатов или аварийного завершения Julia.

Перехват ошибок

Если новый тип массива вызывает ошибки где-то в другом коде, для отладки можно попробовать закомментировать @boundscheck в вашей реализации getindex и setindex!. Это позволит убедиться в том, что при обращении к каждому элементу происходит проверка границ. Либо же можно перезапустить Julia с параметром --check-bounds=yes.

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