Giảm độ phức tạp của mã o (n^3) C++

Question

Tôi muốn giảm độ phức tạp của thuật toán sau. Về cơ bản, nó có một từ như là một đầu vào và tính toán số lượng các chữ cái duy nhất bên trong nó ("entropy" của từ). Giải pháp hiện tại của tôi sử dụng 3 nhúng cho vòng, mà đi ra đến một phức tạp của o (n^3). Vì mã này là một phần của dự án lớn hơn (chúng tôi đã xây dựng bộ giải cho trò chơi được gọi là boggle), tôi đã hy vọng giảm độ phức tạp của thuật toán để giảm thời gian thực thi của nó. Cảm ơn trước!

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

Nếu đây thực sự là về hiệu suất, tùy thuộc vào phạm vi của các nhân vật có giá trị một cái gì đó như thế này có thể nhanh hơn:

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

Nhưng rõ ràng, điều này khó khăn hơn một chút để duy trì. Giải pháp này có đảm bảo độ phức tạp của O (n) và nó không thực hiện bất kỳ phân bổ bộ nhớ động nào.

phiên bản thay thế mà không có vấn đề nếu một nhân vật xuất hiện nhiều hơn 255 lần:

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

Một giải pháp rẻ tiền chỉ là để dính vào các nhân vật trong một unordered_set, mà là một HashSet (khấu hao O (1) chèn và tra cứu):

#include <unordered_set> 

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

Điều này mang lại một phức tạp của O (n), đó là tốt như nó được.

Answer 3

Do việc tính toán tại chỗ, mà không cần bất kỳ cấp phát bộ nhớ thêm (và tốn thời gian):

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

Answer 4

Nếu chuỗi ngắn, sau đó bạn sẽ lo lắng thêm về allocs bộ nhớ hơn lớn-O. Dù bằng cách nào, đây là một giải pháp nhanh hơn.

Vì bạn đã đề cập rằng trò chơi này là một trò chơi boggle, và đầu vào cho hàm này là một chuỗi có tên "word", tôi giả định rằng bạn đã xác minh rằng tất cả các ký tự trong "word" là ký tự bảng chữ cái ascii. Nếu có, đây có lẽ là số entropy bất biến nhanh nhất của trường hợp:

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