पर्ल में द्वि-आयामी हैश ट्रैवर्सिंग को कैसे अनुकूलित करें?

Question

मेरे पास हैश का हैश %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"; 
    } 
} 

तत्वों मेरी कोड में के रूप में एक ही क्रम में मुद्रित करने के लिए है:

वहाँ (timewise) अनुकूलन करने के लिए किसी भी तरह से कोड के इस टुकड़े है।

Answer 1

दो माइक्रो ऑप्टिमाइज़ेशन: इसके बजाय निरंतर डीरफ्रेंसिंग और बफर के बजाय नक्शा आंतरिक हैश निरंतर प्रिंट का। वैकल्पिक भंडारण प्रारूपों का उपयोग करके सॉर्टिंग से छुटकारा पाना संभव है, दो प्रकारों का परीक्षण किया गया है। परिणाम:

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

निष्कर्ष:

यह presorted भंडारण प्रारूप का उपयोग करने के लिए बेहतर है, लेकिन सी के बिना जीत शायद (अपने परीक्षण डेटासेट पर) 100% के भीतर हो जाएगा। डेटा के बारे में प्रदान की गई जानकारी से पता चलता है कि बाहरी हैश में कुंजी लगभग अनुक्रमिक संख्याएं हैं, इसलिए यह सरणी के लिए रोती है।

स्क्रिप्ट:

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

मैं पहले Sort::Key module के साथ प्रयोग करता हूं क्योंकि सॉर्टिंग सरल लूपिंग और प्रिंटिंग से अधिक समय लेती है। इसके अलावा, यदि आंतरिक हैश कुंजी (ज्यादातर) समान हैं, तो आपको बस उन्हें पूर्ववत करना चाहिए, लेकिन मुझे लगता है कि यह मामला नहीं है या नहीं तो आप पहले से ही ऐसा कर रहे हैं।

आपको स्पष्ट रूप से एक संदर्भ में $ sim_db {$ cycle} असाइन करने का प्रयास करना चाहिए। आपको लगता है कि eachkeys से अधिक तेज़ है, साथ ही विशेष रूप से यदि Sort::Key के साथ उपयोग किया जाता है। मैं जांचता हूं कि नक्शा foreach से भी अधिक तेज़ चलता है, शायद वही है, लेकिन कौन जानता है। यदि आप इसे एक सूची पास करते हैं या इसे कई बार कॉल करते हैं तो आपको print तेज हो सकता है।

मैं इस कोड प्रयास नहीं किया है लेकिन each को छोड़कर एक साथ इन सभी विचारों को फेंक देता है:

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

वहाँ पर्ल here में छँटाई के बारे में एक लेख है, बाहर की जाँच Schwartzian रूपांतरण करता है, तो आप कैसे को देखने के लिए एक इच्छा each का उपयोग कर सकते हैं।

अपने कोड सुरक्षा के प्रति जागरूक होने की जरूरत नहीं है, तो आप क़यास algorithmic complexity attacks के खिलाफ पर्ल के संरक्षण PERL_HASH_SEED की स्थापना द्वारा अक्षम कर सकते हैं या संबंधित चर और/या बदल सेटिंग के साथ पर्ल पुनः संकलित करें, ताकि पर्ल के keys और values आदेशों में चाबी या मूल्यों लौटे क्रमबद्ध क्रमबद्ध क्रम, इस प्रकार आपको उन्हें सॉर्ट करने में काफी समय बचाता है। लेकिन कृपया ऐसा करने से पहले this 28C3 talk देखें। मुझे नहीं पता कि यह भी काम करेगा या नहीं, आपको पर्ल के स्रोत कोड के इस हिस्से को पढ़ने की आवश्यकता होगी, शायद सी

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

जो हो जाता है:

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

नहीं एक बहुत बड़ा लाभ है, लेकिन यह कुछ है। पूर्ववर्ती सरणी का उपयोग करने के लिए अपनी डेटा संरचना को बदलने के बिना आप अनुकूलित नहीं कर सकते हैं।(या XS में पूरी बात लिख)

स्विचिंग foreach छोरों बाहरी पैकेज चर का उपयोग करने के लिए समय का एक छोटा सा की बचत होती है क्योंकि पर्ल पाश में lexicals बनाने के लिए नहीं है। इसके अलावा संकुल चर उपनाम के लिए थोड़ा तेज लगते हैं। एक ही स्तर पर आंतरिक लुकअप को कम करने में भी मदद मिलती है।

मैं तुम्हें STDOUT को प्रिंट कर रहे हैं और फिर एक फाइल करने के लिए उत्पादन पुनः निर्देशित मान? यदि हां, तो पर्ल का उपयोग कर उत्पादन फ़ाइल सीधे और फिर उस संभाल करने के लिए मुद्रण खोलने के लिए फ़ाइल आईओ प्रदर्शन में सुधार के लिए अनुमति दे सकता। एक और सूक्ष्म अनुकूलन विभिन्न रिकॉर्ड आकारों के साथ प्रयोग करना हो सकता है। उदाहरण के लिए, यह किसी भी समय भीतरी पाश में एक सरणी के निर्माण के लिए बचाने के लिए है, तो बाहरी पाश के तल पर/यह प्रिंट में शामिल होने? लेकिन उस कुछ है कि काफी (अन्य आईओ कैशिंग परतों की वजह से और संभवतः व्यर्थ) निर्भर डिवाइस है, तो मैं आप पर निर्भर है कि परीक्षण छोड़ देंगे।