John Gietzen
Reputation
1,058
Top tag
Next privilege 2,000 Rep.
 Feb 28 awarded Nice Question Dec 12 awarded Yearling Feb 5 awarded Favorite Question Aug 12 awarded Yearling Jul 2 awarded Curious May 9 awarded Nice Question Mar 19 awarded Good Question Mar 7 awarded Enlightened Mar 7 awarded Nice Answer Nov 25 awarded Notable Question Oct 9 awarded Famous Question Aug 4 comment Is it possible to generate an $M$-order Hilbert Curve without consuming $O(M^2)$ memory? @StevenStadnicki: Cool, thanks for your help! Aug 4 comment Is it possible to generate an $M$-order Hilbert Curve without consuming $O(M^2)$ memory? @StevenStadnicki: FYI, I'm treating the strings themselves as queues by taking a substring of all but the first character for each replacement. Aug 4 comment Is it possible to generate an $M$-order Hilbert Curve without consuming $O(M^2)$ memory? @Steven, I don't think that I will actually have 3/4 of the full path on the stack, since the elements in the stack are stored unexpanded. Only when I encounter a replacement do I push the expanded form onto the stack. This is essentially equivalent to a recursive solution, but is easier to implement as an iterator. Aug 4 answered Is it possible to generate an $M$-order Hilbert Curve without consuming $O(M^2)$ memory? Aug 4 comment Is it possible to generate an $M$-order Hilbert Curve without consuming $O(M^2)$ memory? I would like to generate "the" Hilbert curve, which I would then adapt to my specific use case. My only criteria is that the interface is a sequence of relative moves (N, S, E, W) and that it consumes a linear or sub-linear amount of memory with respect to the order. Aug 4 revised Is it possible to generate an $M$-order Hilbert Curve without consuming $O(M^2)$ memory? added 14 characters in body Aug 4 asked Is it possible to generate an $M$-order Hilbert Curve without consuming $O(M^2)$ memory? Jul 20 awarded Yearling Jun 20 awarded Good Question