Re^2: Sorting a hash of arrays based on a particular array element.

Replies are listed 'Best First'.
Re^3: Sorting a hash of arrays based on a particular array element. by Random_Walk (Prior) on Jul 28, 2005 at 08:39 UTC
Wow, most impressive. How do you do the sorting under the covers, can you point me to some online resources ? As it is so much faster than perl's sort will it ever make it into core and replace the current sort or does it gain speed by having different interfaces for sorting different data types ? Cheers, R. Pereant, qui ante nos nostra dixerunt!	[reply]
Re^4: Sorting a hash of arrays based on a particular array element. by salva (Canon) on Jul 28, 2005 at 10:10 UTC
well, actually Sort::Key uses the internal perl sort function under the hood. It just exposes a different API that can cover most sorting usages without incurring in an extra cost as core sort does. The algorithm used is similar to... `sub sortkey { my ($func, @v); my @keys = map { &$func } @v; my @ix = sort { $keys[$a] cmp $keys[$b] } 0..$#keys; return @v[@ix] }` [download] but being implemented in C (specially, the comparing callbacks) it doesn't require the nasty hacks of the GRT to do the sort part efficiently.	[reply] [d/l]
Re^3: Sorting a hash of arrays based on a particular array element. by Random_Walk (Prior) on Jul 28, 2005 at 12:28 UTC
Oh silly silly me ... 2 million values thrown into a hash with only 100 possible keys !!! # for (1..$elements) { # my ($key, $one, $two) = rand =~/(\d\.\d{2})(\d{2})(\d{4})/; # $hash{$key} = [$one, $two]; #} for (1..$elements) { my ($one, $two) = rand =~/\d+.(\d{6})(\d{4})/; $hash{$_} = [$one, $two]; } # Also reduced $elements to 200_000 and 2 million # exceeded per proc memeory limit. # I also use more entropy in the field to sort on # requiring a change of packed_default to ... sub packed_default { my @sorted_keys = map substr($_,4), sort map {pack('N', $hash{$_}[0])."$_"} keys %hash; return @sorted_keys; } Benchmark: timing 10 iterations of BroweserUK, packed_default... BroweserUK: 188 wallclock secs (175.63 usr + 0.13 sys = 175.76 CPU) @ 0.06/s (n=10) packed_default: 72 wallclock secs (64.61 usr + 0.16 sys = 64.77 CPU) @ 0.15/s (n=10) [download] Sadly I am on a company machine with a restrictive policy about installing modules so I can not test Sort::Key here, will give it a bash at home this evening. Cheers, R. Pereant, qui ante nos nostra dixerunt!	[reply] [d/l]
Re^4: Sorting a hash of arrays based on a particular array element. by salva (Canon) on Jul 28, 2005 at 13:57 UTC
on my computer (for 1M elements): `s/iter BrowserUK packed_default SortKey BrowserUK 71.7 -- -66% -79% packed_default 24.5 193% -- -38% SortKey 15.2 372% 61% --` [download] another important point for sorting algorithms is their memory comsumption, and the GRT offers the worst behaviour for that aspect: `use Memchmark qw(cmpthese); ... cmpthese(BrowserUK => \&BrowserUK, packed_default => \&packed_default, SortKey => \&SortKey ); __end__ test: BrowserUK, memory used: 102006784 bytes test: SortKey, memory used: 85598208 bytes test: packed_default, memory used: 182788096 bytes` [download] (Memchmark results are approximate, but accurate enough to show the difference)	[reply] [d/l] [select]