CODEWITHSUNDEEP
julia
kungfooman
kungfooman

Reputation: 4893

Remove element from vector while iterating over it

My first try was:

I = Vector{String}(["first", "second", "third", "fourth"])

for i in I
    if i == "fourth"
        splice!(I, 4)
    end
    print("$i\n")
end

Which ends up in a Bounds error:

BoundsError(String["first", "second", "third"], (5,))

Then I figured it kinda out the "handwritten" way:

I = Vector{String}(["first", "second", "third", "fourth"])

state = start(I)

while ! done(I, state)
    (i, state) = next(I, state)

    if i == "fourth"
        splice!(I, state - 1)
        print("Delete element i=$(state - 1)\n")
        state = state - 1
        continue
    end

    print("Got: i=$i state=$state\n")
end

Output:

Got: i=first state=2
Got: i=second state=3
Got: i=third state=4
Delete element i=4

But yea, thats neither easy to read nor easy to write. Is there any "julian" way to delete elements from a vector, while iterating over it? Or is there any recommended data structure which explicitly supports it via some function call?

Upvotes: 1

Views: 2299

Answers (2)

tim
tim

Reputation: 2096

Calling splice! many times is very slow for large arrays:

function d!(I, s)
    i = 1
    while i <= length(I)
        if I[i] == s; splice!(I,i);
        else i += 1;
        end
    end
end

function t()
    I = rand(1:10, 1000000)
    s = 1
    d!(I,s)
    I
end

julia> @btime t()
 6.752 s (2 allocations: 7.63 MiB)
899975-element Array{Int64,1}:
...

It is better to call deleteat! only once with an iterator that produces all indices that should be deleted, e.g.,

function d2!(I, s)
    deleteat!(I, (i for i in eachindex(I) if I[i] == s))
end

function t2()
    I = rand(1:10, 1000000)
    s = 1
    d2!(I,s)
    I
end

julia> @btime t2()
 15.889 ms (8 allocations: 7.63 MiB)
900414-element Array{Int64,1}:
...

Upvotes: 1

Tasos Papastylianou
Tasos Papastylianou

Reputation: 22225

Solution 1: using shift! and push!

julia> I = Vector{String}(["first", "second", "third", "fourth", "fifth"]);
julia> Inew = Vector{String}(0);
julia> while !isempty(I)
         i = shift!(I);
         if i == "fourth"; println("Skipped $i"); 
         else println("Got: i = $i"); push!(Inew, i);
         end
       end
Got: i = first
Got: i = second
Got: i = third
Skipped fourth
Got: i = fifth

julia> show(Inew)
String["first", "second", "third", "fifth"]

Solution 2: Using splice!

julia> I = Vector{String}(["first", "second", "third", "fourth", "fifth"]);
julia> i = 1;
julia> while i <= length(I)
         if I[i] == "fourth"; splice!(I,i);
         else i += 1;
         end
       end
julia> show(I)
String["first", "second", "third", "fifth"]

However, note that this is not necessarily more efficient, since new memory is allocated for I whenever you splice it anyway (since it's changing size).

Solution 3: using findin and deleteat! (i.e. "the one-liner"):

julia> I = Vector{String}(["first", "second", "third", "fourth", "fifth"]);
julia> deleteat!(I, findin(I, ["second", "fourth"]))
3-element Array{String,1}:
 "first"
 "third"
 "fifth"

If you don't really need to perform any other intermediate actions (e.g. printing) and you just want to identify and delete elements, then this is probably the way to go.

Further ramblings:

Also, regarding your attempt to do this via a for loop: a cardinal rule when iterating with a for loop (in any language) is that the state of the variable that you're iterating over does not change. Disobeying this rule will usually lead to errors in the best case, or undefined behaviour and silent errors in the worst case. If the state of the variable is meant to change, then you're not looking at a 'for loop' iteration, but at the more general while loop which makes no assumption of consistent state.

I.e. what you've done here is the correct approach and you shouldn't be looking for one that involves a for loop. (and if you do happen to find one, consider that bad code and leave it alone :p ). But, yes, there were nicer-looking ways of doing it; however it's worth noting that what you did is basically re-discover the wheel, in that you made explicit the interface on which the for loop actually relies in julia. I.e. the following code: 

for i in MyCollection; print("$i "); end

essentially gets internally translated as its equivalent: 

state = start(MyCollection)
while !done( MyCollection, state)
  (i, state) = next(MyCollection, state)
  print("$i ")
end

Upvotes: 3

Related Questions