CODEWITHSUNDEEP
c++stringperformance
Ali
Ali

Reputation: 5476

How to efficiently check if a word's all letters are the same in C++

I have checked and couldn't a better option by checking the word's letters one by one. I've decided to use the ascii equivalence of the letter check by diving the word but didn't lead to any where as well. Any Ideas?

Upvotes: 0

Views: 1592

Answers (4)

Steve Jessop
Steve Jessop

Reputation: 279285

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

Clearly in the worst case it can't be done without examining every character. Whichever character(s) you don't examine, might be the same as the others or different, and the result needs to be sensitive to that in the case where the ones you do examine are all the same.

If you know something about what might be in the string, then the order in which you examine the characters might affect how early you can bail out. But knowing nothing, you may as well read them in order, and reading them in order might result in better cache performance.

Things get more complicated if the string is long enough that it's worth parallelizing.

Upvotes: 5

Ian Thompson
Ian Thompson

Reputation: 654

Actually, the solution to this problem can be optimized for large strings, I don't believe it is n-p complete, because a CPU can examine two values that are larger than 8 bits in a single instruction. For example, the string 'aaaaaaaa' in hex is 61616161 61616161 which is (if I've got my endianess correct) 1633771873 1633771873 as integer.

My memory of assembler is fading fast, but comparing two 32bit integers on a 32bit processor is two instructions: mv and cp (mov cmp?), but comparing eight 8 bit integers is 16 instructions (mv cp, mv cp, etc). (Feel free to correct me if I am wrong).

This optimization obviously only works on strings that are multiples of the CPUs word size. If the word size is 32 bits and the string size is more than 8 characters long, then algorithm can be done in (n/4) + (n%4) steps. With a 64 bit word size it would be (n/8) + (n%8) steps, assuming the string is more than 16 characters long.

Upvotes: 0

Gian
Gian

Reputation: 13955

You will at least have to do n-1 comparisons, where n is the length of the string. The most naive approach is going to be (in pseudo code):

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

Upvotes: 0

littleadv
littleadv

Reputation: 20272

Whatever algorithm may be, you'll have to go through all the letters, there's nothing much you can do to avoid it.

Upvotes: 0

Related Questions