14 ms·
Why recursive data structures?
- eridius 10y agoThe footnotes say that all the functions can be adjusted to deal with non–power-of-2 squares, but it's not obvious how this is done when working with region quadtrees.
- braythwayt 10y agoOne way is to represent squares as a square-that-is-a-power-of-two, plus a “clipping size” that is used when the square is rastorized. If you’re using a lot of optimizations for blank regions, the extra padding has a negligible effect on performance.
- eridius 10y agoI 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.
- braythwayt 10y agoThat 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!
- eridius 10y agoAnother approach would be to allow a cell's value to be null, meaning it should be clipped, but then you run the risk of having transforms on the region quadtrees that cause the null cells to migrate inwards into the square (such that they cannot simply be clipped off later).
- jlas 10y agoOne can use recursive properties better if the structure divides equally. So if not having a strict quadtree is okay, they can divide the square into 3x3, 5x5, etc
- pacaro 10y agoFor odd size squares, simply duplicate the center row and column before rotating, then deduplicate after.
- deleted 10y ago[deleted]
- tallanvor 10y agoYes, that made me lose a lot of confidence in the article. This shouldn't have been a footnote. It should have been stated in the beginning that the author was only considering powers of two, and the footnote should have been a reference to ways to deal with other sizes - my very first question, before I got to the footnotes, was "How would I deal with a 3x3 square?"
- dukerutledge 10y agoReginald is definitely hinting at hylomorphisms here. I'd be curious to see if stream fusion could be achieved in JS for a hylomorphism.
- braythwayt 10y agoIsn’t `multirec` a function for making hylomorphisms? The recursive dividing is the anamorphism, and the combining of the results is the catamorphism. As written, however, `multirec` does not efficiently compose. For two constructions to be compatible, they’d have to share their decomposition strategy, including `indivisible` and `divide`. `value` probably composes neatly, but `combine` is a little thorny as the current implementation does two jobs: Processing the data and reconstructing the form of the data. A composable `multirec` does sound interesting, however. Hmmm...
- jaredtobin 10y agoIt's exactly a hylomorphism. Here's a possibly more familiar-looking Haskell form: {-# LANGUAGE DeriveFunctor #-} {-# LANGUAGE LambdaCase #-} import Data.Functor.Foldable import Data.List.Split data QuadTreeF a r = NodeF r r r r | LeafF a | EmptyF deriving Functor builder :: [a] -> QuadTreeF a [a] builder = \case [] -> EmptyF [x] -> LeafF x xs -> NodeF a b c d where [a, b, c, d] = chunksOf (length xs `div` 4) xs consumer :: QuadTreeF a [a] -> [a] consumer = \case EmptyF -> [] LeafF a -> [a] NodeF ul ur lr ll -> concat [ll, ul, ur, lr] rotate :: [a] -> [a] rotate = hylo consumer builder
- braythwayt 10y agoFYI, this article on recursive combinators from 2008: http://www.lazutkin.com/blog/2008/06/30/using-recursion-combinators-javascript/ http://www.lazutkin.com/blog/2008/06/30/using-recursion-comb...
- maxdemarzi 10y agoGot an opportunity to do this recently using a graph mapped on to a K^2 Tree to find out if a relationship existed or not. See https://maxdemarzi.com/2016/12/27/connected-2/ https://maxdemarzi.com/2016/12/27/connected-2/
- pmiller2 10y agoThat was a lot of words to say "because the languages we use to solve problems is naturally recursive."
- deleted 10y ago[deleted]
- jgalt212 10y agotrue, but sometimes people need to be convinced by a preponderance of evidence.
- deleted 10y ago[deleted]
- ianamartin 10y agoI love the word "isomorphic". It's by far the most efficient word in the English language. When someone else uses it in conversation, it's absolutely guaranteed that the person is a pretentious asshole. When you use it in a conversation, the same is also true. It's only ever acceptable in written contexts or if you happen to be Douglas Hofstadter.
- lacampbell 10y ago> 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?
- braythwayt 10y agoConsidering that TFA pokes fun at the word in the very first footnote, I took this comment to be mostly in jest. But if we’re going to be serious about it, technical jargon is really only appropriate when the speaker is 100% sure the audience 100% understands it. There is sometimes a problem (I wouldn't use personal terms to describe it, but still) where technical terms are slung about without regard for whether people understand them. That’s poor communication, and as a bad side-effect, it encourages people to misuse the words in ways that don’t match the formal definitions. In any event, if a comment is criticizing the article for using the word “isomorphism,” we could quite fairly ask if there is a bijective between algorithm and data structure, and whether the morphisms preserve behaviour. If not... Perhaps TFA is at fault.
- lacampbell 10y ago> But if we’re going to be serious about it, technical jargon is really only appropriate when the speaker is 100% sure the audience 100% understands it. I disagree. Half the reason I come here is to be exposed to new ideas or concepts. This isn't a lecture, I'll gladly take time to learn about a new concept if it seems relevant.
- mypalmike 10y agomaxIndex = size - 1 for x in range(0, size): for y in range(0, size): # swap diagonally, invert horizontally out[x][y] = in[maxIndex - y][x]
- zachrose 10y agoThe 'multirec' function here looks to have a lot in common with Clojure's transducers. Can anyone more knowledgeable do a compare and contrast?
- braythwayt 10y ago`multirec` is a combinator, it transforms functions into other functions. `transducers` are "composable algorithmic transformations.” `multirec` as presented here is not composable the way transducers are composable. It is, however, an extremely stimulating thing to consider. https://news.ycombinator.com/item?id=13305176 https://news.ycombinator.com/item?id=13305176
- cousin_it 10y agoQuadtrees are neat. Though I guess general purpose image processing would be better served by either raster or vector representation. Maybe a better showcase would be something like collision detection or geospatial indexing.
- braythwayt 10y agoIf you really want to show quadtrees off... http://raganwald.com/hashlife/ http://raganwald.com/hashlife/ But yes, I’d love to read more about things like collision detection and geospatial indexing.
- bpicolo 10y ago(You probably know this but) quadtrees are indeed used extensively for both of those things. Whole buncha programs can use them (though there are other good options as well) for geospatial: https://www.elastic.co/guide/en/elasticsearch/reference/current/geo-shape.html https://www.elastic.co/guide/en/elasticsearch/reference/curr...
- phkahler 10y agoI have a bit-rotting ray tracing library where I put all geometric primitives in an oct-tree. When you fire a ray through a 2x2x2 cube it intersects at most 4 of the child nodes. You can see that because the ray must originate in one octant, and it must cross one of the 3 partition planes to reach another octant and it can only cross each one once. There are lots of other interesting properties. One of my favorite algorithms is one that takes an oct-tree and a triangle and inserts the triangle into the tree. I allow primitives to occupy more than one tree node, so first I decide what size node they will occupy and then I use a recursive algorithm to "voxelize" the triangle. I found a heuristic for determining optimal node size. The ability for node to contain and arbitrary number of primitives and for each primitive to be in an arbitrary number of nodes resulted in a very interesting data structure that allows fast deletes and inserts of the primitives. But I'm really starting to ramble now.
- SomeStupidPoint 10y agoCould you go on a bit more (or post a link to somewhere you do)?
- taeric 10y agoThis is worth it, if only for the footnotes. Don't skip them!
- matt4077 10y agoRaganwald is the poet of code.
- nitrix 10y agoI stopped reading at the first sentence when he improperly used `isomorphic`. I thought it made no sense at all so I looked up the footnote... just to get a big middle finger from the author. What a con artist. Moving on.
- wonnage 10y agoIt's a great read, you shouldn't be so thin skinned
- deleted 10y ago[deleted]
- Ericson2314 10y agoIf you suspend your disbelief until the end, it's an inductive anti-hypothesis. Induction is recursion under intuitionism.
- noobiemcfoob 10y agoToday I learned a different, much more harsh meaning for "bespoke" I've never picked up on a hipster connotation from the word, though I did feel it was coming back into vogue.
- vostok 10y agoIt's been popular in the derivatives space for a while now.
- skybrian 10y agoBefore reading this, I would have said that we need to use recursion to model constructs like programming languages that are specifically designed to have a recursive structure. They are naturally recursive because someone designed the language that way. (By contrast, building a basic database-backed website doesn't require any recursion, unless you're modeling a hierarchy.) But with a compiler, there is the same pattern of converting to a recursive data structure (parsing), performing manipulations, and then converting back to a non-recursive structure (object code generation).
- Const-me 10y agoApparently, 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 are RGB, one good format for those images, optimized for rotations, is BC7 https://www.opengl.org/registry/specs/ARB/texture_compression_bptc.txt https://www.opengl.org/registry/specs/ARB/texture_compressio... the decompressor being implemented right in the graphics hardware. > If we were writing an image manipulation application, we’d provide much snappier behaviour using coloured quadtrees to represent images on screen. That statement was true 30 years ago, no longer a case. Branch misprediction is expensive, memory latency is huge, RAM is a block device now (the block size typically being 16 bytes for dual-channel DDR). In addition, some displays now show 8+ megapixels, and most show 16M colors. For an image manipulation application, that recursive thing ain’t good at all.
- taeric 10y agoAt 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?
- GFK_of_xmaspast 10y agoRecursive matrix multiplication is in general a bad idea (Strassen, for example, loses a little bit of stability and is not cache-friendly)
- taeric 10y agoTo 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.
- stephenboyd 10y agoAs a web developer, I appreciate this rare use of JavaScript in a CS lesson.
- braythwayt 10y agoJavaScript is the language most likely to be familiar to the audience I'm trying to reach. But at a certain point, it gets in the way of explaining an idea rather than making it easier. I think this essay stays on the right side of that trade-off.
- iamleppert 10y agoRecursion 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 the elegance of using a recursive data structure. In general parlance, an affine transform or rotation matrix would both be more elegant and readable.
- devty 10y agoAre 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.
- 35bge57dtjku 10y agoI believe even GCC optimizes tail recursion in some cases.
- andreareina 10y agoMy 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.
- nick0garvey 10y agoYes, this is right
- junke 10y agoTail-merging doesn't only apply to recursive functions. As soon as you don't need to store intermediate result, you can jump to another function without allocating a frame.
- 10y ago
- logicallee 10y agoUsing the same didactic style as the author, I would like to show how it is possible to replace the image rotation algorithm with a NOOP. First, look at any of the pictures shown. Next, turn your head to the side 90 degrees. Although the computer's output hasn't chamged, by redefining requirements we can achieve the the desired change. The fastest way to rotate a square is a noop (or O(1) message to the user): turning your head. Never forget it!
- Greek0 10y agoThe 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.
- braythwayt 10y agoFor 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.
- Greek0 10y agoThe 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.
- lucker 10y agoUmm... or, I could just rotate a square a quarter-turn by iterating over the square's elements: for (x = 0; x < N; x ++) { for (y = 0; y < N; y ++) { newSquare[x][y] = oldSquare[y][N-1-x]; } } Of course, in certain representations of the square (such as using a 1-d array) even simpler algorithms can be used.
- c2the3rd 10y agoI 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.
- pjc50 10y agoBut why recursive data structures? (Both a recursion joke and a Zoolander joke)
- nickkell 10y agohttps://news.ycombinator.com/item?id=13308230 https://news.ycombinator.com/item?id=13308230
- johnfn 10y agoI really enjoyed this article because it introduced me to a new data structure and some very elegant and (subjectively) beautiful algorithms. I came onto HN expecting some insightful commentary and instead got 80 comments griping about how it wasn't 100% optimized. Sigh.
- deleted 10y ago[deleted]
- braythwayt 10y agoAuthor here. Nevertheless, there's learning gold in those comments. Take the gold, leave the mud.
- nemoniac 10y agoInteresting article. While reading it I wrote a version of the code in Racket. YMMV but I think it turns out cleaner, especially towards the end. https://gist.github.com/bon/801fdb6dbced0efdb83a358bb4f6285f https://gist.github.com/bon/801fdb6dbced0efdb83a358bb4f6285f
- teddyh 10y agoThe algorithm to rotate images can be illustrated by running /usr/lib/xscreensaver/blitspin blitspin - rotate a bitmap in an interesting way The blitspin program repeatedly rotates a bitmap by 90 degrees by using logical operations: the bitmap is divided into quadrants, and the quad‐ rants are shifted clockwise. Then the same thing is done again with progressively smaller quadrants, except that all sub-quadrants of a given size are rotated in parallel. So this takes O(16×log2(N)) blits of size NxN, with the limitation that the image must be square, and the size must be a power of 2. Movie here, for those without XScreenSaver installed: https://www.youtube.com/watch?v=UTtcwb-UWW8 https://www.youtube.com/watch?v=UTtcwb-UWW8
- braythwayt 10y agoThanks, I have included the video and a credit to you in the essay.
- iamaelephant 10y agoWait, the way he defines the quad tree color property requires that you manually input the color for each region. If you wanted this to be part of a general purpose algorithm in real software then you'd need another algorithm that determines the color of each region - a very expensive operation if you wanted the maximum benefit.