I liked this article because I enjoy reading about data structures that can be used in places where the "obvious" implementation is a list of lists. A lists of lists data structure is general enough for many applications and readily available in many languages, but when using it, I often get the sense that I am spinning wheels writing far more code than necessary to do the desired manipulations. It makes me happy to read about more novel solutions.
Why recursive data structures?
71–80 of 129 posts
Re: Why recursive data structures?
#72Earlier quoted context omitted.
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)
To be clear, I can see why coding it purely recursively would be a bad idea. Same for using linked structures, if that was the concern with the quad tree.
However, it seems that you could use the general recursive definition to find some optimizations that one could do. For example, define a recursive structure to break down a problem until it is small enough that a more traditional method works. (So, don't drop down to the size of a pixel, but do drop down till you have things at cache line size?)
Perusing the wikipedia for Strassen, I see that it scoffs at a ~10% benefit for large matrices. Curious how that holds in light of "deep learning" environments. Especially since 1k x 1k matrices are probably not that uncommon nowdays. Seems like every little bit would help.
Edit to add: THinking of the context of the original post. Yeah... probably not needed for anything in a "snappy" user application. I was thinking more for very large data sets.
Re: Why recursive data structures?
#73Earlier quoted context omitted.
I suppose that would work, but all the operations you do on the region quadtree have to be aware of the "clipping size" as well. For example, the rotation transformation that this article implements would also have to rotate that "clipping size" as the unwanted portion of the square is now in a different location.
That depends If you can live with evenly-sized squares, you can always center the clipping square, and you’re good for rotations, flips, and so on. If you want odd-sized squares, or other shapes, then yes, you’ll need to know how to transform the clipping path/description as well. All in a day’s work!
For odd size squares, simply duplicate the center row and column before rotating, then deduplicate after.
Re: Why recursive data structures?
#74Earlier quoted context omitted.
I suppose that would work, but all the operations you do on the region quadtree have to be aware of the "clipping size" as well. For example, the rotation transformation that this article implements would also have to rotate that "clipping size" as the unwanted portion of the square is now in a different location.
That depends If you can live with evenly-sized squares, you can always center the clipping square, and you’re good for rotations, flips, and so on. If you want odd-sized squares, or other shapes, then yes, you’ll need to know how to transform the clipping path/description as well. All in a day’s work!
[deleted]
Re: Why recursive data structures?
#75Earlier quoted context omitted.
For every complex problem there is an answer that is clear, simple, and wrong.
A slow solution isn't wrong. Just inefficient.
We're talking about several orders of magnitude here.
Is a web page that loads in fifty seconds 'correct' or is it wrong? Is a video format that can only decode 2 frames per second correct, or wrong?
Often, timeliness is an unstated part of the requirements, in which case an academically pleasing solution that isn't practical doesn't fulfill the requirements.
Re: Why recursive data structures?
#76Apparently, 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…
> 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 the image is very large and contains large contiguous regions of solid colors, then a quadtree that doesn't subdivide homogeneous regions can be a much faster approach than a flat pile-o-pixels.
Either way, this article isn't about rotating images.
Re: Why recursive data structures?
#77Earlier quoted context omitted.
A slow solution isn't wrong. Just inefficient.
We're talking about several orders of magnitude here. Is a web page that loads in fifty seconds 'correct' or is it wrong? Is a video format that can only decode 2 frames per second correct, or wrong? Often, timeliness is an unstated part of the requirements, in which case an academically pleasing solution that isn't practical doesn't fulfill the requirements.
>Is a web page that loads in fifty seconds 'correct' or is it wrong? Is a video format that can only decode 2 frames per second correct, or wrong?
If your condition of satisfaction is "I am presenting information to someone who will read it", then "loads in fifty seconds" is wrong, yes.
Re: Why recursive data structures?
#78Recursion 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.
I believe even GCC optimizes tail recursion in some cases.
Re: Why recursive data structures?
#79Earlier quoted context omitted.
A slow solution isn't wrong. Just inefficient.
We're talking about several orders of magnitude here. Is a web page that loads in fifty seconds 'correct' or is it wrong? Is a video format that can only decode 2 frames per second correct, or wrong? Often, timeliness is an unstated part of the requirements, in which case an academically pleasing solution that isn't practical doesn't fulfill the requirements.
I think you're missing the point.
A quadtree is a compact way to store a partition of two-dimensional space, much like you'd store a binary heap in an array.
The implementation of a recursive data structure or algorithm can usually take advantage of tail recursion or trampolining. The practical implementation of a theoretical algorithm may look extremely different, much like you wouldn't literally translate abstract pseudocode to the language of your choice.
Re: Why recursive data structures?
#80Earlier quoted context omitted.
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.
Yes, this is right