Юлия - выступление декартовых индусов - PullRequest
Новая
       23

Юлия - выступление декартовых индусов

2 голосов
/ 19 сентября 2019

Я копался в исходном коде Base.IteratorsMD и был убежден, что реализация Base.nextind для CartesianIndex (в julia/base/multidimensional.jl, см. Здесь https://github.com/JuliaLang/julia/blob/55e36cc308b66d3472990a06b2797f9f9154ea0a/base/multidimensional.jl#L142-L150) должна быть крайне неэффективной:

function Base.nextind(a::AbstractArray{<:Any,N}, i::CartesianIndex{N}) where {N}
    iter = CartesianIndices(axes(a))
    return CartesianIndex(inc(i.I, first(iter).I, last(iter).I))
end

Я предполагал, что создание нового экземпляра CartesianIndices(...) в каждом вызове должно быть очень дорогим, поскольку на моей машине вызов CartesianIndices(...) через REPL, кажется, создает все индексы.Поэтому я написал следующий эталонный скрипт для альтернативной реализации mynextind: 

using Base.IteratorsMD

function mynextind(a::AbstractArray{<:Any,N}, i::CartesianIndex{N}) where {N}
    dims = (x.stop for x in axes(a))
    return CartesianIndex(Base.IteratorsMD.inc(i.I, CartesianIndex(ones(Int64, length(dims))...).I, CartesianIndex(dims...).I))
end

function f(func, M)
    c = CartesianIndex(1,1)
    while true
        (c = func(M, c)) == CartesianIndex(size(M)...) && break
    end
end

A = rand(100,100)

@btime f(Base.nextind, A)
@btime f(mynextind, A)

Base.nextind был на несколько порядков быстрее (7 мкс против 12 мс), чем mynextind.Кроме того, Base.nextind не выделяет памяти.Теперь я пытаюсь понять, почему это так.CartesianIndices создает все индексы или нет?

1 Ответ

4 голосов
/ 19 сентября 2019

Я предполагал, что создание нового экземпляра CartesianIndices (...) в каждом вызове должно быть очень дорогим, поскольку на моей машине вызов CartesianIndices (...) через REPL, кажется, создает все индексы.

Это недопустимо.

Когда вы печатаете CartesianIndices(...) в REPL, все элементы будут напечатаны.Но это не значит, что он создаст все индексы.

Как вы можете видеть в исходном коде структуры CartesianIndices здесь: https://github.com/JuliaLang/julia/blob/64d8ca49122609d1c10c72a96d1711b95346980a/base/multidimensional.jl#L248

Когда вы создаетеНапример, CartesianIndices(axes(A)), сохраняются только оси.Причина, по которой вы увидели, что все индексы напечатаны, заключается в том, что CartesianIndices - это AbstractArray.И он также реализует методы getindex.Поэтому, когда вы набираете CartesianIndices(axes(A)), все индексы вычисляются по требованию.

И вы можете увидеть больше обсуждений о CartesianIndices здесь: https://discourse.julialang.org/t/psa-replacement-of-ind2sub-sub2ind-in-julia-0-7/14666

...