Re: What defines the choice of a Hash or an Array?

I think that the name of the perl data types: ARRAY and HASH are confusing this issue. It is important not to confuse these data types with the data structures with simular names. Both perl data types can be used to create arrays:

$ARRAY->[1][2] = 'bob';
$HASH->{1}{2} = 'bob';

As this table shows about the only thing you can use a HASH data type for directly is as an array.

data type ARRAY HASH
array X X
list X

iterator X

stack X

queue X

So should you use and HASH or an ARRAY to store arrays? Accessing the ARRAY data type is only slightly faster than accessing the HASH data type, so I would recomend using HASH arrays except for rare cases were speed is vital. If you your arrays are more more 1 dimentional then the ARRAY data type really looses all of its advantage over the HASH data type, as it can no longer be used directly as a list.

         Rate  HASH ARRAY
HASH  54856/s    --   -5%
ARRAY 57536/s    5%    --

And of course every thing else is in an ARRAY (or a SCALAR).

use Benchmark qw (cmpthese);

use constant {
   SEC   => 0,
   MIN   => 1,
   HOUR  => 2,
   MDAY  => 3,
   MON   => 4,
   YEAR  => 5,
   WDAY  => 6,
   YDAY  => 7,
   ISDST => 8,
};

our $array = [ qw (sec min hour mday mon year wday yday isdst ) ];
our $hash  = { qw (SEC sec MIN min HOUR hour MDAY mday MON mon
                    YEAR year WDAY wday YDAY yday ISDST isdst ) };

sub array {
    my $a;
    $a |= $array->[SEC];
    $a |= $array->[MIN];
    $a |= $array->[HOUR];
    $a |= $array->[MDAY];
    $a |= $array->[MON];
    $a |= $array->[YEAR];
    $a |= $array->[WDAY];
    $a |= $array->[YDAY];
    $a |= $array->[ISDST];
    $a;
}

sub hash {
    my $a;
    $a |= $hash->{'SEC'};
    $a |= $hash->{'MIN'};
    $a |= $hash->{'HOUR'};
    $a |= $hash->{'MDAY'};
    $a |= $hash->{'MON'};
    $a |= $hash->{'YEAR'};
    $a |= $hash->{'WDAY'};
    $a |= $hash->{'YDAY'};
    $a |= $hash->{'ISDST'};
    $a;
}

cmpthese(-1, 
{
   'ARRAY' => \&array,
   'HASH' => \&hash,
});

cmpthese(-1,
{
   'ARRAY' => sub { sort @$array },
   'HASH' => sub { sort values %$hash },
});
[download]

-- gam3
A picture is worth a thousand words, but takes 200K.

Comment on Re: What defines the choice of a Hash or an Array? Download Code

Replies are listed 'Best First'.
Re^2: What defines the choice of a Hash or an Array? by chromatic (Archbishop) on Apr 01, 2005 at 00:11 UTC
I'm not sure why you bring up the issue of storing array references in hashes versus arrays. I'm also not sure why speed is a consideration. Arrays are useful where you need ordered access, where you might use a data structure such as a stack, a queue, a dequeue, or access to a list of items by sequential indexes. Hashes are useful when you need keyed access to a list of items where near-constant access time is more important than preserving insertion order. That dubiousity aside, I think the rest of your post is confusing misinformation. I think that the name of the perl data types: ARRAY and HASH are confusing this issue. It is important not to confuse these data types with the data structures with simular names. No, this is wrong. The Perl data type has the name ARRAY because it is an array. The Perl data type has the name HASH because it is a hash. Both perl data types can be used to create arrays: `$ARRAY->[1][2] = 'bob'; $HASH->{1}{2} = 'bob';` [download] This is half wrong. The first is an array because it's an array. The second is not an array because it's a hash. Try iterating through the indexes of the hash, for example. Try using a non-integer as the index of an array. Try using a huge integer as the index of an array. Sure, if you provide a really degenerate, simplified definition of what an array is, you can emulate it with a hash, but that doesn't make it an array. If you your arrays are more more 1 dimentional then the ARRAY data type really looses all of its advantage over the HASH data type, as it can no longer be used directly as a list. I don't know what this means, but unless you're talking about the need to dereference nested arrays (which you also have to do with nested hashes), I think it's wrong too.	[reply] [d/l]
Re^3: What defines the choice of a Hash or an Array? by Anonymous Monk on Apr 01, 2005 at 08:12 UTC
No ... wait ... silly post was posted on Mar 31, but rational sane response was posted on Apr 1 - April Fool's Day. Where's the laughter if there's no joke? This is a paradox wrapped in an enigma wrapped in a conundrum! Ahhh, my ... brains!!! AAAAAAAAAAAAAAAAAHHHHHHHHHHHHHH!!!	[reply]