o（n^3）C++コードの複雑さの軽減

Question

以下のアルゴリズムの複雑さを軽減したいと思います。基本的には、入力として単語を取り、その中のユニークな文字の数（単語の「エントロピー」）を計算します。私の現在のソリューションでは、3つの埋め込みforループが使用されています。これはo（n^3）の複雑さを伴います。このコードは大規模なプロジェクトの一部であるため（私たちはboggleというゲームのソルバーを作った）、実行時間を短縮するためにアルゴリズムの複雑さを減らすことを望んでいました。前もって感謝します！

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

しかし、明らかにこれは維持するのが少し難しいです。この解は、O（n）のの複雑さが保証されたを持ち、動的メモリ割り当てを行いません。

文字以上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

一つの安価な解決策は、HashSetの（償却O（1）挿入とルックアップ）である、ちょうどunordered_set内の文字を固執することです：

#include <unordered_set> 

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

これは、n（Oの複雑さをもたらし）、それは得られるほど良いです。

Answer 3

は、余分な（と時間のかかる）メモリの割り当てなしで、場所で計算を行います。

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

Answer 4

文字列が不足している場合、あなたは大きな-Oよりもメモリallocsについてもっと心配する必要があります。いずれにしても、ここではより速い解決策があります。

これはboggleゲームのためのもので、この関数への入力は "word"という文字列であると言われていますので、 "word"のすべての文字がasciiアルファベット文字であることを既に確認していると仮定しています。もしそうなら、ここではおそらく最速のケース不変エントロピー数があります：

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