В чем разница между `UnitRange` и` Array`? - PullRequest
Новая
       4

В чем разница между `UnitRange` и` Array`?

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

У меня есть две версии кода, которые, кажется, делают одно и то же: 

sum = 0
for x in 1:100
    sum += x
end

sum = 0
for x in collect(1:100)
    sum += x
end

Есть ли практическая разница между этими двумя подходами?

Ответы [ 2 ]

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

UnitRange будет использовать постоянный пробел, в то время как Array будет расти пропорционально количеству элементов, для которых вы выполняете итерацию.

Вы можете увидеть разницу, используя BenchmarkTools пакет. 

julia> @btime sum(1:1000000)
  0.044 ns (0 allocations: 0 bytes)
500000500000

julia> @btime sum(collect(1:1000000))
  1.123 ms (2 allocations: 7.63 MiB)
500000500000

Между этими двумя подходами существует значительная разница в производительности в пространстве и времени.UnitRange избегает работы по выделению большого куска памяти, когда вам все это не нужно сразу.Когда это возможно, используйте UnitRange вместо Array.

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

В Julia 1:100 возвращает конкретную структуру с именем UnitRange, которая выглядит следующим образом: 

julia> dump(1:100)
UnitRange{Int64}
  start: Int64 1
  stop: Int64 100

Это очень компактная структура для представления диапазонов с шагом 1 и произвольным (конечным) размером.UnitRange является подтипом AbstractRange, типом для представления диапазонов с произвольным шагом, подтипом AbstractVector.

Экземпляры UnitRange динамически вычисляют свои элементы всякий раз, когда вы используете getindex (илисинтаксический сахар vector[index]).Например, с @less (1:100)[3] вы можете увидеть этот метод: 

function getindex(v::UnitRange{T}, i::Integer) where {T<:OverflowSafe}
    @_inline_meta
    val = v.start + (i - 1)
    @boundscheck _in_unit_range(v, val, i) || throw_boundserror(v, i)
    val % T
end

Это возвращает i -й элемент вектора путем добавления i - 1 к первому элементу (start) издиапазон.Некоторые функции оптимизировали методы с UnitRange или, в более общем случае, с AbstractRange.Например, с @less sum(1:100) вы можете увидеть следующее 

function sum(r::AbstractRange{<:Real})
    l = length(r)
    # note that a little care is required to avoid overflow in l*(l-1)/2
    return l * first(r) + (iseven(l) ? (step(r) * (l-1)) * (l>>1)
                                     : (step(r) * l) * ((l-1)>>1))
end

Этот метод использует формулу для суммы арифметической прогрессии , что чрезвычайно эффективно, поскольку оценивается за времяне зависит от размера вектора.

С другой стороны, collect(1:100) возвращает простой Vector с сотней элементов 1, 2, 3, ..., 100. Основное отличие с UnitRange (или другие типы AbstractRange) в том, что getindex(vector::Vector, i) (или vector[i], с vector::Vector) не выполняет никаких вычислений, а просто обращается к i -ому элементу вектора.Недостатком Vector по сравнению с UnitRange является то, что, вообще говоря, нет эффективных методов при работе с ними, поскольку элементы этого контейнера полностью произвольны, в то время как UnitRange представляет набор чисел с особыми свойствами (отсортировано, постоянный шаг и т.д ...).

Если вы сравните производительность методов, для которых UnitRange имеет суперэффективные реализации, этот тип выиграет руки (обратите внимание на использование интерполяции переменных с $(...) при использовании макросов из BenchmarkTools): 

julia> using BenchmarkTools

julia> @btime sum($(1:1000_000))
  0.012 ns (0 allocations: 0 bytes)
500000500000

julia> @btime sum($(collect(1:1000_000)))
  229.979 μs (0 allocations: 0 bytes)
500000500000

Помните, что UnitRange имеет стоимость динамического вычисления элементов каждый раз, когда вы получаете к ним доступ с помощью getindex.Рассмотрим, например, эту функцию: 

function test(vec)
    sum = zero(eltype(vec))
    for idx in eachindex(vec)
        sum += vec[idx]
    end
    return sum
end

Давайте сопоставим ее с UnitRange и простым Vector: 

julia> @btime test($(1:1000_000))
  812.673 μs (0 allocations: 0 bytes)
500000500000

julia> @btime test($(collect(1:1000_000)))
  522.828 μs (0 allocations: 0 bytes)
500000500000

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

Конечно, в этих игрушечных примерах было бы более разумно перебирать все элементы vec, а нечем его показатели, но в реальных ситуациях такая ситуация может быть более разумной.Этот последний пример, однако, показывает, что UnitRange не обязательно более эффективен, чем простой массив, особенно если вам нужно динамически вычислить все его элементы.UnitRange более эффективны, когда вы можете воспользоваться специализированными методами (например, sum), для которых операция может выполняться в постоянное время.

В качестве примечания к файлу обратите внимание, что если у вас изначально естьUnitRange не обязательно хорошая идея преобразовать его в обычный Vector, чтобы получить хорошую производительность, особенно если вы собираетесь использовать его только один или несколько раз, так как преобразование в Vector включает в себя динамическийВычисление всех элементов диапазона и выделение необходимой памяти: 

julia> @btime collect($(1:1000_000));
  422.435 μs (2 allocations: 7.63 MiB)

julia> @btime test(collect($(1:1000_000)))
  882.866 μs (2 allocations: 7.63 MiB)
500000500000
...