Redukcja złożoności kodu o (n^3) C++

Question

Chciałbym zmniejszyć złożoność następującego algorytmu. Zasadniczo przyjmuje słowo jako dane wejściowe i oblicza liczbę unikalnych liter w nim ("entropia" słowa). Moje obecne rozwiązanie wykorzystuje 3 osadzone dla pętli, które wychodzi na złożoność o (n^3). Ponieważ ten kod jest częścią większego projektu (stworzyliśmy rozwiązanie dla gry znanej jako boggle), miałem nadzieję zmniejszyć złożoność mojego algorytmu w celu skrócenia czasu jego wykonywania. Z góry dziękuję!

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

Jeśli jest to naprawdę o wydajności, w zależności od zakresu poprawnych znaków coś takiego może być szybszy:

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

Ale oczywiście jest to nieco trudniejsze w utrzymaniu. To rozwiązanie ma gwarantowaną złożoność O (n) i nie tworzy żadnych dynamicznych alokacji pamięci.

alternatywna wersja, że ​​nie ma problemów, jeśli postać występuje więcej niż 255 razy:

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

Jeden tanim rozwiązaniem jest po prostu przykleić znaków w unordered_set, który jest HashSet (amortyzowane O (1) do wprowadzania i odnośnika)

#include <unordered_set> 

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

Daje to złożoność O (N), który jest tak dobry, jak to tylko możliwe.

Answer 3

Wykonaj obliczenia na miejscu, bez żadnych dodatkowych (i czasochłonnych) alokacji pamięci:

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

Answer 4

Jeśli ciągi są krótkie, wówczas powinien być bardziej zaniepokojony ALLOCS pamięci niż big-O. Tak czy inaczej, oto szybsze rozwiązanie.

Odkąd wspomniałeś, że jest to gra typu boggle, a wprowadzeniem do tej funkcji jest ciąg o nazwie "słowo", zakładam, że już zweryfikowaliście, że wszystkie znaki w "słowie" są znakami alfabetu ascii. Jeśli tak, to prawdopodobnie najszybsza, niezmienna wielkość entropii:

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