алгоритм — Снижение сложности кода o (n ^ 3) c ++
Я хотел бы уменьшить сложность следующего алгоритма. По сути, он принимает слово в качестве входных данных и вычисляет количество уникальных букв в нем («энтропия» слова). В моем текущем решении используется 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;
}
Решение
Если это действительно производительность, в зависимости от диапазона допустимых символов что-то вроде этого может быть быстрее:
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; } );
}
Другие решения
Одно дешевое решение — просто вставить персонажей в 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), которая так же хороша, как и получается.
Выполните вычисления на месте, без каких-либо дополнительных (и отнимающих много времени) выделений памяти:
std::sort(word.begin(), word.end());
auto last = std::unique(word.begin(), word.end());
return last - word.begin();
Если строки короткие, вы должны больше беспокоиться о распределении памяти, чем 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 );
}