Làm cách nào để tối ưu hóa tính năng băm ngang hai chiều trong Perl?

Question

Tôi có một băm băm %signal_db. Một yếu tố điển hình là: $signal_db{$cycle}{$key}. Có 10.000 tín hiệu và 10.000 khóa.

Có cách nào để tối ưu hóa (timewise) đoạn mã này:

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

Các yếu tố phải được in theo thứ tự như trong mã của tôi.

Answer 1

Hai tối ưu hóa vi: bản đồ bên trong băm thay vì dereferencing liên tục và bộ đệm thay thế in liên tục. Có thể loại bỏ việc sắp xếp bằng cách sử dụng các định dạng lưu trữ thay thế, đã thử nghiệm hai biến thể. Kết quả:

   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%   -- 

Kết luận:

Nó tốt hơn để sử dụng định dạng lưu trữ presorted, nhưng không có C giành chiến thắng có lẽ sẽ là trong vòng 100% (trên bộ dữ liệu thử nghiệm của tôi). Cung cấp thông tin về dữ liệu cho thấy rằng các khóa trong băm bên ngoài là số gần như tuần tự, do đó, điều này khóc cho mảng.

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

Answer 2

Lần đầu tiên tôi thử nghiệm với Sort::Key module vì việc sắp xếp mất nhiều thời gian hơn lặp và in đơn giản. Ngoài ra, nếu các khóa băm bên trong là (chủ yếu) giống hệt nhau, thì bạn nên chỉ đơn giản là presort chúng, nhưng tôi sẽ giả định đây không phải là trường hợp hoặc nếu không bạn sẽ làm điều đó rồi.

Bạn rõ ràng nên thử chỉ định $ signal_db {$ cycle} cho tham chiếu. Bạn có thể thấy rằng each nhanh hơn keys cộng với truy xuất, đặc biệt nếu được sử dụng với Sort::Key. Tôi cũng sẽ kiểm tra xem bản đồ có chạy nhanh hơn foreach không, có lẽ giống nhau, nhưng ai biết được. Bạn có thể tìm thấy print chạy nhanh hơn nếu bạn vượt qua danh sách hoặc gọi nó nhiều lần.

Tôi chưa thử mã này, nhưng ném lại với nhau tất cả những ý tưởng này trừ each cho:

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

Có một bài viết về sắp xếp trong perl here, hãy kiểm tra Schwartzian Biến đổi nếu bạn muốn xem làm thế nào một có thể sử dụng each.

Nếu mã của bạn không cần phải được an ninh có ý thức, thì bạn có thể hình dung vô hiệu hóa bảo vệ Perl chống lại algorithmic complexity attacks bằng cách thiết lập PERL_HASH_SEED hay liên quan đến các biến và/hoặc biên dịch lại Perl với khung cảnh thay đổi, vì vậy của perl mà keys và values lệnh trả lại chìa khóa hoặc giá trị trong sắp xếp thứ tự đã được, do đó giúp bạn tiết kiệm đáng kể thời gian phân loại chúng. Nhưng xin vui lòng xem this 28C3 talk trước khi làm như vậy. Tôi donno nếu điều này thậm chí sẽ làm việc hoặc, bạn cần phải đọc phần này của mã nguồn của Perl, có thể dễ dàng hơn chỉ cần thực hiện vòng lặp của bạn trong C.

Answer 3

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, 
}; 

mà được:

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

Không tăng khổng lồ, nhưng nó là một cái gì đó. Không có nhiều hơn nữa bạn có thể tối ưu hóa mà không thay đổi cấu trúc dữ liệu của bạn để sử dụng các mảng được sắp xếp.(hoặc viết toàn bộ nội dung trong XS)

Chuyển đổi các vòng gói foreach để sử dụng biến gói bên ngoài tiết kiệm một chút thời gian vì perl không phải tạo từ vựng trong vòng lặp. Các biến gói cũng có vẻ nhanh hơn một chút so với bí danh. Việc giảm tra cứu bên trong xuống một cấp cũng giúp ích.

Tôi giả sử bạn đang in tới STDOUT và sau đó chuyển hướng đầu ra sang tệp? Nếu vậy, bằng cách sử dụng Perl để mở tệp đầu ra trực tiếp và sau đó in đến tay cầm đó có thể cho phép cải thiện hiệu suất tệp IO. Một tối ưu hóa vi mô khác có thể là thử nghiệm với các kích thước bản ghi khác nhau. Ví dụ, nó có tiết kiệm thời gian để xây dựng một mảng trong vòng lặp bên trong, sau đó nối/in nó ở dưới cùng của vòng lặp bên ngoài? Nhưng đó là một cái gì đó là khá phụ thuộc thiết bị (và có thể vô nghĩa do các lớp IO caching khác), vì vậy tôi sẽ để lại thử nghiệm đó cho bạn.