The argument would be stronger if he wasn't swapping an O(n) algorithm for O(n log(n)). With the recursive implementation you have to touch every element once for each recursion level.
Why recursive data structures?
61–70 of 129 posts
Re: Why recursive data structures?
#62The argument would be stronger if he wasn't swapping an O(n) algorithm for O(n log(n)). With the recursive implementation you have to touch every element once for each recursion level.
Re: Why recursive data structures?
#63Apparently, every computer science problem has easy to understand solution that’s easy to implement but awfully slow in practice. This is one of them. Rotating images that way isn’t CPU bound problem. It’s RAM bandwidth and RAM latency bound problem. The optimal data structure for that is not recursive, it’s 2D array of small square blocks of pixels. If pixels are bits, I’d bet on either 8x8 or 16x16 blocks. If they…
>> we’d provide much snappier behaviour using coloured quadtrees
> That statement was true 30 years ago, no longer a case.
The colored quadtrees are an optimization over the plain quadtrees earlier in the article, reducing the number of comparisons for some images. That will be more efficient 300 years from now just as much as it was 30 years ago. In context it is perfectly obvious that "much snappier" does not refer to the totally different techniques used by actual graphics software.
It's a toy implementation used as an example, if you get hung up on the example, you miss the whole point.
Re: Why recursive data structures?
#64Recursion is often times less efficient than a well designed and concrete imperative solution, even if the imperative solution uses more memory. This is because most languages, the stack is not free. There's a lot of meta data and house keeping that goes on when you invoke a function to support things like stack traces and introspection. The provided example (at least to me) is also convoluted and fails to illustrate…
Are you aware of a programming language/compiler that optimizes on recursively written code? I'm finding it difficult to imagine a PL where stack _isn't_ free except tail-recursive code.
Re: Why recursive data structures?
#65The argument would be stronger if he wasn't swapping an O(n) algorithm for O(n log(n)). With the recursive implementation you have to touch every element once for each recursion level.
For quadtrees come into their own when there are optimizations that fit the problem domain, such as the coloured quadtrees explained at the end of the post: They are much faster for images with large blank areas.
They aren’t discussed in the post, but quadtrees are also very amenable to memoizing common operations.
Re: Why recursive data structures?
#66Recursion is often times less efficient than a well designed and concrete imperative solution, even if the imperative solution uses more memory. This is because most languages, the stack is not free. There's a lot of meta data and house keeping that goes on when you invoke a function to support things like stack traces and introspection. The provided example (at least to me) is also convoluted and fails to illustrate…
Are you aware of a programming language/compiler that optimizes on recursively written code? I'm finding it difficult to imagine a PL where stack _isn't_ free except tail-recursive code.
My understanding is that it's the opposite -- function calls expend a cost to save (and later restore) the registers and push the locals onto the stack. Tail recursive functions on the other hand can be implemented as a jump to the top of the function, right after all the stack bookkeeping, and so saves on that expense.
Re: Why recursive data structures?
#67Apparently, every computer science problem has easy to understand solution that’s easy to implement but awfully slow in practice. This is one of them. Rotating images that way isn’t CPU bound problem. It’s RAM bandwidth and RAM latency bound problem. The optimal data structure for that is not recursive, it’s 2D array of small square blocks of pixels. If pixels are bits, I’d bet on either 8x8 or 16x16 blocks. If they…
For every complex problem there is an answer that is clear, simple, and wrong.
A slow solution isn't wrong. Just inefficient.
Re: Why recursive data structures?
#68Earlier quoted context omitted.
> When someone else uses it in conversation, it's absolutely guaranteed that the person is a pretentious asshole. I don't get your angle here. You realise an isomorphism is actually a well-defined mathematical concept, right? Are you advocating we use another, plainer word for an isomorphism, or do just naturally get angry when you hear words you don't understand?
Pretentious or not, the term is used erroneously here. Recursive data structures and recursive algorithms are, quite plainly, not isomorphic. They are not two equivalent representations of the same thing. Something that is isomorphic to a recursive function that works on a quadtree would be an imperative function that works on a quadtree with identical functionality. tl;dr: I think the author meant "synergistic".
I am following the mathmatical definiton of isomorphism:
The two sets are Quadtree instances and calls of `myself`. The map from calls to instances is "instance that was given as argument". This map is obviously bijective. The structure that is preserved is "is a child of".
QED :)
Re: Why recursive data structures?
#69Apparently, every computer science problem has easy to understand solution that’s easy to implement but awfully slow in practice. This is one of them. Rotating images that way isn’t CPU bound problem. It’s RAM bandwidth and RAM latency bound problem. The optimal data structure for that is not recursive, it’s 2D array of small square blocks of pixels. If pixels are bits, I’d bet on either 8x8 or 16x16 blocks. If they…
At face value, I don't actually see where you contradict the article. The recursive nature of this solution is akin to recursive matrix multiplication. Which can be a way to setup memory fetches to stay optimal. (Could... I have no data to say it is.) Any chance you know of any benchmarks exploring this?
Recursive matrix multiplication is in general a bad idea (Strassen, for example, loses a little bit of stability and is not cache-friendly)
Re: Why recursive data structures?
#70Umm... or, I could just rotate a square a quarter-turn by iterating over the square's elements:
for (x = 0; x Of course, in certain representations of the square (such as using a 1-d array) even simpler algorithms can be used.