पर्ल: एक स्ट्रिंग

Question

भीतर क्रमबद्ध पात्रों मैं दो तार है, और मुझे अगर वे एक दूसरे का विपर्यय हैं परीक्षण करना चाहते हैं। यदि स्ट्रिंग एक स्ट्रिंग बी का विपर्यय शब्द है

के परीक्षण के लिए ए और बी के पात्रों दोनों हल कर रहे हैं। यदि परिणामस्वरूप क्रमबद्ध तार ठीक से मेल खाते हैं, तो स्ट्रिंग ए और स्ट्रिंग बी एक दूसरे के आरेख हैं।

मैं split चरित्र विन्यास में, ऊपर तार ing, पर्ल के sort दिनचर्या का उपयोग कर, join पात्रों वापस एक साथ ing हूँ, और eq के साथ स्ट्रिंग समानता के लिए परीक्षण:

sub anagram 
{ 
    my ($s1, $s2) = @_; 

    return (join '', sort { $a cmp $b } split(//, $s1)) eq 
     (join '', sort { $a cmp $b } split(//, $s2)); 
} 

वहाँ एक रास्ता के लिए होने से बचने के लिए है अदिश और सरणी प्रकार (join और split पर निर्भर) के बीच कन्वर्ट? और यदि हां, तो कौन सी विधि अधिक कुशल है?

Answer 1

दोनों तार चर रहे हैं, मुझे नहीं लगता कि आप ज्यादा बेहतर कर सकते हैं। एक विकल्प हैश बनाने के लिए है जो वर्णों को उनके मायने रखता है, और फिर तुलना करें कि हैंश की एक ही कुंजी और मान हैं। मेरा मानना ​​है कि यह आपके दृष्टिकोण के लिए ओ (एन लॉग एन) के बजाय ओ (एन) है, लेकिन शायद यह बहुत लंबे तारों को छोड़कर वास्तविक प्रदर्शन खराब होगा।

आप, एक निश्चित संदर्भ स्ट्रिंग के लिए चर तार की तुलना तो शायद हैश आधारित दृष्टिकोण लाभांश पहले भुगतान कर सकते हैं, के बाद से आप केवल एक बार संदर्भ हैश करने के लिए की जरूरत चाहते हैं।

Answer 2

वहाँ एक रास्ता अदिश और सरणी प्रकार (join और split पर निर्भर) के बीच परिवर्तित करने के लिए होने से बचाने के है? और यदि हां, तो कौन सी विधि अधिक कुशल है?

चूंकि आप इन्हें दो अलग-अलग प्रश्न पूछते हैं, इसलिए मैं दोनों का जवाब दूंगा।

हां, @ सरणी या % हैश या व्हाट्नॉट बनाने के बिना ऐसा करने के तरीके हैं, और मैं कुछ रूपरेखा तैयार करूंगा; लेकिन इनमें से किसी भी से आपका तरीका अधिक कुशल है।

एक तरह से the substr function का उपयोग करके पात्रों में से एक सरणी के रूप में एक स्ट्रिंग के इलाज के लिए है ($c = substr $s, 4, 1 सेट $s के पांचवें तत्व को $c, और substr($s, 4, 1) = $c$c को $s के पांचवें तत्व सेट), और उस पर किसी भी ठेठ छंटाई एल्गोरिथ्म लागू ।

वैकल्पिक रूप से, मैं बहुत यकीन है कि आप /e साथ बुलबुला-तरह का उपयोग कर बस regex-प्रतिस्थापन को लागू कर सकता हूँ।

अंत में, यदि आप प्रकार-से-तुलना दृष्टिकोण के साथ बांटना करने को तैयार हैं, तो आप लिख सकते हैं:

sub anagram 
{ 
    my ($s1, $s2) = @_; 
    while($s1 =~ m/\G(.)/s) 
     { $s2 =~ s/\Q$1// or return ''; } 
    return $s2 eq ''; 
} 

लेकिन, फिर से, split -then- join इनमें से किसी भी तुलना में अधिक कुशल है ।

Answer 3

मैं पुनः बनाना स्ट्रिंग मौका होगा ओपी की विधि

sub anagram_smatch { 
    return [sort split//,$_[0]] ~~ [sort split//,$_[1]]; 
} 

मात बिना सरणियों तुलना करने के लिए स्मार्ट मैचों का उपयोग कर सोचा लेकिन मानक है कि भालू बाहर नहीं है।

  Rate smatch join 
smatch 1.73/s  -- -54% 
join 3.72/s 116%  -- 

Answer 4

ठीक है, मुझे एक रास्ता मिला है जो 30 गुना तेज है-हालांकि, तर्कसंगत रूप से, इसकी धोखाधड़ी। मैंने Benchmark.pm कोड को बेंचमार्क करने के लिए शामिल किया है, क्योंकि आप स्पष्ट रूप से इसके बारे में परिचित नहीं हैं।

बेंचमार्क है:

  Rate Join Cheat 
Join 83294/s -- -97% 
Cheat 2580687/s 2998% -- 

और कोड। तीसरी लाइन के बाद, मुझे लगता है कि आप समझ जाएंगे कि क्यों अपने यकीनन धोखाधड़ी:

use v5.14; 
use Benchmark qw(cmpthese); 
use Inline 'C'; 

sub an_join { 
    my ($s1, $s2) = @_; 
    return (join '', sort split(//, $s1)) eq 
     (join '', sort split(//, $s2)); 
} 

use constant { 
    STR1 => 'abcdefghijklm', 
    STR2 => 'abcdefghijkmm', 
    STR3 => 'abcdefghijkml', 
}; 

cmpthese(
    0, 
    { 
     'Join' => 'an_join(STR1, STR2); an_join(STR1, STR3)', 
     'Cheat' => 'an_cheat(STR1, STR2); an_cheat(STR1, STR3)', 
    }); 

__END__ 
__C__ 

int an_cheat(const char *a, const char *b) { 
    unsigned char vec_a[26], vec_b[26]; 
    const char *p, *end; 

    memset(vec_a, 0, sizeof(vec_a)); 
    memset(vec_b, 0, sizeof(vec_b)); 

    end = a+strlen(a); 
    for (p = a; p < end; ++p) 
     if (*p >= 'a' && *p <= 'z') 
      ++vec_a[(*p)-'a']; 
    end = b+strlen(b); 
    for (p = b; p < end; ++p) 
     if (*p >= 'a' && *p <= 'z') 
      ++vec_b[(*p)-'a']; 

    return 0 == memcmp(vec_a, vec_b, sizeof(vec_a)); 
} 

बेशक

, अपने धोखा है क्योंकि इसकी में नहीं लिखा पर्ल-अपने पर्ल संस्करण नहीं है में सी इसके अलावा, यह सीमाएँ हैं (केवल लोअरकेस ASCII वर्णों के साथ सबसे महत्वपूर्ण होने के साथ काम करता है-यह सब कुछ और अनदेखा करता है)। लेकिन अगर आपको वास्तव में गति की आवश्यकता है, तो आप इस तरह धोखाधड़ी का उपयोग कर सकते हैं।

संपादित करें:

लेटिन 1 सभी के लिए विस्तार (अच्छी तरह से, कच्चे 8 बिट अक्षर, वास्तव में)। साथ ही, मैंने पाया कि संकलक एक सरल लूप (बिना अंक अंकगणितीय) को अनुकूलित करने में कामयाब रहा है, और इसे पढ़ने में भी आसान है, इसलिए ... बेंचमार्क मुझे बताता है कि लोअरकेस-एएससीआईआईआई-केवल संस्करण लगभग 10% तेज है:

int an_cheat_l1b(const char *a, const char *b) { 
    unsigned char vec_a[UCHAR_MAX], vec_b[UCHAR_MAX]; 
    size_t len, i; 

    memset(vec_a, 0, sizeof(vec_a)); 
    memset(vec_b, 0, sizeof(vec_b)); 

    len = strlen(a); 
    for (i = 0; i < len; ++i) 
     ++vec_a[((const unsigned char *)(a))[i]]; 
    len = strlen(b); 
    for (i = 0; i < len; ++i) 
     ++vec_b[((const unsigned char *)(b))[i]]; 

    return 0 == memcmp(vec_a, vec_b, sizeof(vec_a)); 
} 

ध्यान दें कि सी संस्करण का लाभ बढ़ता है क्योंकि स्ट्रिंग लंबे समय तक हो जाती है- इसकी उम्मीद है, क्योंकि इसके Θ (एन) पर्ल संस्करण ओ (एन · लॉगन) के विपरीत है। इसके अलावा पूर्ण लैटिन 1 के लिए जुर्माना भी कम हो जाता है, जिसका अर्थ है कि जुर्माना शायद memcmp है।