5

我想降低以下算法的复杂性。基本上，它将一个单词作为输入并计算其中的唯一字母数（单词的“熵”）。我当前的解决方案使用 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;
}
4

4 回答 4

13

一种廉价的解决方案是将字符粘贴在 中unordered_set，这是一个哈希集（摊销 O(1) 插入和查找）：

#include <unordered_set>

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

这产生了 O(n) 的复杂度，这是它所能得到的。

于 2016-10-31T14:30:36.213 回答
10

就地进行计算，无需任何额外（且耗时）的内存分配：

std::sort(word.begin(), word.end());
auto last = std::unique(word.begin(), word.end());
return last - word.begin();
于 2016-10-31T14:34:14.270 回答
9

如果这真的与性能有关，根据有效字符的范围，类似这样的东西可能会更快：

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; } );
}
于 2016-10-31T14:45:10.740 回答
0

如果字符串很短，那么您应该比 big-O 更担心内存分配。无论哪种方式，这是一个更快的解决方案。

既然你提到这是一个拼图游戏，并且这个函数的输入是一个名为“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 );
}
于 2016-11-03T15:04:25.930 回答