Perl 数组语法

Question

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

Answer 1

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

展示你的作品

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

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

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

是的，哈希值是很自然的选择，请参阅 perlfaq4，搜索“计数”、“uniq”和“重复”

Answer 2

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。

Answer 3

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

sort giant-file.txt | uniq -c > giant_file_counts.txt