perl - 计算二进制文件中设置位数的最快方法是什么

Question

我想知道在 Perl 中计算二进制文件中设置位数(1)的最快方法是什么我需要速度快，因为我正在读取 10 个文件，每个文件都有大约 5000 万位。

我现在这样做的方式太慢了，运行 10-15 个文件需要几个小时。

这就是我现在的做法(我知道它很慢而且效率低下，但在过去文件要小得多，而且这种方法已经足够好了):

#count number of 1's in binary vector
sub get_DET_fault_count {
    my $bin_vec = shift;

    my $tmp_vec = generate_tmp_path("bin_vec");
    io($tmp_vec)->println( unpack( "B*", $bin_vec ) );
    my $fault_count = `grep -o -E '1' $tmp_vec | wc -l`;

    chomp $fault_count;
    `rm $tmp_vec`;
    return $fault_count;
}

Answer 1

我想到的有两种方式:1) 像你已经在做的那样使用 unpack，但不要浪费周期来做任何 IO。2) 使用带有预先计算值的查找表来确定给定字节中有多少位

1) 这里的技巧是解包的“%”指令，它告诉解包对结果执行校验和，在二进制数据的情况下对所有 0 和 1 求和

use strict;
use warnings;

my $filename = $ARGV[0];

open(my $fh, '<', $filename) or die "$!";
binmode $fh;


my $count = 0;
my $word  = 0;

while ( read $fh, $word, 4 ) {
   $count += unpack '%32B*', $word;
}

print "filename contains $count set bits\n";
__END__
7733485

2) 0 - 255 的值只有一定数量的设置位，永远不会改变，因此您可以预先计算一个数组来保存所有这些值。您浪费了一点内存——大约 4k 或 8k，具体取决于构建——以防止除查找之外的任何计算。

use strict;
use warnings;

my $filename = $ARGV[0];

open(my $fh, '<', $filename) or die "$!";
binmode $fh;

my @bitcounts = (
   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 
   3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 
   3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 
   2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 
   3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 
   5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 
   2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 
   4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 
   4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 
   5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 
   5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
);

my $count = 0;
my $byte  = 0;
while ( read $fh, $byte, 1 ) {
   $count += $bitcounts[ord($byte)];
}

print "filename contains $count set bits\n";
__END__
7733485

对于我处理的样本 JPEG，这两种方法都为我提供了 7733485。