It's a mistake to consider $foo [$bar] {$baz {$quux}} to be a complex datastructure. It ain't. It's still arrays and hashes. One does the same thing in C, except that one is more likely to use a struct instead of a hash. But in C, that still isn't complex. Now, a five dimensional partition tree using epsilon nets, with associated k-d trees in the nodes, that's a complex datastructure.

The only thing "complex" about $foo [$bar] {$baz {$quux}} is the long single expression to get an element out of it. But you have your data, and you need to store you data somewhere. Preferably in a way to retrieve your elements. And regardless whether you use arrays, hashes, or objects, you have two options. Either you nest, or you don't. And if you nest, you either use long single expressions to get to the data, or many short expressions. (Note that this is independent of the language you are working in). If you don't nest, I doubt your datastructure becomes any clearer.

BTW, I don't agree with Rob Pikes claim which FoxtrotUniform brings up. Nor do I agree with Wirth's "Algoritms + Datastructures = Programs". I believe that datastructures imply the algorithms. One cannot choice a datastructure and afterwards come up with the algorithm. The algorithm has to follow the rigids of the datastructure.

Abigail

You said:

Now, a five dimensional partition tree using epsilon nets, with associated k-d trees in the nodes, that's a complex datastructure.

Seems arbitrary to me. How about 4 dimensional? Or 3 dimensional using red-black trees? Or AVL trees? Where in particular do you draw the line in the data structure sand that says complex on this side, everything else on that side? I'm not saying that complex data structures don't exist, I'm just wondering about how you distinguish complex from not complex...

–hsm

"Never try to teach a pig to sing…it wastes your time and it annoys the pig."

I'm just wondering about how you distinguish complex from not complex.

Well, I don't think it's possible to draw a sharp border. Just as it's almost impossible to draw the line when you call it "light" or "dark". That doesn't mean that in a lot of cases, it's clear when it's "light" or "dark". ;-)

Anyway, for me, to call a datastructure complex it usually satisfies these points:

• It stores elements where the place in the structure implies (or is implied by) a (spacial) relationship between the elements.
• It's optimized such that queries and/or updates can be done in less time than a full scan, or a rebuild of the entire datastructure.
• It will often have some kind of associated datastructure.
But I don't apply the rules very strict.

Abigail

The only major thing that irritates me about Perl's way of doing complex data structures is that the specification is implicit: you never sit down and declare a "Hash of Hashes of Arrays", for instance: you put arrayrefs in a hash, then a ref to that hash in another hash. And you never sit down and code up a list of admissible hash keys... if you haven't documented what's expected to be in the hash, and where it's inserted, your code can be pretty impenetrable.

On the whole, I think this way of doing things is better than the alternative: well-defined, rigid data structures described at compile time. (Yes, folks, I like LISP too -- conses are your friends. :-) What irritates me is that these "implicit" structures imposes an extra documentation burden, and one that's not always easily satisfied in code. Rob Pike claims that it's better to put the complexity in the data than the code, and I agree, but that doesn't help you if the data is undecipherable.

Update: Another possible disadvantage of Perlish (or LISPy, HaskellicSchemeing, etfc) "implicit, on the fly" data structures is that some compiler optimizations are difficult or even impossible. NOTE: I haven't actually tested these assumptions empirically; for one thing, I'm at work, and don't have the time. I'm going on my understanding of modern computer architecture and compiler optimization, which may be sorely lacking. Thou hast been warned.

For instance, if I want a 3d vector, I could write the following C:

typedef struct {
  float x;
  float y;
  float z;
} vec3d;
[download]

Now, the compiler knows that a vec3d takes up exactly 12 bytes (assuming 4-byte floats), and can make a bunch of optimizations based on that knowledge and some information about the processor it's compiling for. For instance, it can pad the struct out to 16 bytes if addressing is faster on 16-byte boundaries. It can take a declaration like:

vec3d vertices[20];
[download]

and allocate 240 (or 320) contiguous bytes for it.

Contrast that to the implicit equivalent:

my %vert = (
  'x' => undef, # placeholder
  'y' => undef,
  'z' => undef,
);
[download]

Perl knows nothing about the size of this hash: it has three elements now, but there's nothing stopping you from adding a dozen more in the very next statement. And since the size of the hash isn't guaranteed, the best Perl can do if you put twenty vertices in an array is allocate twenty contiguous references: that's better than nothing, but unless you're improbably lucky careful in your memory management, the hashes those refs point to are going to be scattered all over memory, which means cache misses and subsequent stalls.

The Perlish alternative is to create data structures in scalars with pack, which is just fugly.

The "Perl is slower than C!" thesis shouldn't be any surprise to anyone, of course. I just want to point out that the flexibility of hashed (hashish? ;-) structures is sometimes a disadvantage. Again, I want to emphasize that I tend to like this way better, but I'd be a fool to pretend that it's perfect.

Update 2: Minor grammar corrections.

Update 3: I'm not picking on Common LISP in particular, just the "add stuff on the fly" way of building complex structures, which you can do in Common LISP (or any other LISP, for that matter), and in my experience is the most common way of building structures.

A good general rule for finding language features in Common LISP is "it's in there somewhere". :-)

--
The hell with paco, vote for Erudil!
:wq

Common Lisp has had those kind of optimizations for ages. You tell it what your variables hold, and how much effort it should spend compiling for speed, and it figures out the rest. The only catch is that it still does garbage collection.

For a real example of Common Lisp used in a high-performance situation, read this description of how Orbitz works.

I agree pretty much totaly. ("Never say never".)

This is going to be one of the nice things about perl6 -- you can nicely mix both styles, and declare a hash with limited namespace, each entry of which has a specific type, and thus get somthing like a C struct with known size and thus more optimizable.

You can also have limited namespace but not declare the types of the entries strictly. Or pretty well anything else you can think of.

Because the parrot virtual machine resembles a real machine, we can pull on all the experince with compiler optimization to real (register) machines.

---

We are using here a powerful strategy of synthesis: wishful thinking. -- The Wizard Book

One of the key places this problem is really a problem is in the internal data structure of objects. Of course an object can be a blessed just-about-anything, but most people use a hash, and store the object state in there.

In Perl 5 you have 'fields' which can help clean up the problem. I also really like the way accessors are handled in the reformed-perl OO syntax module: (my writeup, authors writeup).