Hey,
I got a little curious about the aforementioned performance benefits of this algorithm,
so I decided to try and time them (timing code snipped from https://stackoverflow.com/a/23000049).
Timing:
// # Loop algorithm
std::cout << std::endl << "IsIsogram():" << std::endl;
auto begin = std::chrono::high_resolution_clock::now();
IsIsogram(Guess); // code to benchmark
auto end = std::chrono::high_resolution_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << " ns" << std::endl << std::endl;
// # Tutorial algorithm
std::cout << "IsIsogram_TutorialVersion(): " << std::endl;
begin = std::chrono::high_resolution_clock::now();
IsIsogram_TutorialVersion(Guess); // code to benchmark
end = std::chrono::high_resolution_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << " ns" << std::endl;
And the functions:
bool FBullCowGame::IsIsogram(FString Word) const
{
// Iterate through the characters.
for (int i = 0; i < Word.length(); ++i) {
for (int j = 0; j < Word.length(); ++j) {
// Ignore if indices match.
if (i == j)
continue;
// Characters match with differing indices. Not an isogram.
else if (Word[i] == Word[j])
return false;
}
}
return true;
}
bool FBullCowGame::IsIsogram_TutorialVersion(FString Word) const
{
// Treat 0 and 1 letter words as isograms.
if (Word.length() <= 1) { return true; }
TMap<char, bool> LetterSeen;
// For all letters of the word
for (auto Letter : Word) {
if (LetterSeen[Letter]) {
return false;
}
else {
LetterSeen[Letter] = true;
}
}
return true;
}
From the result, it would seem that simply iterating over each character in
nested for loops actually performs better. Is there some compiler black magic involved,
or am I perhaps missing something?
