1

我的文件中有 1e8 个数字，大小从 1 到 999 不等。我需要通读每个文件并保存一份报告，说明在每个文件中找到了每个数字的数量。我认为设置一个全为零的常量数组，然后使用我刚刚读取的数字作为索引递增会给我答案。执行此操作的 Perl 语法不是我所期望的。并非所有数字都一定会出现。也许散列是一种方法，但数组中可能只有几个洞。有什么帮助吗？谢谢。

4

3 回答 3

3

执行此操作的 Perl 语法不是我所期望的。

展示你的作品

并非所有数字都一定会出现。

跳过零（简单的 if 块，请参阅http://perldoc.perl.org/perlintro.html）

也许散列是一种方法，但数组中可能只有几个洞。

是的，哈希是很自然的，请参阅 perlfaq4，搜索“count”、“uniq”和“duplicate”

于 2011-11-14T02:08:20.647 回答
3

Tom Duff（Duff's Device 的创造者）：“如果你的代码太慢，你必须让它更快。如果没有更好的算法可用，你必须修剪周期。 ”

我不同意这是最适合散列的情况。当然，哈希是惯用的，它是 perlfaq4 中提到的方法，它不会浪费计数器容器中的元素。但他说的是 1 到 999 之间的 100_000_000 个整数。计数器容器中使用的元素数量是微不足道的。获得计数所需的迭代次数非常重要。100,000,000 次迭代需要很多时间。

如果我们改用数组，我们会丢弃索引为零的元素。如果所有的整数都是相同的值，我们会再扔掉 998 个元素。有这么大的事吗？另一方面，即使索引到数组和索引到散列聚合都需要 O(1) 操作，但 Big-O 表示法只说明了部分情况。其中“n”是整数总数（100,000,000），数组方法和哈希方法都是 O(n) 操作。因此，归结为哪种方法计算效率更高。尽管数组查找和哈希查找都是 O(1)，但事实证明哈希查找需要更多的周期来执行。

迭代超过 100,000,000 个整数和递增计数器需要时间。但事实证明，在散列中这样做比在数组中花费更多的时间。我知道从“常用成语”的角度来看这是亵渎神明。但这可能是一种非常特殊的情况，其中计算效率比惯用代码更重要，并且比使用数组作为计数器的内存占用量稍大一点更重要。

这是一些代码，演示了我在说什么：

use strict;
use warnings;
use Benchmark  qw/ cmpthese /;
use List::Util qw/ max min  /;
use Test::More;
use Readonly;



Readonly my $datasize => 100_000_000;

Readonly my $test_size => 100_000;

my @array_results = keys count_in_array( $test_size );
my @hash_results  = keys count_in_hash(  $test_size );

is( max( @array_results ), 999, "max( keys count_in_array() ) in range." );
is( min( @array_results ),   1, "min( keys count_in_array() ) in range." );
is( max( @hash_results  ), 999, "max( keys  count_in_hash() ) in range." );
is( min( @hash_results  ),   1, "min( keys  count_in_hash() ) in range." );
done_testing();    



cmpthese( 5, {
    array => sub{ my $results = count_in_array() },
    hash  => sub{ my $results = count_in_hash()  },
} );




sub count_in_array {
    my @container;
    for( 1 .. $datasize ) {
        $container[ int( rand( 999 ) ) + 1 ]++;
    }
    return {
        map{ 
                $container[$_] > 0 
                    ? ( $_ => $container[$_] ) 
                    : () 
        } 1 .. $#container
    };
}



sub count_in_hash {
    my %container;
    for( 1 .. $datasize ) {
        $container{ int( rand ( 999 ) ) + 1 }++;
    }
    return \%container;
}

以下是该基准的结果：

ok 1 - max( keys count_in_array() ) in range.
ok 2 - min( keys count_in_array() ) in range.
ok 3 - max( keys  count_in_hash() ) in range.
ok 4 - min( keys  count_in_hash() ) in range.
1..4
      s/iter  hash array
hash    24.9    --  -42%
array   14.5   72%    --

这是数组方法的一大胜利（它快了 72%）。如果这仍然太慢，请使用 Inline::C 修剪循环，以使用整数数组重写数组方法。这将更快一个数量级。

这可能是需要优化的关键 3%。

那么，我们应该做些什么来减轻脱离公认习语的影响呢？我们确保记录我们正在做的事情，以便未来的读者（包括未来的我们自己）了解正在做的事情，以及为什么它以我们不熟悉的方式完成。

只是我的 .02。

于 2011-11-14T06:23:09.360 回答
0

根据系统排序实用程序的质量，在命令行：

sort giant-file.txt | uniq -c > giant_file_counts.txt
于 2011-11-14T13:53:12.573 回答