Re: Returning the lowest key in a hash (or highest)

Says indigo:

Sort takes O(n log n). Simply walking the keys of the hash is only O(n).

A lot of people made this point, but I wonder if it's really as important as people think. sort() is written in C and is very fast. Walking the keys requires that a lot of Perl opcodes must be dispatched, so it is probably a lot slower. Yes, the times are O(n log n) and O(n), but that ignores the constant factors, and I would expect the constant factor for the sort to be much smaller, so that the sort would be faster except for extremely large hashes.

Maybe someone who likes benchmarking can look into this and post the results.

Comment on Re: Returning the lowest key in a hash (or highest)

Replies are listed 'Best First'.
Benchmarking hash sort vs. walk (Was: Re: Re: Returning the lowest key in a hash (or highest)) by larryl (Monk) on Mar 26, 2001 at 01:03 UTC
Here's a benchmark I tried that compares sorting to hash-walking for hashes of various sizes, and the results confirm Dominus's expectations. The hash entries are generated using `rand(65000)` and both subs are given the same hash to work with. (I think the comparison is pretty fair, let me know if you have ideas for either of the subs!) The code: `sub walkit { my $hashref = shift; my $min = each %$hashref; $min > $_ and $min = $_ for keys %$hashref; $min; } sub sortit { my $hashref = shift; ( sort {$a<=>$b} keys %$hashref )[0]; }` [download] The results: Size sort walk 10 8329.50/s 5289.68/s (sort wins!) 100 1020.53/s 727.29/s (sort wins!) 1000 94.68/s 80.14/s (sort wins!) 10000 7.15/s 7.31/s (almost a wash...) 100000 0.52/s 0.73/s (walking wins!)	[reply] [d/l] [select]

Replies are listed 'Best First'.

Benchmarking hash sort vs. walk (Was: Re: Re: Returning the lowest key in a hash (or highest))
by larryl (Monk) on Mar 26, 2001 at 01:03 UTC

Here's a benchmark I tried that compares sorting to hash-walking for hashes of various sizes, and the results confirm Dominus's expectations. The hash entries are generated using rand(65000) and both subs are given the same hash to work with. (I think the comparison is pretty fair, let me know if you have ideas for either of the subs!)

The code:

sub walkit {
   my $hashref = shift;
   my $min = each %$hashref;
   $min > $_ and $min = $_ for keys %$hashref;
   $min;
}

sub sortit {
   my $hashref = shift;
   ( sort {$a<=>$b} keys %$hashref )[0];
}
[download]

The results:

Size       sort       walk
10      8329.50/s  5289.68/s  (sort wins!)
100     1020.53/s   727.29/s  (sort wins!)
1000      94.68/s    80.14/s  (sort wins!)
10000      7.15/s     7.31/s  (almost a wash...)
100000     0.52/s     0.73/s  (walking wins!)

[reply]
[d/l]
[select]