什么是Perl中用于字符串的最快校验位例程？

Question

什么是Perl中用于字符串的最快校验位例程？

perlpackunpack

3

给定一个数字字符串，我需要使用Perl尽快将所有数字相加。

我的第一种实现是使用unpack()解压缩数字，然后使用List::Utils的sum()函数对数字列表求和。这个方法非常快，但是否有更快的打包/解包方法来完成此任务呢？

我试过使用了pack/unpack组合，并对两种实现进行了基准测试。使用的CPU时间几乎相同；也许有我不知道的一些快速技巧吗？

以下是我如何进行基准测试的方法：

#!/usr/bin/env perl

use 5.012;
use strict;
use List::Util qw/sum/;
use Benchmark qw/timethese/;

timethese ( 1000000, {
    list_util => sub {
        my $CheckDigit = "999989989";
        do {
            $CheckDigit = sum( unpack( 'AAAAAAAAA', $CheckDigit ) );
        } while ( $CheckDigit > 9 );
    },
    perl_only => sub {
        my $CheckDigit = "999989989";
        do {
            $CheckDigit = unpack( '%16S*', pack( 'S9', unpack( 'AAAAAAAAA', $CheckDigit ) ) );
        } while ( $CheckDigit > 9 );
    },
} );

- Marco De Lellis

也许可以使用Inline::C？您可以使用SvIV宏将Perl标量变量转换为C int。 - daxim

我总是在这种情况下考虑使用C（和Inline::C），但非常谦虚地说，我认为List::Util sum()是目前可用的最快实现。 - Marco De Lellis

2个回答

4

不要过于聪明地使用pack/unpack，而是使用简单的split，或者略微数学上的巧妙之处，使用模运算，这比所有其他方法都更好。

#!/usr/bin/env perl

use strict;
use List::Util qw/sum/;
use Benchmark qw/timethese/;

my $D="99949596";

timethese ( 1000000, {
    naive => sub {
        my $CheckDigit= $D;
        do {
            $CheckDigit = sum( split//, $CheckDigit );
        } while ( $CheckDigit > 9 ); 
    },  
    list_util => sub {
        my $CheckDigit = $D;
        do {
            $CheckDigit = sum( unpack( 'AAAAAAAAA', $CheckDigit ) );
        } while ( $CheckDigit > 9 );
    },
    perl_only => sub {
        my $CheckDigit = $D;
        do {
            $CheckDigit = unpack( '%16S*', pack( 'S9', unpack( 'AAAAAAAAA', $CheckDigit ) ) );
        } while ( $CheckDigit > 9 );
    },
    modulo => sub {
        my $CheckDigit = $D % 9;
    },
} );

结果：

Benchmark: timing 1000000 iterations of list_util, modulo, naive, perl_only...
 list_util:  5 wallclock secs ( 4.62 usr +  0.00 sys =  4.62 CPU) @ 216450.22/s (n=1000000)
    modulo: -1 wallclock secs ( 0.07 usr +  0.00 sys =  0.07 CPU) @ 14285714.29/s (n=1000000)
            (warning: too few iterations for a reliable count)
     naive:  3 wallclock secs ( 2.79 usr +  0.00 sys =  2.79 CPU) @ 358422.94/s (n=1000000)
 perl_only:  6 wallclock secs ( 5.18 usr +  0.00 sys =  5.18 CPU) @ 193050.19/s (n=1000000)

- mirod

“轻度数学聪明”似乎是最快的。我不知道模数属性，这是我的错。 - Marco De Lellis

我知道这个属性，但是我并没有想到它会是最快的方法，而且差距如此之大，所以今天我们都学到了一些东西。 - mirod

4

请注意，当其他方法产生9时，$D％9会产生0。实际等效函数是($D + 0) && ($D％9 || 9)。 - cjm

@cjm：收到，谢谢。我一直认为split()函数比unpack()函数慢，但你的回答告诉了我另一个故事。 - Marco De Lellis

糟糕！你发现了，谢谢。这会教训我在发布代码之前不进行正式（全面）的测试。 - mirod

2

此外，您设置的基准测试方式使取模运算得到了额外的提升，因为将 $D 从字符串转换为整数只会发生一次，而不是 1,000,000 次。在实际程序中，每次都会使用不同的数字字符串。尽管如此，它仍然比拆分字符串要快得多。 - cjm

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- cjm · Accepted Answer

unpack不是拆分字符串最快的方式：

#!/usr/bin/env perl

use strict;
use List::Util qw/sum/;
use Benchmark qw/cmpthese/;

cmpthese ( -3, {
    list_util => sub {
        my $CheckDigit = "999989989";
        do {
            $CheckDigit = sum( unpack( 'AAAAAAAAA', $CheckDigit ) );
        } while ( $CheckDigit > 9 );
    },
    unpack_star => sub {
        my $CheckDigit = "999989989";
        do {
            $CheckDigit = sum( unpack( '(A)*', $CheckDigit ) );
        } while ( $CheckDigit > 9 );
    },
    re => sub {
        my $CheckDigit = "999989989";
        do {
            $CheckDigit = sum( $CheckDigit =~ /(.)/g );
        } while ( $CheckDigit > 9 );
    },
    split => sub {
        my $CheckDigit = "999989989";
        do {
            $CheckDigit = sum( split //, $CheckDigit );
        } while ( $CheckDigit > 9 );
    },
    perl_only => sub {
        my $CheckDigit = "999989989";
        do {
            $CheckDigit = unpack( '%16S*', pack( 'S9', unpack( 'AAAAAAAAA', $CheckDigit ) ) );
        } while ( $CheckDigit > 9 );
    },
    modulo => sub {
        my $CheckDigit = "999989989";
        $CheckDigit = ($CheckDigit+0) && ($CheckDigit % 9 || 9);
    },
} );

产生：

                 Rate perl_only list_util       re unpack_star    split   modulo
perl_only     89882/s        --      -15%     -30%        -45%     -54%     -97%
list_util    105601/s       17%        --     -17%        -35%     -45%     -97%
re           127656/s       42%       21%       --        -21%     -34%     -96%
unpack_star  162308/s       81%       54%      27%          --     -16%     -95%
split        193405/s      115%       83%      52%         19%       --     -94%
modulo      3055254/s     3299%     2793%    2293%       1782%    1480%       --

如果你需要将字符串分割成字符，那么split看起来是最好的选择。

但是，重复求和数字几乎等同于对数字取模9（正如mirod所指出的）。不同之处在于$Digits % 9会产生0而不是9。一个修复这个问题的公式是($Digits-1) % 9 + 1，但是（至少在Perl中）它不能用于全零情况（它会产生9而不是0）。在Perl中有效的表达式是($Digits+0) && ($Digits % 9 || 9)。第一个术语处理全零情况，第二个术语处理常规情况，第三个术语将0更改为9。