CODEWITHSUNDEEP
perlsorting
lolibility
lolibility

Reputation: 2187

perl quick sort

Is there a way to do very quick sort in perl? Like I have a very large hash, probably with 100 million keys there. It is very inefficient to do foreach my $x (sort {$a cmp $b} keys %myhash){DO SOMETHING} when I test. Wondering if I can first copy out all keys to a array and use a quick sort to it.

Upvotes: 0

Views: 393

Answers (2)

ikegami
ikegami

Reputation: 386676

Say sorting 100 strings takes 10μs (10 millionth of a second). Would you consider that fast? Probably. That's roughly what my machine does.

If so, you should consider 41s fast for 100,000,000 strings!

Here's why.

You're not sorting 100 strings; you're sorting 1,000,000 times more string. But sorting isn't linear. The best sorting algorithms are O(N log N). Assuming that's tightly bound, that means

  • Sorting 100 strings is going to take $overhead + 100 * log2(100) * $time_per_operation.

  • Sorting 100,000,000 keys is going to take $overhead + 1,000,000 * log2(1,000,000) * $time_per_operation.

Assuming negligible overheard, that means sorting 100,000,000 strings will take 4,100,000 times longer than sorting 100 strings.

So if you consider 10μs fast for 100 strings, you should consider 41s fast for 100,000,000 strings.

What kind of numbers are you getting?

Upvotes: 3

Axeman
Axeman

Reputation: 29854

You wouldn't want to put the hash in a list context, because you do not want the values sorted with the keys. Instead, yes you want to sort the keys: 

my @ordered_keys = sort { $a cmp $b } keys %hash;

However, if you wanted to deal with the values in that way, you could do this:

my @ordered_values = @hash{ sort { $a cmp $b } keys %hash };

This uses a "hash slice".

But in this fashion, you could do the following: 

foreach my $value ( @hash{ sort { $a cmp $b } keys %hash } ) { 
    # key? What key?
    do_something_with_hash_value( $value );
}

Upvotes: 3

Related Questions