Как эффективно проверить, все ли буквы слова одинаковы в C ++

Question

Я проверил и не мог найти лучшего варианта, проверяя буквы слова одну за другой. Я решил использовать ascii-эквивалентность проверки букв при погружении слова, но также ни к чему не привел. Есть идеи?

Answer 1

#include <string>

bool are_all_characters_the_same(const std::string &s) {
    return (s.size() == 0) || s.find_first_not_of(s[0]) == std::string::npos;
}

Очевидно, что в худшем случае это невозможно сделать без изучения каждого символа. Какой бы символ (ы) вы не исследовали, он может быть таким же, как другие, или отличаться, и результат должен быть чувствительным к этому в случае, когда те, которые вы проверяете, одинаковы.

Если вы знаете что-то о том, что может быть в строке, то порядок, в котором вы проверяете символы, может повлиять на то, как рано вы сможете спасти. Но ничего не зная, вы можете также прочитать их по порядку, а чтение по порядку может привести к повышению производительности кэша.

Ситуация усложняется, если строка достаточно длинная, чтобы ее можно было распараллелить.

Answer 2

На самом деле, решение этой проблемы может быть оптимизировано для больших строк, я не верю, что оно завершено n-p, потому что ЦП может исследовать два значения, которые больше 8 бит, в одной инструкции. Например, строка «aaaaaaaa» в шестнадцатеричном формате - это 61616161 61616161, которая (если я правильно указал мой порядковый номер) 1633771873 1633771873 как целое число.

Моя память на ассемблере быстро исчезает, но сравнение двух 32-битных целых чисел на 32-битном процессоре - это две инструкции: mv и cp (mov cmp?), А сравнение восьми 8-битных целых чисел - 16 инструкций (mv cp, mv cp и т. Д.) ). (Не стесняйтесь поправлять меня, если я ошибаюсь).

Эта оптимизация, очевидно, работает только со строками, кратными размеру слова ЦП. Если размер слова составляет 32 бита, а размер строки превышает 8 символов, алгоритм может быть выполнен в (n / 4) + (n% 4) шагах. При размере слова 64 бита это будет (n / 8) + (n% 8) шагов при условии, что длина строки превышает 16 символов.

Answer 3

По крайней мере, вам нужно будет сделать n-1 сравнений, где n - длина строки.Наиболее наивный подход будет (в псевдокоде):

c = first character
for i in second character to last character:
    if c = i then continue else return false
return true

Answer 4

Каким бы ни был алгоритм, вам придется пройтись по всем буквам, вы ничего не можете сделать, чтобы избежать его.