Rich Felker
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.
Rich Felker
5932 forward iterate steps to do 1000 reverse iterate steps.
Rich Felker
Expected to be O(n log n), looks like empirically it's about 2/3 n log n.
Rich Felker
@lritter @pkhuong Yes it needs logarithmic space but that's constant space for all practical purposes because log(n) is bounded by 64.
LR
@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.
Paul Khuong
@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)
LR
@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
Rich Felker
@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.
Rich Felker
@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.
Rich Felker
@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.
LR
@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.
Rich Felker
Paul Khuong
@dalias @lritter pretty sure you can bucket iterators by ctz of their index, and keep the highest indexed iterator in each bucket.
GNU social JP is a social network, courtesy of GNU social JP管理人. It runs on GNU social, version 2.0.2-dev, available under the GNU Affero General Public License.
All GNU social JP content and data are available under the Creative Commons Attribution 3.0 license.