From: Charles Hixson Date: 2003-11-20T06:00:03+09:00 Subject: Re: Multi-dimensioned sparse array ? Simon Strandgaard wrote: >>>On Wed, 19 Nov 2003 14:21:19 +0900, Charles Hixson wrote: >>> >>> >>> >>> >>>>Does anyone have an implementation of a multi-dimensioned sparse >>>>array? >>>> >>>> >>>> >[snip] > > >>numerous times. Ugh! The list mesh looks faster, even though it >>absorbe 2*n+1 units of memory for each cell used (two pointers for each >>dimension.), and is itself quite slow. >> >> > >I am curious to how many dimension you need? 3, 7, 50 ? > >Which kind of algorithm are you implementing? > >-- >Simon Strandgaard > It's actually basically a lookup algorithm at this point, but I'd rather not be too specialized. If you want a simple visual idea, imagine that you're representing the pieces on a chess board. One representation could have columns, rows, and move-number, such that if you knew the column, row, and move number you could quickly determine which (if any) piece was on that square. I'm actually considering many more than eight rows & columns, and more than 200 moves, and perhaps there'll be a third (unknown as yet) dimension. Like, perhaps, in a game of Angband. I realize that none of these examples are done quite this way, for rather obvious reasons. One would clearly need to pack the representation tightly for storage...but that's no big problem, as when it's being stored one doesn't need to move between rows & columns. The packing and unpacking operations can afford to be relatively slow. The end goal of the structure is to be included in an AI program which I haven't yet designed, much less built. But I'm looking for useful pieces that I can build before starting. E.g. I know that I'll need a B+Tree. And I suspect that I'll need the data structure to have multiple indexes, so a simple B+Tree approach won't work. (This is nearly unrelated to the multi-dimensioned sparse array.) Anyway, I don't know how many dimensions I'll need, but probably no more than four large ones (where large means to big to be a reasonable enumeration in C). If this approach proves too difficult, I'll probably settle for using a packed representation, with reasoning being done using an unpacked fixed size array (perhaps 500 X 500 x 10 or 100 X 100 X 100 X 10) that I might call the foeva, but as you can see it would quickly get too large to be useful. Another approach would be to do all of the detail work in, say, D (Digital Mars D), a language that is in many ways similar to Ruby, but is an expansion from C that differs from either C++ or Objective C. (Objective C is another possibility, but I've never learned it even as well as I've learned D -- which is still being written.)