perl快速排序

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

来源

2012-10-18 lolibility

你想做什么？ '排序{$ a cmp $ b}％myhash'会尝试对你的散列的键和值进行排序，我确定这不是你想要做的。 –

一个散列中的1亿个键（在内存中）听起来像你应该考虑别的东西而不是Perl。数据库？ – TLP

@j_random_hacker，是的，这是一个错字，我的意思是排序{$ a cmp $ b}键％myhash – lolibility

您不希望将散列放在列表上下文中，因为您不希望按键排序值。相反，是要的按键排序：

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); 
}

来源

2012-10-18 18:53:16 Axeman

说分拣100个字符串需要为10μs（10万分之一秒的）。你会认为那么快吗？大概。这大致就是我的机器所做的。

如果是这样，你应该考虑41万快速为100,000,000字符串！

这是为什么。

你没有排序100个字符串;你正在分拣1,000,000次以上的字符串。但排序不是线性的。最好的排序算法是O（N log N）。假设这是紧密绑定，这意味着

排序100个字符串将花费$开销+ 100 * log2（100）* $ time_per_operation。
排序100,000,000个键将花费$开销+ 1,000,000 * log2（1,000,000）* $ time_per_operation。

假设可以忽略不计的偷听，这意味着排序100,000,000个字符串将比排序100个字符串长410万次。

所以如果你考虑100个字符串的快速度为10μs，那么你应该考虑对于100,000,000个字符串的41s快。

你得到了什么样的数字？

来源

2012-10-18 19:58:36 ikegami

回答

相关问题