Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Re: Re: Array vs. Hash (newbie perlguts)

by demerphq (Chancellor)
on Sep 01, 2001 at 05:49 UTC ( [id://109594]=note: print w/replies, xml ) Need Help??


in reply to Re: Array vs. Hash (newbie perlguts)
in thread Array vs. Hash (newbie perlguts)

While the OP did say optimize memory, lookup times for a hash are O(1) and for an array O(N).
The choice is really 1 of fast fetch versu slows fetch,slow lookup vs fast lookup,small footprint verus large.

Yves

Update
That should read O(f(N)) where f(n) changes depending on additional factors about the data in the array, such as if its sorted etc.
Sorry.

Replies are listed 'Best First'.
Re: Re: Re: Array vs. Hash (newbie perlguts)
by runrig (Abbot) on Sep 01, 2001 at 09:54 UTC
    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 :)

      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%

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://109594]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others musing on the Monastery: (5)
As of 2024-03-19 09:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found