Efficient popnfirst!?

General Usage Performance
1

Hi,

I was wondering if it exists an efficient implementation of popfirst! for an array that allows a n argument to request multiple pops at once (instead of calling popfirst! n times).
Like popfirst!(a::Array, n::Int = 1)

If not, is there a reason that this can’t be done efficiently ?

1 Like
2

What problem do you have with: [popfirst!(xs) for _ in 1:n] ?

3

deleteat!(a, 1:n) might be efficient, I’ve not looked at the implementation, but I’d assume it’s slightly better.

2 Likes
4

It’s just that I don’t know if it’s efficient to do multiple calls like that instead of removing one by one.

5

Okay thanks, it will do the trick for what I need. I didn’t know deleteat accepts ranges.

6

It’s just that I don’t know if it’s efficient to do multiple calls like that instead of removing one by one.

It is efficient.

It will be a static dispatch.
and julia’s Vector can efficiently grow and shrink at both ends.

Edit:
actually deleteat! is much faster. Not sure why

julia> @btime [popfirst!(x) for _ in 1:1000] setup=(x=rand(1_000_000));
  6.954 μs (1 allocation: 7.94 KiB)

julia> @btime deleteat!(x, 1:1000) setup=(x=rand(1_000_000));
  136.274 ns (0 allocations: 0 bytes)
1 Like
7

Probably the lack of allocation since it’s not creating the comprehension?

8

Might be better to use foreach since otherwise, you create a redundant vector.

But for this specific case, I would think deleteat! be significantly faster since it should be O(1) instead of O(n).

2 Likes
9

Oh yeah, it doesn’t return the deleted elements.
It returns the remaining elements.

I assume though if you are using popfirst you want the deleted elements.
(also why can’t use foreach).

10

Well, not in my case but it’s true that it could be.

11

Yeah, true, probably saving x[1:n] prior to deleteat! would be a better option then, maybe:

julia> function popnfirst!(xs, n)
           out = xs[1:n]
           deleteat!(xs, 1:n)
           return out
       end
1 Like
12

Do you think it would be worth doing a PR in Base.array.jl ?

It could even be a new method for popfirst!() to avoid a new name.

1 Like
13

splice! may be what you want actually…

julia> splice!([1, 2, 3, 4, 5], 1:3)
3-element Vector{Int64}:
 1
 2
 3
2 Likes