`collect` iterator in reverse

General Usage
1

Is there a generic function for collecting an iterator in reverse? I’m looking for a more efficient version of the following:

itr = (i for i = 1:10) # for example
vec = reverse(collect(itr))

I don’t think the solution is to add a method reverse(itr).
(Though if something like GitHub - goretkin/FixArgs.jl existed in Base, it might be reasonable to add a method to reverse such that reverse(@xquote collect(itr)) worked.)

2

Maybe?

collect(Iterators.reverse(itr))
5 Likes
3

reverse!(collect(itr))?

4

See the section on reverse-order iteration in the iteration manual — the Iterators.reverse(itr) function is generally the way to do reverse iteration, and the manual also describes how to support reverse iteration for custom iterator types.

5

Thanks. It’s not that I want to iterate in reverse order, it’s that I want to collect in reverse order. I wanted a solution that did not require any more from the iterator interface than collect does.

e.g.

julia> collect(Iterators.reverse(Iterators.TakeWhile(<(10), 1:10)))
ERROR: MethodError: no method matching iterate(::Base.Iterators.Reverse{Base.Iterators.TakeWhile{UnitRange{Int64}, Base.Fix2{typeof(<), Int64}}})

but I am not sure how it would work, now that I think about it, if Base.IteratorSize is not Base.HasLength. If it is Base.SizeUnknown, the reverse collect method could use pushfirst!, but that will then take quadratic time.

Thanks, that is more efficient than reverse(collect(itr)), but still does unnecessary operations compared to just collecting in reverse for the situation where IteratorSize is HasLength.

If it helps, in my case, I have a singly-linked list (really a tree where a node points to its parent but not its children), so there is only one possible iteration order (from node to root). Each node also keeps track of its level, so this iterator HasLength.

In summary, I want to iterate “forwards” and collect in reverse, which has has a straightforward implementation in the case that the iterator HasLength.

6

There is likely a ~ O(n\log n) solution where we assign into a Vector in reverse order, and resize ~ exponentially as needed, and return a view into the array starting at the last element that was assigned. (Sort of, but not really, reminiscent of Okazaki fragments - Wikipedia in DNA)

7

Actually this is O(n), and can be accomplished simply by

a = Vector{eltype(itr)}()
for x in itr
    pushfirst!(a, x)
end

in Julia. But it’s obviously better if you know the length. e.g.

collectreverse(itr) = collectreverse(itr, Base.IteratorSize(itr), Base.IteratorEltype(itr))

function collectreverse(itr, ::Union{Base.HasLength,Base.HasShape}, ::Base.HasEltype)
   a = Vector{eltype(itr)}(undef, length(itr))
   offset = length(a)+1
   for (i,x) in enumerate(itr)
      a[offset - i] = x
   end
   return a
end

function collectreverse(itr, ::Any, ::Base.HasEltype)
   a = Vector{eltype(itr)}()
   for x in itr
      pushfirst!(a, x)
   end
   return a
end

collectreverse(itr, ::Any, ::Any) = reverse!(collect(itr))

That being said, I doubt the performance improvement compared to reverse!(collect(itr)) will matter in most applications.

1 Like
8

I see, I had assumed pushfirst!(vec, elt) was always linear in length(vec), but I see now that its written in terms of _growbeg!.

So, my take-away is that there isn’t an existing name in Base for this generic function for collecting in reverse, and perhaps there shouldn’t be because reverse!(collect(itr)) is sufficient in most applications.

By the way, it seems like you could do just:

function collectreverse(itr, ::Any, ::Base.HasEltype)
   a = Vector{eltype(itr)}()
   prepend!!(a, itr) # [EDIT]
   return a
end
9

This will push the iterator object as the first element, which is not what you want. For example:

julia> pushfirst!(Any[], 1:10)
1-element Vector{Any}:
 1:10
1 Like
10

Ah, yes, of course. I did mean only prepend!(vec, itr). I got tripped up looking at

11

That won’t reverse the order of itr.

1 Like
12

sigh, indeed! Thanks for catching that.