Как оптимизировать обход двумерного хеша в Perl? - PullRequest
Новая
       29

Как оптимизировать обход двумерного хеша в Perl?

6 голосов
/ 15 января 2012

У меня есть хэш хэшей %signal_db. Типичный элемент: $signal_db{$cycle}{$key}. Есть 10 000 сигналов и 10 000 ключей.

Есть ли способ оптимизировать (по времени) этот фрагмент кода: 

foreach my $cycle (sort numerically keys %signal_db) {
    foreach my $key (sort keys %{$signal_db{$cycle}}) {
        print $signal_db{$cycle}{$key}.$key."\n";
    }
}

Элементы должны быть напечатаны в том же порядке, что и в моем коде.

Ответы [ 3 ]

7 голосов
/ 15 января 2012

Две микрооптимизации: отображение внутреннего хэша вместо постоянной разыменования и буфера вместо постоянной печати.Можно избавиться от сортировки, используя альтернативные форматы хранения, опробовав два варианта.Результаты: 

               Rate     original         try3  alternative alternative2
original     46.1/s           --         -12%         -21%         -32%
try3         52.6/s          14%           --         -10%         -22%
alternative  58.6/s          27%          11%           --         -13%
alternative2 67.5/s          46%          28%          15%           --

Вывод:

Лучше использовать предварительно отсортированный формат хранения, но без C win, вероятно, будет в пределах 100% (по моему тестовому набору данных).Предоставленная информация о данных позволяет предположить, что ключи во внешнем хеше являются почти последовательными числами, так что это требует массив.

Script: 

#!/usr/bin/env perl

use strict; use warnings;
use Benchmark qw/timethese cmpthese/;

my %signal_db = map { $_ => {} } 1..1000;
%$_ = map { $_ => $_ } 'a'..'z' foreach values %signal_db;

my @signal_db = map { { cycle => $_ } } 1..1000;
$_->{'samples'} = { map { $_ => $_ } 'a'..'z' } foreach @signal_db;

my @signal_db1 = map { $_ => [] } 1..1000;
@$_ = map { $_ => $_ } 'a'..'z' foreach grep ref $_, @signal_db1;

use Sort::Key qw(nsort);

sub numerically { $a <=> $b }

my $result = cmpthese( -2, {
    'original' => sub {
        open my $out, '>', 'tmp.out';
        foreach my $cycle (sort numerically keys %signal_db) {
            foreach my $key (sort keys %{$signal_db{$cycle}}) {
                print $out $signal_db{$cycle}{$key}.$key."\n";
            }
        }
    },
    'try3' => sub {
        open my $out, '>', 'tmp.out';
        foreach my $cycle (map $signal_db{$_}, sort numerically keys %signal_db) {
            my $tmp = '';
            foreach my $key (sort keys %$cycle) {
                $tmp .= $cycle->{$key}.$key."\n";
            }
            print $out $tmp;
        }
    },
    'alternative' => sub {
        open my $out, '>', 'tmp.out';
        foreach my $cycle (map $_->{'samples'}, @signal_db) {
            my $tmp = '';
            foreach my $key (sort keys %$cycle) {
                $tmp .= $cycle->{$key}.$key."\n";
            }
            print $out $tmp;
        }
    },
    'alternative2' => sub {
        open my $out, '>', 'tmp.out';
        foreach my $cycle (grep ref $_, @signal_db1) {
            my $tmp = '';
            foreach (my $i = 0; $i < @$cycle; $i+=2) {
                $tmp .= $cycle->[$i+1].$cycle->[$i]."\n";
            }
            print $out $tmp;
        }
    },
} );
4 голосов
/ 16 января 2012 
my %signal_db = map {$_ => {1 .. 1000}} 1 .. 1000;

sub numerically {$a <=> $b}
sub orig {
    my $x;
    foreach my $cycle (sort numerically keys %signal_db) {
        foreach my $key (sort keys %{$signal_db{$cycle}}) {
            $x += length $signal_db{$cycle}{$key}.$key."\n";
        }
    }
}

sub faster {
    my $x;
    our ($cycle, $key, %hash); # move allocation out of the loop
    local *hash;      # and use package variables which are faster to alias into

    foreach $cycle (sort {$a <=> $b} # the {$a <=> $b} literal is optimized
                    keys %signal_db) {
        *hash = $signal_db{$cycle}; # alias into %hash
        foreach $key (sort keys %hash) {
            $x += length $hash{$key}.$key."\n";  # simplify the lookup
        }
    }
}

use Benchmark 'cmpthese';
cmpthese -5 => {
    orig   => \&orig,
    faster => \&faster,
};

, который получает: 

         Rate   orig faster
orig   2.56/s     --   -15%
faster 3.03/s    18%     --

Не огромный выигрыш, но это нечто.Вы можете оптимизировать гораздо больше, не меняя структуру данных для использования предварительно отсортированных массивов.(или писать все это в XS)

Переключение циклов foreach на использование внешних переменных пакета экономит немного времени, поскольку perl не нужно создавать лексические выражения в цикле.Также переменные пакета, кажется, немного быстрее псевдоним в.Сокращение внутреннего поиска до одного уровня также помогает.

Я предполагаю, что вы печатаете на STDOUT, а затем перенаправляете вывод в файл?Если это так, использование Perl для непосредственного открытия выходного файла и последующей печати на этот дескриптор может улучшить производительность ввода-вывода файла.Другой микрооптимизацией может быть экспериментирование с различными размерами записейНапример, экономит ли оно какое-либо время, чтобы построить массив во внутреннем цикле, а затем соединить / напечатать его в нижней части внешнего цикла?Но это то, что в значительной степени зависит от устройства (и, возможно, бессмысленно из-за других уровней кэширования ввода-вывода), поэтому я оставлю этот тест на ваше усмотрение.

3 голосов
/ 15 января 2012

Сначала я поэкспериментировал с модулем Sort::Key , потому что сортировка занимает больше времени, чем простая зацикливание и печать. Кроме того, если внутренние ключи хеширования (в основном) идентичны, то вам следует просто предварительно отсортировать их, но я предполагаю, что это не тот случай, иначе вы бы это уже делали.

Очевидно, что вы также должны попытаться присвоить $ signal_db {$ cycle} ссылке. Вы можете обнаружить, что each быстрее, чем keys плюс поиск, особенно если используется с Sort::Key. Я бы проверил, работает ли карта быстрее, чем foreach, наверное, тоже самое, но кто знает. print может работать быстрее, если вы передадите ему список или вызовете его несколько раз.

Я не пробовал этот код, но объединяя все эти идеи, кроме each, получаем: 

foreach my $cycle (nsort keys %signal_db) {
    my $r = $signal_db{$cycle};
    map { print ($r->{$_},$_,"\n"); } (nsort keys %$r);
}

Здесь есть статья о сортировке в perl здесь , посмотрите преобразование Шварца, если хотите узнать, как можно использовать each.

Если ваш код не должен заботиться о безопасности, тогда вы можете отключить защиту Perl от атак алгоритмической сложности , установив PERL_HASH_SEED или связанных переменных и / или перекомпилировать Perl с измененными настройками, так что команды perl keys и values возвращали ключи или значения уже в отсортированном порядке, тем самым экономя ваше время на их сортировку. Но, пожалуйста, посмотрите этот разговор 28C3 , прежде чем делать это. Я даже не думаю, что это сработает, вам нужно прочитать эту часть исходного кода Perl, может быть, проще просто реализовать свой цикл в C.

...