perl - perl 快速排序

Question

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

score 3 · Accepted Answer

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

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

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

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

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

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

score 3 · Accepted Answer

假设对 100 个字符串进行排序需要 10μs（百万分之一秒）。你会考虑这么快吗？大概。这大致就是我的机器所做的。

如果是这样，您应该考虑 100,000,000 个字符串的 41 秒快！

这就是为什么。

您没有对 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μs 快，那么您应该考虑 100,000,000 个字符串的 41s 快。

你得到什么样的数字？

2 回答 2