Live data from Hacker News

Why recursive data structures?

raganwald.com

51–60 of 129 posts

Re: Why recursive data structures?

#51

Quadtrees 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.

I 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.

Re: Why recursive data structures?

#52

Apparently, 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?

Re: Why recursive data structures?

#53

Apparently, 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…

I don't think the point of the article was to present an efficient and novel solution for image rotation. It was just a nicely visual example of a recursive data structure.

Re: Why recursive data structures?

#54

Earlier quoted context omitted.

Even with a non-mathematical definition such as yours, I don't see the isomorphism. Recursive code that acts on a quadtree does not itself take the shape of a quadtree. Not the text, not the AST, not the machine code. The code is treelike, but that's because all code is treelike(1). As a counterexample, consider code that acts on arbitrary graphs. DFS on an arbitrary graph doesn't itself take the form of an arbitrary…

I was speaking to the relationship between the code's runtime behaviour and the structure of the data. When I say the word "algorithm," am I talking about the way the code is noted in a particular language? Or the steps one takes to perform the operation?

In some other languages, even the notation itself has obvious parallels between data definition and process definition. Consider a list and `map` in Standard ML:

    datatype 'a list =
      Nil
    | Cons of 'a * 'a list;
    
    val rec map : ('a -> 'b) -> 'a list -> 'b list =
      fn f => fn xs =>
        case xs of
          Nil          => Nil
        | Cons(x, xs') => Cons(f x, map f xs');
The case analysis of a list is obviously isomorphic to the definition of a list, in the sense that the data and the process have the same shape: a list is a `Nil` or a `Cons(item, more list)`, while a function that traverses a list checks if a list is `Nil` and does something, otherwise it's a `Cons(...)` and it does something else. The linear recursive nature of the list definition lends itself naturally to algorithms which are similarly linearly recursive. (`map` itself can be said to create homomorphisms, but that's beside the point here; I use this particular example only because it happens to be the simplest non-trivial one I could think of).

Okay, so perhaps this isn't quite what "isomorphic" means in category theory, or topology, or graph theory, or set theory, or what have you. Even in mathematics, though, it's obvious that terminology gets borrowed between the branches when there are concepts that are somehow related. Why should programming be any different? So, I argue that it's not wrong to use "isomorphic" in the sense that you have—in fact, it's a term that I've seen used in the same sense on numerous occasions, and something that I think experienced programmers have internalized. In this case, the structure of the data, that is, a linearly recursive collection of elements, precisely matches the structure of the process, that is, a linearly recursive traversal of elements. Whether or not there actually exists an isomorphism between the two is irrelevant to the notion that the two are isomorphic, that is, they have "equal shapes".

I think a habit of thinking of words in an etymological way leads naturally to borrowing those words for similar concepts. This is neither the first time such a thing has happened, nor will it be the last. To knowledgeable parties, your use of the word communicated a characteristic of your program in a succinct way that you continued to illustrate—that the shape of the quad tree data structure reflects the shape of the algorithms used to process instances of said structure.

One might say that the various meanings of the term "isomorphic" are... isomorphic ¬_¬

Re: Why recursive data structures?

#56

Apparently, 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.

Re: Why recursive data structures?

#58
Recursion 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.

Re: Why recursive data structures?

#59
Using 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!

Re: Why recursive data structures?

#60

Quadtrees 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.

I 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 al…

Could you go on a bit more (or post a link to somewhere you do)?
Post reply on HN