Tomas
I don't think that what you envision can be implemented efficiently. After
a few steps, there will be an essentially arbitrary mapping between the
current and the original indices. Each time an index is removed, you'll
have to copy O(N) indices, or O(N) array elements.
However, there may be a way out. Does your algorithm come with a pivot
search? Does it already have a re-mapping of indices? If so, you would need
to change the index mapping at every step such that the to-be-removed index
is the last index. Removing the last element from an array is efficient.
This is for example how LAPACK implements dgesv to solve a linear system.
-erik
On Mon, Dec 21, 2015 at 12:19 PM, Matt Bauman <mbau...@gmail.com> wrote:
> Oh man, fun puzzle. Even without the allocations, SubArrays that depend
> upon an indexing vector (that is, not computable range) are really quite
> slow since there's a lot of indirection at every element access.
>
> You can solve the all-but-one problem with a custom view type fairly
> easily:
>
> immutable SkipIndexVector{T,A} <: AbstractVector{T}
> data::A
> skip::Int
> end
> SkipIndexVector{A<:AbstractArray}(data::A, skip::Int) = SkipIndexVector{
> eltype(A),A}(data, skip)
> Base.size(S::SkipIndexVector) = (length(S.data)-1,)
> Base.linearindexing{T<:SkipIndexVector}(::Type{T}) = Base.LinearFast()
> Base.getindex(S::SkipIndexVector, i::Int) = S.data[i+(i>=S.skip)]
>
> julia> SkipIndexVector(1:10, 4)
> 9-element SkipIndexVector{Int64,UnitRange{Int64}}:
> 1
> 2
> 3
> 5
> 6
> 7
> 8
> 9
> 10
>
> But if you're recursively constructing views of views, that will quickly
> hit the nested type parameter limit and fall back to dynamic dispatch.
> What if you just make a copy of the array and `pop!` the elements in your
> algorithm?
>
> On Monday, December 21, 2015 at 11:55:45 AM UTC-5, Tomas Lycken wrote:
>>
>> Is there a way to construct a view into an array that skips a single
>> element?
>>
>> For example, to view v except the element at index p, I can do sub(v,
>> [1:p-1;p+1:length(A)]). However, allocating the array with indices is a
>> bottleneck in my code. Is there a way or trick to get rid of it?
>>
>> I’m using this in a recursive function, so there will be subsequent views
>> of views of views, etcetera, and I can’t easily refactor it to be a
>> (nested) loop instead (because I don’t want to hand-code 20 nested loops…)
>>
>> // T
>>
>>
>
--
Erik Schnetter <schnet...@gmail.com>
http://www.perimeterinstitute.ca/personal/eschnetter/
