lookup times for a hash are O(1) and for an array O(N).
That's ridiculous. If values are going to be indexed by integers anyway, then if anything, it takes a bit longer to look
up a key in a hash than looking it up as an array index.
Maybe you're thinking of looking up things in a linked list, ala LISP?
Or if you're strictly searching for a value without a key then
they're both O(n).
Update: Re: your reply: I figured that
was probably what you were talking about, but the original
poster seemed to want to index things by integers, and was just
wondering whether to use a hash or an regular array, and
the issues with doing one or the other. And I've actually
seen code like the below in perl programs which made me
want to whack the programmer over the head with a hash
array :) | [reply] [Watch: Dir/Any] |
If values are going to be indexed by integers anyway, then if anything, it takes a bit longer to look up a key in a hash than looking it up as an array index.
Maybe we are using our terms differently. I dont mean a fetch on a known element, but a search for a given element, such as an existance test. I mean that if I need to do an existance test for a value I can do it much more efficiently in a Hash where the value IS the key, than I can in an Array, or for that matter with many other data structures due to the optimizations available to a hash being implemented in c.
Heh I just checked your homenode, and I suppose you know the below, but still you might find it interesting. while() and for(;;) seem to perform quite badly.
Both array an hash index operations are O(1) -- taking a fixed amount of time regardless of the number of elements in the hash (with rare pathological exceptions for hashes).
-- Orwant, Heitaniemi & Macdonald in Algorithms With Perl (1st ed, pp 159, para 1)
... it is possible to guarantee O(1) maximum time per access, with O(1) average amortized time per insertion and deletion regardless of the keys being examined; ... -- Knuth in Art of Computer Programming Vol.3 (2nd ed xiv, pp 549 para 1)
For an unsorted array you are limited to a sequential search (or its derivatives if you dont care at all about the order of the elements) which is O(N) in worst case for all of them (the derivates improve success times).
If you have a sorted list you can improve things by using using a binary search O(log2(n)) or if the data is well distributed and relatively unique, proportional binary search which gets a bit better except in pathological cases.
Anyway. I threw together the following benchmark. I hope you find it interesting.
Note
The data was a shuffled list of numbers from 1..1000
Im not really too sure about the distributions here. I tried to pick some that seemed interesting. I'll post the entire code I used to do the benchmark later. Any suggestions are welcome. Oh yeah I chopped the charts so they would fit on the display. Sorry.
Yves
our $i;
our $tmp;
our $Max;
our ($List,$Test)=maketest(1000);
our %Hash=map {$_,1} @$List;
#######################
# Test Code For qssqrt
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
my $ret="";
# from Knuth Art of Computer Programming Vol 3
# Section 6.1 Program Q With swap code added
# Tail Sentinal if NOT being deleted ($array[$Max])
$i=0;
$array[$Max]=$value;
$i++ while($value ne $array[$i]);
if ($i<$Max) {
if ($i>0) {
$ret=int(sqrt($i));
$tmp=$array[$ret];
$array[$ret]=$array[$i];
$array[$i]=$tmp;
} else {
$ret=$i;
}
}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : ""
+)."\n" ;
}}
#######################
# Test Code For qsrand
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
my $ret="";
# from Knuth Art of Computer Programming Vol 3
# Section 6.1 Program Q With swap code added
# Tail Sentinal if NOT being deleted ($array[$Max])
$i=0;
$array[$Max]=$value;
$i++ while($value ne $array[$i]);
if ($i<$Max) {
if ($i>0) {
$ret=int(rand($i));
$tmp=$array[$ret];
$array[$ret]=$array[$i];
$array[$i]=$tmp;
} else {
$ret=$i;
}
}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : ""
+)."\n" ;
}}
#######################
# Test Code For quick
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
my $ret="";
# from Knuth Art of Computer Programming Vol 3
# Section 6.1 Program Q
# Tail Sentinal if NOT being deleted ($array[$Max])
$i=0;
$array[$Max]=$value;
$i++ while($value ne $array[$i]);
$ret=$i if $i<$Max;
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : ""
+)."\n" ;
}}
#######################
# Test Code For wbump
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
my $ret="";
# from Knuth Art of Computer Programming Vol 3
# Section 6.1 Program S. With swap (bump) code added
# While implementation
$i=0;
$i++ while($value ne $array[$i] && $i<$Max);
if ($i<$Max) {
if ($i>0) {
$tmp=$array[0];
$array[0]=$array[$i];
$array[$i]=$tmp;
}
$ret=0;
}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : ""
+)."\n" ;
}}
#######################
# Test Code For qbump
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
my $ret="";
# from Knuth Art of Computer Programming Vol 3
# Section 6.1 Program Q With swap (bump) code added
# Tail Sentinal if NOT being deleted ($array[$Max])
$array[$Max]=$value;
my $i=0;
$i++ while($value ne $array[$i]);
if ($i<$Max) {
if ($i>0) {
$tmp=$array[0];
$array[0]=$array[$i];
$array[$i]=$tmp;
}
$ret=0;
}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : ""
+)."\n" ;
}}
#######################
# Test Code For wswap
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
my $ret="";
# from Knuth Art of Computer Programming Vol 3
# Section 6.1 Program S. With swap code added
# While implementation
$i=0;
$i++ while($value ne $array[$i] && $i<$Max);
if ($i<$Max) {
if ($i>0) {
$ret=$i-1;
$tmp=$array[$ret];
$array[$ret]=$array[$i];
$array[$i]=$tmp;
} else {
$ret=$i;
}
}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : ""
+)."\n" ;
}}
#######################
# Test Code For foreach
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
my $ret="";
# from Knuth Art of Computer Programming Vol 3
# Section 6.1 Program S
# Foreach implementation
LOOP: foreach (@array) {
if ($value eq $_) {
$ret=$value;
last LOOP;
}
}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : ""
+)."\n" ;
}}
#######################
# Test Code For qs i-1
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
my $ret="";
# from Knuth Art of Computer Programming Vol 3
# Section 6.1 Program Q With swap code added
# Tail Sentinal if NOT being deleted ($array[$Max])
$i=0;
$array[$Max]=$value;
$i++ while($value ne $array[$i]);
if ($i<$Max) {
if ($i>0) {
$ret=$i-1;
$tmp=$array[$ret];
$array[$ret]=$array[$i];
$array[$i]=$tmp;
} else {
$ret=$i;
}
}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : ""
+)."\n" ;
}}
#######################
# Test Code For while
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
my $ret="";
# from Knuth Art of Computer Programming Vol 3
# Section 6.1 Program S
# While implementation
$i=0;
LOOP:while($i<$Max) {
if ($value eq $array[$i]) {
$ret=$i;
last LOOP;
} else {
$i++;
}
}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : ""
+)."\n" ;
}}
#######################
# Test Code For Hash
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
my $ret="";
# Simple perl hash Implementation
$ret=$value if exists($Hash{$value});
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : ""
+)."\n" ;
}}
#######################
# Test Code For for(;;)
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
my $ret="";
# from Knuth Art of Computer Programming Vol 3
# Section 6.1 Program S
# For (;;) implementation
LOOP: for ($i=0;$i<$Max;$i++) {
if ($value eq $array[$i]) {
$ret=$i;
last LOOP;
}
}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : ""
+)."\n" ;
}}
#######################
# Test Code For forI
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
my $ret="";
# from Knuth Art of Computer Programming Vol 3
# Section 6.1 Program S
# For (0..n) implementation
LOOP: for $i (0..$Max-1) {
if ($value eq $array[$i]) {
$ret=$i;
last LOOP;
}
}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : ""
+)."\n" ;
}}
#######################
# Test Code For qs i/2
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
my $ret="";
# from Knuth Art of Computer Programming Vol 3
# Section 6.1 Program Q With swap code added
# Tail Sentinal if NOT being deleted ($array[$Max])
$i=0;
$array[$Max]=$value;
$i++ while($value ne $array[$i]);
if ($i<$Max) {
if ($i>0) {
$ret=int($i/2);
$tmp=$array[$ret];
$array[$ret]=$array[$i];
$array[$i]=$tmp;
} else {
$ret=$i;
}
}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : ""
+)."\n" ;
}}
----------------
Testing 0 gaussian(($i-($total_elems/2))/10,0,.5)*100,
Rate while for(;;) wbump wswap forI qbump quick
while 1.07/s -- -3% -29% -34% -49% -53% -55%
for(;;) 1.11/s 3% -- -27% -32% -47% -52% -53%
wbump 1.51/s 41% 36% -- -7% -28% -34% -36%
wswap 1.62/s 51% 47% 8% -- -22% -29% -31%
forI 2.08/s 94% 88% 38% 28% -- -9% -12%
qbump 2.28/s 113% 106% 51% 41% 10% -- -3%
quick 2.36/s 120% 113% 56% 45% 13% 3% --
qs i-1 2.50/s 133% 126% 66% 54% 20% 10% 6%
foreach 2.67/s 149% 141% 77% 64% 28% 17% 13%
qssqrt 5.08/s 374% 359% 237% 213% 144% 123% 115%
qs i/2 15.3/s 1328% 1285% 915% 843% 635% 571% 549%
qsrand 16.3/s 1419% 1373% 980% 903% 682% 614% 590%
Hash 261/s 24295% 23550% 17244% 16010% 12454% 11363% 10983%
----------------
Testing 1 exponential(($i+1)/$total_elems*20,1)*100,
Rate while for(;;) wbump wswap forI qbump quick
while 1.07/s -- -2% -31% -32% -48% -55% -55%
for(;;) 1.09/s 2% -- -30% -31% -47% -54% -54%
wbump 1.55/s 45% 42% -- -1% -25% -34% -35%
wswap 1.57/s 47% 44% 1% -- -24% -33% -34%
forI 2.07/s 93% 90% 33% 31% -- -12% -13%
qbump 2.36/s 120% 116% 52% 50% 14% -- -1%
quick 2.39/s 123% 119% 54% 52% 15% 1% --
qs i-1 2.40/s 124% 120% 55% 53% 16% 2% 1%
foreach 2.64/s 146% 143% 70% 68% 28% 12% 11%
qssqrt 3.06/s 185% 180% 97% 94% 48% 30% 28%
qsrand 5.59/s 421% 413% 260% 255% 170% 137% 134%
qs i/2 5.79/s 440% 432% 273% 268% 180% 146% 143%
Hash 255/s 23634% 23261% 16295% 16071% 12197% 10693% 10555%
----------------
Testing 2 (1/($i+1)*$total_elems)**2,
Rate while for(;;) forI quick wbump foreach wswap
while 1.12/s -- -3% -48% -55% -57% -58% -60%
for(;;) 1.15/s 3% -- -46% -54% -56% -57% -58%
forI 2.15/s 92% 87% -- -14% -17% -19% -22%
quick 2.51/s 124% 118% 17% -- -3% -5% -9%
wbump 2.59/s 131% 125% 21% 3% -- -3% -7%
foreach 2.66/s 137% 131% 24% 6% 3% -- -4%
wswap 2.77/s 147% 141% 29% 10% 7% 4% --
qbump 3.73/s 233% 224% 74% 48% 44% 40% 35%
qs i-1 4.18/s 274% 263% 95% 67% 62% 57% 51%
qssqrt 18.2/s 1530% 1484% 749% 626% 604% 586% 559%
qsrand 29.6/s 2542% 2468% 1276% 1077% 1042% 1013% 968%
qs i/2 30.9/s 2658% 2581% 1337% 1129% 1092% 1062% 1015%
Hash 260/s 23127% 22475% 12001% 10249% 9939% 9683% 9286%
----------------
Testing 3 (($i-$total_elems)/$total_elems+1)**2
Rate while for(;;) wswap wbump forI qssqrt qs i/2
while 1.05/s -- -3% -32% -32% -48% -55% -55%
for(;;) 1.09/s 3% -- -29% -29% -47% -53% -53%
wswap 1.53/s 46% 41% -- 0% -25% -34% -34%
wbump 1.53/s 46% 41% 0% -- -25% -34% -34%
forI 2.04/s 94% 88% 33% 33% -- -12% -12%
qssqrt 2.32/s 120% 114% 51% 51% 14% -- -0%
qs i/2 2.32/s 121% 114% 51% 51% 14% 0% --
qs i-1 2.33/s 122% 115% 52% 52% 14% 0% 0%
qbump 2.35/s 123% 116% 53% 53% 15% 1% 1%
qsrand 2.37/s 125% 118% 54% 54% 16% 2% 2%
quick 2.38/s 126% 119% 55% 55% 17% 2% 2%
foreach 2.61/s 148% 140% 70% 70% 28% 13% 12%
Hash 242/s 22951% 22224% 15687% 15687% 11801% 10354% 10324%
----------------
Testing 4 rand($total_elems)
Rate while for(;;) wbump wswap forI qsrand qs i/2
while 1.02/s -- -3% -30% -32% -48% -51% -52%
for(;;) 1.06/s 3% -- -28% -30% -47% -49% -50%
wbump 1.47/s 44% 40% -- -2% -26% -29% -30%
wswap 1.50/s 46% 42% 2% -- -25% -28% -29%
forI 1.99/s 94% 88% 35% 33% -- -4% -6%
qsrand 2.07/s 102% 96% 41% 38% 4% -- -2%
qs i/2 2.12/s 107% 101% 44% 41% 7% 2% --
qssqrt 2.25/s 120% 113% 53% 50% 13% 9% 6%
qbump 2.26/s 120% 114% 53% 51% 14% 9% 6%
qs i-1 2.29/s 124% 117% 55% 53% 15% 11% 8%
quick 2.31/s 126% 119% 57% 54% 16% 12% 9%
foreach 2.55/s 149% 142% 73% 70% 28% 23% 20%
Hash 245/s 23796% 23083% 16509% 16223% 12210% 11717% 11447%
| [reply] [Watch: Dir/Any] [d/l] |