in reply to Re: Array or Hash
in thread Array or Hash

Both scale the same for insertions (amortised O(1))

Care to demonstrate how insertions into an array amortise to O(1)?

Both scale the same for fetches (amortised O(1)).

A fetch should take a little longer with a hash, but I suspect this wouldn't be the deciding factor in most cases.

You wouldn't notice if your programs ran 5 times slower? 

perl -MTime::HiRes=time 
-E"@a=1..1e6;$t=time; ++$a[$_] for 1..1e6; printf qq[%f\n], time()-$t"
0.146912

perl -MTime::HiRes=time 
-E"%h=map{($_)x2}1..1e6;$t=time; ++$h{$_} for 1..1e6; printf qq[%f\n],
+ time()-$t"
0.525000

[download]

Or an order of magnitude more slowly? 

perl -MTime::HiRes=time 
-E"$t=time;my @a; $a[$_]=1 for 1..1e6; printf qq[%f\n], time()-$t"
0.220181

perl -MTime::HiRes=time 
-E"$t=time;my %h; $h{$_}=1 for 1..1e6; printf qq[%f\n], time()-$t"
1.805000

[download]

Concealing reality behind grand sounding theoretical BS is all the worse as you obviously know better.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re^3: Array or Hash
by ikegami (Patriarch) on Jan 21, 2011 at 18:35 UTC

    Care to demonstrate how insertions into an array amortise to O(1)?

    Oops, that's limited to insertions at the start or end.

    Concealing reality behind grand sounding theoretical BS is all the worse as you obviously know better.

    You have it backwards. I avoided the theoretical BS, sticking to real world cases.

    You wouldn't notice if your programs ran 5 times slower?

    Some yes, some no, but what's that got to do with my comment?

    You didn't demonstrate any correlation between data structure access time and run time of my programs, much less 1:1.

    as you obviously know better.

    Enough with the lies and personal attacks.

[reply]
      Oops, that's limited to insertions at the start or end.

      Still wrong: 

      C:\test>perl -MTime::HiRes=time 
-E"$t=time; my @a; push @a, 1 for 1 .. 2**19; say (time()-$t)/2**19"
0.123739004135132

C:\test>perl -MTime::HiRes=time 
-E"$t=time; my @a; push @a, 1 for 1 .. 2**20; say (time()-$t)/2**20"
0.226538896560669

C:\test>perl -MTime::HiRes=time 
-E"$t=time; my @a; push @a, 1 for 1 .. 2**21; say (time()-$t)/2**21"
0.46043586730957

      [download]
      I avoided the theoretical BS, sticking to real world cases.

      You get worse.

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]

        Still wrong

        No, it's your test that's wrong. You're dividing the result of say() instead of the time difference.

        You get worse.

        Again, enough with the lies and personal attacks. The comment doesn't even make any sense potato.

[reply]

In Section Seekers of Perl Wisdom