Best practices for passing vector index in function

General Usage
1

I’m making a bunch of partition and selection functions. In my use case I will always have vectors indexed by one, but given that offsetarray exists I wonder what would be a good signature for a function that takes an array and an index of said array.

I think the partition function in Base.jl takes a lo, hi as well and partitions arr[lo:hi] but I wonder if there’s an abstract type that represents “index i from the beginning of this vector’s linearindex”, or if something like “for i = eachindex(arr)[1:input_index]” would work?

Thanks!!

2

You could probably do arr[begin-1+i] which would convert i from one-based to array-offset-based. The function behind this is firstindex

1 Like
3

That sounds like what I needed! I’ll try it out, thank you!

4

So… after looking into begin I got to look into Base.Iterators and tried to implement the same function with and without iterators. Iterators make handling of indices easier as I need to traverse in both directions. I managed to get something that runs 2x slower than the initial version with while loops and indices (I’m not pasting that version here as it turns out it also has some errors in edge cases that I haven’t debugged yet). I was wondering if someone would have suggestions to improve the performance. For example, I wonder if these iterators are frozen or are recomputed every time I modify the array, and if there’s a way to freeze them (I don’t think so as they’re lazy):

function hoarepartitioniter!(arr::AbstractVector, pivot_index::Integer)
    @inbounds arr[begin - 1 + pivot_index], arr[begin] = arr[begin], arr[begin - 1 + pivot_index]
    pivot_value = arr[begin]
    it_lr = Iterators.filter(p -> p[2] > pivot_value, pairs(@view(arr[begin+1:end])))
    it_rl = Iterators.filter(p -> p[2] <= pivot_value, Iterators.reverse(pairs(@view(arr[begin+1:end]))))
    final_pivot_index = firstindex(arr)
    @inbounds for ((i1, _), (i2, _)) in Iterators.zip(it_lr, it_rl)
        final_pivot_index = firstindex(arr) + i2
        i1 >= i2 && break
        arr[begin+i1], arr[begin+i2] = arr[begin+i2], arr[begin+i1]
        final_pivot_index = firstindex(arr) + i1
    end
    if final_pivot_index == firstindex(arr)
        if isempty(it_lr)
            arr[begin], arr[end] = arr[end], arr[begin]
            return lastindex(arr)
        else
            return firstindex(arr)
        end
    end    
    @inbounds arr[begin], arr[final_pivot_index] = arr[final_pivot_index], arr[begin]
    # returns relative position
    return final_pivot_index

The benchmark returns the following:

BenchmarkTools.Trial: 10000 samples with 5 evaluations.
 Range (min … max):   7.604 μs … 39.520 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     20.769 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   20.249 μs ±  3.302 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

                                   ▂▁▂▂▄▄▄▅▅▇▇▇█▇▇▅▃▃
  ▁▁▁▁▁▁▁▁▁▂▂▂▂▂▂▂▂▂▃▄▄▄▃▄▄▄▅▆▆▆▇█████████████████████▇▆▅▃▃▂▂ ▄
  7.6 μs          Histogram: frequency by time        26.4 μs <

 Memory estimate: 0 bytes, allocs estimate: 0.