ओ (एन^3) सी ++ कोड

Question

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

#include <unordered_set> 

int wordEntropy(const std::string &word) { 
    std::unordered_set<char> uniquechars(word.begin(), word.end()); 
    return uniquechars.size(); 
} 

यह हे की एक जटिलता पैदावार n:

int wordEntropy(string word) 
{ 

int length = word.length(); 
int uniquewords = length; 
string compare = word; 
char save[17]; 
int cond=0; 

for (int ii=0; ii < length; ii++) 
{ 

    for (int jj=ii+1; jj < length; jj++) 
    { 
     for (int kk=0; kk<= ii; kk++) 
     { 
      if (save[kk] == word[ii]) {cond++;} 
     } 
     if (word[ii] == word[jj]) 
     { 
      if (cond>0) {break;} 
      uniquewords--; 
     } 
    } 

    save[ii] = word[ii]; 
    cond = 0; 

} 
return uniquewords; 
} 

Answer 1

यदि यह प्रदर्शन के बारे में वास्तव में है, मान्य वर्ण कुछ इस तरह तेजी से हो सकता है की सीमा पर निर्भर करता है:

std::size_t wordEntropy(const std::string & word) 
{ 
    unsigned char seen[256] = { 0 }; 
    for(unsigned char c : word) 
    { 
     ++seen[ c ]; 
    } 
    return std::count_if(& seen[0], & seen[ 0 ] + 256, 
          [](unsigned char c) { return c != 0; }); 
} 

लेकिन जाहिर है, यह बनाए रखने के लिए थोड़ा कठिन है। इस समाधान में ओ (एन) की जटिलता की गारंटी है और यह कोई गतिशील स्मृति आवंटन नहीं करता है। समस्या नहीं है कि एक चरित्र में 255 से अधिक बार होती है, तो

वैकल्पिक संस्करण:

std::size_t wordEntropy(const std::string & word) 
{ 
    bool seen[256] = { false }; 
    for(unsigned char c : word) 
    { 
     seen[ c ] = true; 
    } 
    return std::count_if(& seen[0], & seen[ 0 ] + 256, 
          [](bool t) { return t; }); 
} 

Answer 2

एक सस्ता समाधान सिर्फ एक unordered_set है, जो एक HashSet (परिशोधित हे (1) प्रविष्टि और देखने) है में पात्रों रहना है), जो उतना अच्छा है जितना इसे मिलता है।

Answer 3

जगह में गणना करते हैं, किसी भी अतिरिक्त (और समय लेने) स्मृति आवंटन के बिना:

std::sort(word.begin(), word.end()); 
auto last = std::unique(word.begin(), word.end()); 
return last - word.begin(); 

Answer 4

तार कम है, तो आप बड़े-ओ से स्मृति allocs के बारे में अधिक चिंतित होना चाहिए। किसी भी तरह से, यहां एक तेज समाधान है।

चूंकि आपने बताया है कि यह एक बोगल गेम के लिए है, और इस फ़ंक्शन में इनपुट "शब्द" नामक एक स्ट्रिंग है, मुझे लगता है कि आप पहले ही सत्यापित कर चुके हैं कि "शब्द" के सभी वर्ण असीसी वर्णमाला वर्ण हैं। यदि ऐसा है, तो शायद सबसे तेज़ केस-इनवेरिएंट एन्ट्रॉपी गिनती है:

int word_entropy (std::string const& word) 
{ 
    uint32_t bit_map = 0; 
    for (char const ch : word) 
     bit_map |= static_cast <uint32_t> (1) << (ch & 31); 
    return __builtin_popcount (bit_map); 
}