c++ - अक्सर एनाग्राम फ़ंक्शन का उपयोग करना अनुकूलित करना




string algorithm (5)

मैंने एक फ़ंक्शन लिखा है जो निर्धारित करता है कि दो शब्द आरेख हैं या नहीं। वर्ड ए शब्द बी का एक आरेख है यदि आप अक्षरों को पुन: व्यवस्थित करके ए के शब्द बी को बना सकते हैं, उदाहरण के लिए:

lead is anagram of deal

यह मेरा कार्य है:

bool is_anagram(std::string const & s1, std::string const & s2)
{
    auto check = [](std::string const & x)
    {
        std::map<char, unsigned> counter;
        for(auto const & c : x)
        {
            auto it = counter.find(c);
            if(it == counter.end())
                counter[c] = 1;
            else
                ++counter[c];
        }
        return counter;
    };

    return check(s1) == check(s2);
}

यह ठीक काम करता है, लेकिन शब्दों की संख्या बढ़ जाती है (और यह फ़ंक्शन मेरे आवेदन के भीतर कई मिलियन बार उपयोग किया जाता है), यह जल्द ही मेरे आवेदन की एक बड़ी बाधा बन गया।

क्या किसी को इस फ़ंक्शन को गति देने का विचार है?


अन्य सभी सुझावों के अतिरिक्त, यदि आप किसी सेट में एनाग्राम के जोड़े ढूंढने की कोशिश कर रहे हैं, तो आप उसी तर्क पर is_anagram को कॉल करेंगे (हालांकि तर्कों के समान जोड़े नहीं) बार-बार।

अधिकांश समाधानों में दो चरण होते हैं:

  1. किसी अन्य ऑब्जेक्ट (स्ट्रिंग स्ट्रिंग, लंबाई 26 की सरणी, एक मानचित्र को अपने स्वयं के समाधान में) के रूप में स्ट्रिंग तर्कों को मानचित्र करें
  2. इन वस्तुओं की तुलना एक-दूसरे से करें

यदि आपके पास N स्ट्रिंग्स का एक सेट है, और आप सभी जोड़ों को एक दूसरे के एनाग्राम ढूंढना चाहते हैं, तो आप is_anagram O(N^2) बार कॉल करेंगे।

आप प्रत्येक N स्ट्रिंग्स के लिए उपरोक्त चरण 1 की गणना करके और फिर परिणामों की तुलना करके बहुत कुछ बचा सकते हैं।


आपके पास 26 वर्ण हैं, 26 के आकार की एक सरणी बनाएं, फिर दोनों शब्दों के माध्यम से पुनरावृत्त करें और जैसे ही आप शब्दों में अक्षरों को घेरते हैं, पहले शब्द में वर्णों के लिए एक समान सरणी तत्व बढ़ाएं और दूसरे में charaacters के लिए संबंधित सरणी तत्व घटाएं शब्द। यदि शब्द एनाग्राम हैं, तो सभी सरणी तत्व अंत में 0 होंगे। जटिलता केवल ओ (एन) होगी जहां एन शब्दों की लंबाई है।


नक्शा निर्माण और std::map::find आपके कॉल पर पुनरावृत्ति के भीतर std::map::find , काफी महंगा है।

इस मामले में, आप इस तथ्य का उपयोग कर सकते हैं कि std::string std::vector<char> जैसे कई संबंधों में व्यवहार करता है, जिसका अर्थ है कि आप इसे std::sort का उपयोग करके सॉर्ट कर सकते हैं:

bool is_anagram(std::string s1, std::string s2)
{
    std::sort(s1.begin(), s1.end());
    std::sort(s2.begin(), s2.end());
    return s1 == s2;
}

आपके द्वारा बनाए जा रहे दो मानचित्रों के बजाय, मैं तारों की प्रतिलिपि ले रहा हूं (उन्हें संदर्भ संदर्भ के बजाय मूल्य से गुजर रहा हूं) और उन्हें सॉर्ट करना, इसलिए

sort("lead") => "adel"
sort("deal") => "adel"

यह परिवर्तन पहले से ही आपके एल्गोरिदम को थोड़ा बढ़ा सकता है। यदि आप मनमानी शब्दों की तुलना करते हैं तो एक और चीज जो प्रदर्शन को बहुत प्रभावित कर सकती है:

bool is_anagram(std::string s1, std::string s2)
{
    if(s1.length() != s2.length())
        return false;
    /* as above */
}

यदि दो तारों की लंबाई अलग है, तो यह स्पष्ट रूप से एक आरेख नहीं हो सकता है। std::string::length() एक बहुत तेज़ ऑपरेशन है (इसे स्ट्रिंग आकार को वैसे भी स्टोर करने की आवश्यकता है), इसलिए हम दो तारों को क्रमबद्ध करने से O(N*log(N)) की हलचल को बचाते हैं।


मैं एक समाधान का प्रस्ताव करता हूं जो दो तारों में से केवल एक को क्रमबद्ध करता है:

 bool is_anagram(std::string const & s1, std::string s2)
 {
     if (s1.length() != s2.length()) return false;
     for (int i=0; i<s1.length(); ++i)
     {
         size_t pos = s2.find(s1[i], i);
         if (pos == std::string::npos)
         {
             return false;
         }
         std::swap(s2[i], s2[pos]);
     }
     return true;
 }

यह समाधान उन परिस्थितियों में फायदेमंद हो सकता है जहां आपके पास एक स्ट्रिंग में एक वर्ण है जो दूसरे में नहीं है - क्योंकि यदि यह अन्य स्ट्रिंग में वह वर्ण नहीं ढूंढता है, तो यह मूल्यांकन को छोटा कर सकता है (इसके विपरीत यहां दिखाए गए सभी अन्य समाधान, जहां हमेशा पूर्ण तारों का मूल्यांकन किया जाता है)। विशेष रूप से यदि एक तरफ यह अनन्य चरित्र एक लंबी स्ट्रिंग में जल्दी होता है ...

सॉर्ट समाधान पर एक लाभ को भंडारण स्थान की भी आवश्यकता होती है - सॉर्ट समाधान के लिए दो तारों की प्रतिलिपि की आवश्यकता होती है, जबकि मेरे समाधान में केवल एक प्रतिलिपि बनाई जाती है। छोटी स्ट्रिंग लम्बाई के लिए (गणना करने के लिए प्रयुक्त int प्रकार के आधार पर, लेकिन कम से कम 256 वर्णों तक), इसे "गिनती अप / डाउन" समाधान की तुलना में कम स्मृति की भी आवश्यकता होती है।

दूसरी ओर, एनाग्राम वाले लंबे तारों के लिए, यह "गिनती ऊपर / नीचे" समाधान के पीछे गिरना शुरू हो जाता है।

विश्लेषण

नीचे दिए गए कोड और परिणाम देखें। जैसा कि आसानी से देखा जा सकता है, मेरा समाधान (is_anagram3) लघु एनाग्राम के लिए काफी तेज़ है (केवल वास्तव में पूरी तरह कार्यात्मक समकक्ष 26 वर्ण गणना गिनती / नीचे विधि द्वारा पीटा जाता है), और लंबे गैर-एनाग्राम मामले के लिए भी सबसे तेज़ है, जिसमें गैर- मिलान करने वाले पात्र; लेकिन लंबे तारों के लिए गिनती अप / डाउन विधियों की तुलना में धीमे हो जाते हैं जो एनाग्राम हैं, या लंबे गैर-एनाग्राम के लिए जो चरित्र गणनाओं से भिन्न होते हैं।

सारांश

अंत में, यह वास्तव में अनुमानित इनपुट डेटा पर निर्भर करेगा कि आदर्श समाधान क्या है:

  • एकल कॉल के लिए, "गिनती अप / डाउन" समाधान आमतौर पर कई मामलों में सर्वश्रेष्ठ प्रदर्शन प्रदान करेंगे।
  • परिस्थितियों के आधार पर, (उदाहरण के लिए उपरोक्त वर्णित तारों की संभावनाओं के साथ अलग-अलग वर्ण होते हैं), मेरा समाधान तेज़ हो सकता है
  • अभी तक परीक्षण नहीं किया गया है, लेकिन ऐसा लगता है: इस मामले के लिए जब आपके पास कई एनाग्राम जांच करने के लिए जांच होती है, और जब आप सॉर्ट किए गए तारों के लिए कैश लागू करते हैं, तो सॉर्टिंग और तुलना समाधान सबसे तेज़ हो जाएगा।

कोड:

#include <string>
#include <map>
#include <algorithm>

#include <sys/time.h>
#include <iostream>
#include <iomanip>

bool is_anagram(std::string const & s1, std::string const & s2)
{
    auto check = [](std::string const & x)
    {
        std::map<char, unsigned> counter;
        for(auto const & c : x)
        {
            auto it = counter.find(c);
            if(it == counter.end())
                counter[c] = 1;
            else
                ++counter[c];
        }
        return counter;
    };

    return check(s1) == check(s2);
}

bool is_anagram2(std::string s1, std::string s2)
{
    std::sort(s1.begin(), s1.end());
    std::sort(s2.begin(), s2.end());
    return s1 == s2;
}

bool is_anagram3(std::string const & s1, std::string s2)
{
    if (s1.length() != s2.length()) return false;

    for (int i=0; i<s1.length(); ++i)
    {
        size_t pos = s2.find(s1[i], i);
        if (pos == std::string::npos)
        {
            return false;
        }
        std::swap(s2[i], s2[pos]);
    }
    return true;
}

bool is_anagram4(std::string const & s1, std::string const & s2)
{
    if (s1.length() != s2.length()) return false;

    int count[26] = {0};
    for (int i=0; i<s1.length(); ++i)
    {
        count[s1[i]-'a']++;
        count[s2[i]-'a']--;
    }
    for (int i=0; i<26; ++i)
    {
        if (count[i] != 0) return false;
    }
    return true;
}

bool is_anagram5(std::string const & s1, std::string const & s2)
{
    if (s1.length() != s2.length()) return false;

    int count[256] = {0};
    for (int i=0; i<s1.length(); ++i)
    {
        count[s1[i]]++;
        count[s2[i]]--;
    }
    for (int i=0; i<256; ++i)
    {
        if (count[i] != 0) return false;
    }
    return true;
}

template<typename T>
bool test(const char* name, T func)
{
    if (!func("deal", "lead") || !func("lead", "deal") || !func("dealbreaker", "breakdealer") ||
        !func("dealbreakerdealbreakerdealbreakerdealbreaker", "breakdealerbreakdealerbreakdealerbreakdealer") ||
        func("dealbreakerdealbreakerdealbreakerdealbreakera", "breakdealerbreakdealerbreakdealerbreakdealerb") ||
        func("dealxbreakerdealbreakerdealbreakerdealbreaker", "breakdealerbreakdealerbreakdealerbreakdealerb") ||
        func("abcdefg", "tuvwxyz") ||
        func("lot", "bloat") || func("lead", "deala") ||
        func("lot", "bloat") || func("deala", "lead") ||
        func("abc", "abcd"))
    {
        std::cout << name << ": impl doesn't work" << std::endl;
        return false;
    }
    return true;
}

template<typename T>
void measure(const char* name, T func,
    std::string const & s1, std::string const & s2)
{
    timeval start,end;
    unsigned long secDiff;
    long usecDiff;

    gettimeofday(&start, 0);
    for (int i=0; i<100000; ++i)
    {
        func(s1, s2);
    }
    gettimeofday(&end, 0);
    secDiff = end.tv_sec - start.tv_sec;
    usecDiff = end.tv_usec - start.tv_usec;
    if (usecDiff < 0)
    {
        secDiff--;
        usecDiff += 1000000;
    }
 std::cout << name << ": " << secDiff << "."<< std::setw(3) << std::setfill('0') << (usecDiff/1000) << " s" << std::endl;
}

template <typename T>
void run(const char * funcName, T func)
{
    std::cout << funcName << std::endl;
    if (!test(funcName, func)) {
        return;
    }
    measure("short", func, "dealbreaker", "breakdealer");
    measure("short no anagram", func, "abcdefg", "tuvwxyz");
    measure("long", func, "dealbreakerdealbreakerdealbreakerdealbreaker", "breakdealerbreakdealerbreakdealerbreakdealer");
    measure("long no anagram", func, "dealbreakerdealbreakerdealbreakerdealbreakera", "breakdealerbreakdealerbreakdealerbreakdealerb");
    measure("long no anagram nonmatching char", func, "dealxbreakerdealbreakerdealbreakerdealbreaker", "breakdealerbreakdealerbreakdealerbreakdealerb");
}

int main(int argv, char**argc)
{
    run("is_anagram", is_anagram);
    run("is_anagram2", is_anagram2);
    run("is_anagram3", is_anagram3);
    run("is_anagram4", is_anagram4);
    run("is_anagram5", is_anagram5);
}

उत्पादन

मेरी धीमी एटम मशीन पर मापा गया, परिणाम विभिन्न प्रणालियों पर थोड़ा भिन्न हो सकते हैं, लेकिन सामान्य रूप से सापेक्ष प्रदर्शनों की एक अच्छी तस्वीर देना चाहिए:

is_anagram
short: 2.960 s
short no anagram: 2.154 s
long: 8.063 s
long no anagram: 8.092 s
long no anagram nonmatching char: 8.267 s
is_anagram2
short: 0.685 s
short no anagram: 0.333 s
long: 3.332 s
long no anagram: 3.557 s
long no anagram nonmatching char: 3.740 s
is_anagram3
short: 0.280 s
short no anagram: 0.022 s
long: 0.984 s
long no anagram: 0.994 s
long no anagram nonmatching char: 0.140 s
is_anagram4
short: 0.123 s
short no anagram: 0.071 s
long: 0.399 s
long no anagram: 0.389 s
long no anagram nonmatching char: 0.390 s
is_anagram5
short: 0.283 s
short no anagram: 0.145 s
long: 0.551 s
long no anagram: 0.454 s
long no anagram nonmatching char: 0.455 s

यहां एनाग्राम विश्लेषण करने वाले कार्यों का चयन किया गया है:

#include <iostream>
#include <iomanip>
#include <map>
#include <cctype>
#include <string>
#include <algorithm>

using namespace std;

bool is_anagram(const std::string & s1, const std::string & s2)
{
    auto check = [](const std::string& x)
    {
        std::map<char, unsigned> counter;
        for(auto c : x)
        {
            auto it = counter.find(c);
            if(it == counter.end())
                counter[c] = 1;
            else
                ++counter[c];
        }
        return counter;
    };

    return check(s1) == check(s2);
}


bool is_anagram1(const std::string & s1, const std::string & s2)
{
    auto check = [](const std::string& x)
    {
        std::map<char, unsigned> counter;
        for(auto c : x)
        {
        ++counter[c];
        }
        return counter;
    };

    return check(s1) == check(s2);
}


bool is_anagram2(std::string s1, std::string s2)
{
    std::sort(s1.begin(), s1.end());
    std::sort(s2.begin(), s2.end());
    return s1 == s2;
}


bool is_anagram3(std::string s1, std::string s2)
{
    if (s1.length() != s2.length()) return false;
    std::sort(s1.begin(), s1.end());
    std::sort(s2.begin(), s2.end());
    return s1 == s2;
}

bool is_anagram4(const std::string &s1, const std::string &s2)
{
    int arr[256] = {};
    if (s1.length() != s2.length()) return false;
    for(std::string::size_type i = 0; i < s1.length(); i++)
    {
    arr[(unsigned)s1[i]]++;
    arr[(unsigned)s2[i]]--;
    }
    for(auto i : arr)
    {
    if (i) return false;
    } 
    return true;
}

bool is_anagram5(const std::string &s1, const std::string &s2)
{
    int arr[26] = {};
    if (s1.length() != s2.length()) return false;

    for(std::string::size_type i = 0; i < s1.length(); i++)
    {
    arr[(unsigned)tolower(s1[i])-'a']++;
    arr[(unsigned)tolower(s2[i])-'a']--;
    }
    for(auto i : arr)
    {
    if (i) return false;
    } 
    return true;
}


static __inline__ unsigned long long rdtsc(void)
{
    unsigned hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}


template<typename T>
void bm(const char *name, T func, 
    const std::string &s1, const std::string &s2)
{
    unsigned long long time = rdtsc();
    bool res = func(s1, s2);
    time = rdtsc()-time;
    cout << "Function" << left << setw(15) << name 
     << " time: " << right << setw(8) << time 
     << " Res: " << res << endl;
}


#define BM(x) bm(#x, x, s1, s2)

int main()
{
    const std::string short1 = "lead";
    const std::string short2 = "deal";
    const std::string long1 = "leaddealleaddealleaddealleaddealleaddealleaddealleaddealleaddealleaddealleaddeal";
    const std::string long2 = "dealleaddealleaddealleaddealleaddealleaddealleaddealleaddealleaddealleaddeallead";

    cout << "Testing with short strings:" << endl;
    std::string s1 = short1;
    std::string s2 = short2;

    BM(is_anagram);
    BM(is_anagram1);
    BM(is_anagram2);
    BM(is_anagram3);
    BM(is_anagram4);
    BM(is_anagram5);

    cout << "Testing with long strings:" << endl;
    s1 = long1;
    s2 = long2;

    BM(is_anagram);
    BM(is_anagram1);
    BM(is_anagram2);
    BM(is_anagram3);
    BM(is_anagram4);
    BM(is_anagram5);

    cout << "Testing with inequal short string:" << endl;
    s1 = short1;
    s2 = short2;
    s1[s1.length()-1]++;

    BM(is_anagram);
    BM(is_anagram1);
    BM(is_anagram2);
    BM(is_anagram3);
    BM(is_anagram4);
    BM(is_anagram5);

    cout << "Testing with inequal long string:" << endl;
    s1 = long1;
    s2 = long2;
    s1[s1.length()-1]++;

    BM(is_anagram);
    BM(is_anagram1);
    BM(is_anagram2);
    BM(is_anagram3);
    BM(is_anagram4);
    BM(is_anagram5);
}

और परिणाम:

Testing with short strings:
Functionis_anagram      time:    72938 Res: 1
Functionis_anagram1     time:    15694 Res: 1
Functionis_anagram2     time:    49780 Res: 1
Functionis_anagram3     time:    10424 Res: 1
Functionis_anagram4     time:     4272 Res: 1
Functionis_anagram5     time:    18653 Res: 1
Testing with long strings:
Functionis_anagram      time:    46067 Res: 1
Functionis_anagram1     time:    33597 Res: 1
Functionis_anagram2     time:    52721 Res: 1
Functionis_anagram3     time:    41570 Res: 1
Functionis_anagram4     time:     9027 Res: 1
Functionis_anagram5     time:    15062 Res: 1
Testing with inequal short string:
Functionis_anagram      time:    11096 Res: 0
Functionis_anagram1     time:    10115 Res: 0
Functionis_anagram2     time:    13022 Res: 0
Functionis_anagram3     time:     8066 Res: 0
Functionis_anagram4     time:     2963 Res: 0
Functionis_anagram5     time:     1916 Res: 0
Testing with inequal long string:
Functionis_anagram      time:    44246 Res: 0
Functionis_anagram1     time:    33961 Res: 0
Functionis_anagram2     time:    45004 Res: 0
Functionis_anagram3     time:    38896 Res: 0
Functionis_anagram4     time:     6455 Res: 0
Functionis_anagram5     time:    14603 Res: 0

यह स्पष्ट है कि प्रत्येक चरित्र की घटना के आधार पर ऊपर / नीचे गिनती वाली सरणी के साथ सीधी जांच, विजेता है। मैंने मूल कोड लिया और खोज को हटा दिया, और इस तथ्य का उपयोग किया कि is_anagram1 में कोई प्रविष्टि नहीं है, तो एक map::operator[] शून्य मान is_anagram1 , जो कुछ सभ्य सुधार भी दिखाता है।

परिणाम मेरी मशीन से हैं, ये अन्य मशीनों पर परिणामों को प्रतिबिंबित नहीं कर सकते हैं या नहीं, लेकिन मुझे संदेह है कि "विजेता बनाम हारने वाला" काफी अलग होगा।

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

"ढूंढें" ऑपरेशन के बारे में सोचा, और इसे विभिन्न तरीकों से उपयोग करने का फैसला किया:

bool is_anagram0(const std::string & s1, const std::string & s2)
{
    auto check = [](const std::string& x)
    {
        std::map<char, unsigned> counter;
        for(auto const &c : x)
        {
            auto it = counter.find(c);
            if(it == counter.end())
                counter[c] = 1;
            else
                it->second++;
        }
        return counter;
    };

    return check(s1) == check(s2);
}

मूल कार्य पर थोड़ा सुधार देता है, लेकिन सरणी समाधान के साथ प्रतिस्पर्धा करने के लिए पर्याप्त बेहतर नहीं है जो सर्वोत्तम परिणाम देता है।







anagram