### N-Dimensional Arrays on the fly

by qumsieh (Scribe)
 on Aug 19, 2004 at 23:44 UTC Need Help??
qumsieh has asked for the wisdom of the Perl Monks concerning the following question:

Hi,

I'm writing up a class that needs to create a multi-dimensional array on the fly. The dimension is specified through an argument to the new() method.

Needless to say, I'm looking for an elegant and efficient implementation.

The only way I can think of is to create a string of Perl code on the fly, and eval() it. Something like this:

```my \$dim  = 3;
my @size = (4, 5, 6);
my \$var  = 'a';
my \$str  = '';

for my \$i (0 .. \$dim - 1) {
\$str .= '  ' x \$i .
"for my \\$\$var (0 .. \$size[\$i] - 1) {\n";
\$var++;
}

\$var = 'a';
\$str .= '  ' x \$dim . '\$array' .
join '' => map {'[\$ ' . \$var++ . ']'} 1 .. \$dim;
\$str .= " = 0;\n";

\$str .= "  " x (\$dim - \$_) . "}\n" for 1 .. \$dim;
This results in \$str holding:
```for my \$a (0 .. 4 - 1) {
for my \$b (0 .. 5 - 1) {
for my \$c (0 .. 6 - 1) {
\$array[\$ a][\$ b][\$ c] = 0;
}
}
}
This solution strikes me as rather elegant, but somewhat inefficient, but I can live with that since I need to eval this only once. Now, my main concern is how I would set individual elements (through a call to another method).

I could only think of the same approach: Create a sub on the fly that can be called with the proper arguments. Something like:

```  my \$i = 0;
my \$sub = 'sub { \$array' .
join '' => map {'[\$_[' . \$i++ . ']]'} 1 .. \$dim;
\$sub .= ' = \$_[-1] }' . "\n";
Now \$sub looks like this:
```sub { \$array[\$_[0]][\$_[1]][\$_[2]] = \$_[-1] }
which I can eval and then call anonymously with the coordinates and the desired value. But, I will need to call this sub a huge number of times and hence think it will be rather inefficient.

Is there a better way?
Thanks,
--Ala

Replies are listed 'Best First'.
Re: N-Dimensional Arrays on the fly
by BrowserUk (Pope) on Aug 20, 2004 at 01:41 UTC
```#! perl -slw
use strict;
use Data::Dumper;

sub new {
return [ ( 0 ) x shift ] if @_ == 1;
return [ map { new( @_ ) } 1 .. shift ];
}

sub deref {
return \$_[ 0 ] = \$_[ 1 ] if @_ == 2;
return deref( shift()->[ shift ], @_ );
}

my \$aref = new( 3, 4, 5 );

deref \$aref, 0, 0, 0, 'This is element [0,0,0]';
deref \$aref, 2, 3, 4, 'This is element [2,3,4]';

print Dumper \$aref;

__END__
\$VAR1 = [
[
[ 'This is element [0,0,0]', 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ]
],
[
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ]
],
[
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 'This is element [2,3,4]' ]
]
];

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
Ahh .. that looks good. Thanks. From past experience, I tend to avoid recursion as much as possible since it is usually slower than the more direct approach. I guess that in this case, recursion is the most natural representation. I'll try to benchmark it and see.

Thanks again.

When dealing with trees, it's hard to avoid recursion. And this really is a tree problem: Create a structure which has i0 children, each of which have i1 children, .., each of which has 'i(n-1)' children.

Normally, recursion can be avoided with AoA(oA(oA))) by hardcoding the for loops, because the list of loop counter vars acts as the stack recursion would give us. This doesn't apply in this case, because we have an arbitrary number of for loops.

You could avoid recursion in this case by creating an 1-dimentional array of loop counters as long as the input list, but it would overcomplicate the code for nothing. It would be fun to code it for hte challenge, but I'm late.

Update: deref can easily be rewritten to be non-recursive:

```sub deref {
my \$aref = shift;
\$aref = \$aref->[shift] while (@_ > 2);
return \$aref->[\$_[0]] = \$_[1];
}
Re: N-Dimensional Arrays on the fly
by blokhead (Monsignor) on Aug 20, 2004 at 00:28 UTC
You can can accomplish that for-loop without eval using NestedLoops from tye's Algorithm::Loops. And instead of eval'ing that anonymous sub to only work with a set number of indices, you can use a function that takes an arbitrary list of indices to dereference (which answers your main question).
```use Algorithm::Loops 'NestedLoops';

## returns an alias to \$_[0]->[ \$_[1] ]...[ \$_[-1] ]
sub deref_many : lvalue {
my \$ptr = \shift;
\$ptr = \\$\$ptr->[\$_] for @_;
\$\$ptr;
}

my @array;
my @size = (4, 5, 6);

NestedLoops(
[ map [0 .. \$_-1], @size ],
sub { deref_many(\@array, @_) = rand }
);
The lvalue sub might be a tad too cutesy, but I think its usage at the bottom reads fairly well (since you want to use \$a[x][x]..[x] as an lvalue)

While all of this might be cleaner, and it avoids eval, I would imagine that your initial eval solution is going to be fastest, since it doesn't involve any function call overhead.

Re: N-Dimensional Arrays on the fly
by Zaxo (Archbishop) on Aug 20, 2004 at 01:45 UTC

Your three-deep loop could be written,

```my @array = (undef) x \$size[0];
\$_ = [ map { [(0) x \$size[2]] } (undef) x \$size[1] ] for @array;
Inside the map block is what happens in your deepest loop level. That is a reference to an array of \$size[2] zeros. The list map acts on is bogus. Any list of \$size[1] items would do there because the data in that list is never touched or remembered. It's only there to make \$size[1] different copies of the inner array. A reference is taken to the whole map expression to make the top level data in @array.

Setting 3d array elements is easier than you think. Just say,

```\$array[\$foo][\$bar][\$baz] = \$quux
if \$foo >= -\$size[0] and \$foo < \$size[0]
and \$bar >= -\$size[1] and \$bar < \$size[1]
and \$baz >= -\$size[2] and \$baz < \$size[2];
If you don't care about checking index range, all that logic can go.

blokhead's lvalue sub for fetch and store is an elegant approach.

After Compline,
Zaxo

The depth of 3 was only an example. In reality it could be anything.
Re: N-Dimensional Arrays on the fly
by Prior Nacre V (Hermit) on Aug 20, 2004 at 20:50 UTC

Here's a solution with neither eval nor recursion. In terms of efficiency, for a total of N elements created, this requires between 1N and 1.5N passes (best & worst cases I got with a fair number of tests).

Update

Minor code change - runs a bit faster.

Regards,

PN5

Create A New User
Node Status?
node history
Node Type: perlquestion [id://384495]
Front-paged by broquaint
help
Chatterbox?
 [erix]: but I guess there's no stopping the herd [1nickt]: Thank you haukex and hippo. I'm thinking of using IPC::System:: Simple::capture instead. But will go reread Hauke's treatise first :-) [1nickt]: herveus is so weird. Love his reply in that SQLite thread! Much more effective warning system to have diverse monks debunk on technical merits... [haukex]: IPC::System:: Simple does all the \$? handling for you, and does it well [erix]: weird problem btw (that SQLite question) - I asked astroboy to let us know if he finds the cause [hippo]: The syntax is warning enough to me.

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (9)
As of 2017-12-13 11:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What programming language do you hate the most?

Results (360 votes). Check out past polls.

Notices?