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 RitterJun 29

@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

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 threadCassandrich
@lritter @pkhuong Yes it needs logarithmic space but that's constant space for all practical purposes because log(n) is bounded by 64.
Jun 29 at 1:11pmWeb
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.