CassandrichJun 29

Just designed and tested an algorithm to build a reverse-iterator on top of an iterator that can only run in forwards direction (part of the #musl collation project) and it seems to be good!

63 underlying forward-iterate steps to perform 21 reverse-iterate steps in simple test case.

Show threadCassandrichJun 29
5932 forward iterate steps to do 1000 reverse iterate steps.
Show threadCassandrichJun 29
Expected to be O(n log n), looks like empirically it's about 2/3 n log n.
Show threadLeonard Ritter

@dalias what.. how is that even logically possible. it needs n iters to reach the beginning of the iteration range. then m iters to go through the range, buffer all results. then another m to go through the buffer in reverse (the actual reverse iteration). space needed is also m.

do you know of a different way to do this? b/c it doesn't seem like 1-step-iterators give us much freedom here.

or do you build an ad-hoc search tree? then the space needed would be log m and m log m makes more sense

Jun 29 at 5:52amWeb
Show threadPaul KhuongJun 29
@lritter @dalias you keep log n copies of earlier iterators (and always keep a copy of the initial iterator). The copies are more dense when you're closer to the current location (and fully dense just before)
Show threadLeonard RitterJun 29

@pkhuong @dalias yeah. so, an ad-hoc search tree. it has fragments that appear in in-place sorting algorithms.

then it is all the more important to mention the time-for-space trade-off, since that's the whole point.

Show threadCassandrichJun 29
@lritter @pkhuong Yes it needs logarithmic space but that's constant space for all practical purposes because log(n) is bounded by 64.
Show threadLeonard RitterJun 29
@dalias @pkhuong yep. that is absolutely worth mentioning. :) nice idea. when i implemented iterators for our language i was considering adding a backwards-from-forward converter but never thought beyond the "buffer it all" approach, and didn't implement it.
Show threadCassandrichJun 29
@pkhuong @lritter Yep, this is exactly how it works. In fact initially it only keeps one copy, of the initial iterator; it then pushes another one each time it reaches the halfway point between the last one it dropped and the (known-index) end position, and it pops them as they become irrelevant by being for an already-traversed position.
Show threadCassandrichJun 29
@pkhuong @lritter Lovely aside: this can also be applied to video (if your decoded objects can be copied, which may be a bad assumption for typical existing implementations) and solves problems I wanted to solve decades ago for being able to transform video efficiently in random-access-like patterns without having to transcode to a keyframe-dense form.
Show threadLeonard RitterJun 29
@dalias @pkhuong i'm working on fixpoint-iterative primitives lately (as an alternative to structured control flow) that are strictly forward-facing but trivially copyable, and this would be an ideal solution to support time-reversed debugging.
Show threadLeonard RitterJun 29
@dalias @pkhuong now i'm wondering if Braid also used this.
Show threadCassandrichJun 29
@lritter @pkhuong For your case where there's no a priori finite end time, I think you need a slightly different strategy that's not a pure stack. You need to be able to decimate and repack the waypoints to maintain a logarithmic bound on them.
Show threadPaul KhuongJun 29
@dalias @lritter pretty sure you can bucket iterators by ctz of their index, and keep the highest indexed iterator in each bucket.
Show threadCassandrichJun 29
@pkhuong @lritter Yes that seems like a valid strategy.
Show threadLeonard RitterJun 29

@dalias @pkhuong
yes (took a while to write this):

if i'm not mistaken, the stack levels to maintain per index are invariant if one follows a strict log2 distribution;

e.g. the stack for #121 is { #64, #96, #112, #120, #121 } (since 121 = 0b1111001, so 64, 64+32, 64+32+16, 64+32+16+8, skip, skip, 64+32+16+8+1)

but it might be necessary to keep the growing loglevels to the MSB also; so, for our example, the stack starts with #1, #2, #4, #8, #16, #32 before reaching its peak at #64.