perl快速排序

Question

在perl中有没有一种快速排序的方法？就像我有一个非常大的散列，可能有一亿个键。当我测试的时候，做foreach my $x (sort {$a cmp $b} keys %myhash){DO SOMETHING}是非常低效的。我想知道是否可以先将所有键复制到一个数组中，然后对其进行快速排序。

Answer 1

您不希望将散列放在列表上下文中，因为您不希望使用键对值进行排序。取而代之的是，您想要对键进行排序：

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

但是，如果您想以这种方式处理这些值，您可以这样做：

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

这使用了"hash slice"。

但在这种方式下，您可以执行以下操作：

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

Answer 2

假设对100个字符串进行排序需要10μs (10百万分之一秒)。你会认为这很快吗？可能吧。这大致就是我的机器所做的。

如果是这样的话，对于100,000,000个字符串，你应该考虑41s的速度！

这就是为什么。

您不是在对100个字符串进行排序；而是在对超过1,000,000倍的字符串进行排序。但是排序不是线性的。最好的排序算法是O(N log N)。假设这是紧密联系在一起的，这意味着

• 对100个字符串进行排序需要$overhead + 100 * log2(100) * $time_per_operation。
• 对100,000,000个键进行排序需要$overhead + 1,000,000 * log2(1,000,000) * $time_per_operation。

假设可以忽略不计，这意味着对100,000,000个字符串进行排序所需的时间是对100个字符串进行排序的4,100,000倍。

因此，如果您认为100个字符串的速度为10μ，那么您应该考虑100,000,000个字符串的速度为41秒。

你得到的是什么样的数字？