Какова самая быстрая процедура проверки контрольной цифры для строки в Perl? - PullRequest
Новая
       49

Какова самая быстрая процедура проверки контрольной цифры для строки в Perl?

3 голосов
/ 15 июня 2011

Учитывая строку цифр, я должен как можно быстрее суммировать все цифры, используя Perl.

Моя первая реализация распаковывает цифры с помощью unpack (), затем суммирует список цифр с помощью List :: Utilsсумма ().Это довольно быстро, но есть ли более быстрый рецепт упаковки / распаковки для этой задачи?

Я попробовал использовать комбинацию упаковки / распаковки и провел сравнение двух реализаций.Используемое время процессора практически одинаково;может быть, есть какой-то быстрый трюк, о котором я не знаю?

Вот как я сделал свой тест: 

#!/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 );
    },
} );

Ответы [ 2 ]

6 голосов
/ 15 июня 2011

распаковка не самый быстрый способ разбить строку: 

#!/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 выглядит как ваш лучший выбор, если вам нужно разделитьстрока в символы.

Но многократное суммирование цифр равно почти так же, как взятие числа mod 9 (как указал мирод).Разница в том, что $Digits % 9 выдает 0 вместо 9. Одна формула, которая исправляет это ($Digits-1) % 9 + 1, но (по крайней мере в Perl), которая не работает для случая со всеми нулями (она выдает 9 вместо 0).Выражение, которое работает в Perl: ($Digits+0) && ($Digits % 9 || 9).Первое слагаемое обрабатывает регистр с нулем, второе - с нормальным регистром, а третье - с 0 на 9.

4 голосов
/ 15 июня 2011

Как насчет того, чтобы не быть слишком умным с упаковкой / распаковкой и использовать простое разбиение, или быть слегка математически умным и использовать модуль по модулю, который превосходит все остальные методы? 

#!/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)
...