IsIsogram() - I thought I'd made a more efficient version

Unreal Courses Show
,
#1

Made my IsIsogram function using an array containing a number for each letter in the alphabet that I use to track the sum of each letter in a word, then just check if the max element of the array is > 1.
Meaning I only need to loop through the word once.

bool UBullCowCartridge::IsIsogram(const FString Word)
{
    // Initialise alphabet array
    //                         a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
    int32 LetterCounts[26] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

    // Loop through word adding occurences of letter to alphabet array
    for (int32 i = 0; i < Word.Len(); i++)
    {
        char Letter = Word.ToLower()[i];
        ++LetterCounts[Letter - 'a'];
    }

    // Check if maximum value in alphabet array if greater than 1
    if (*std::max_element(LetterCounts, LetterCounts + 26) > 1)
    {
        return false;
    }

    return true;
}

Edit:
Iā€™m aware this will fail if something other than a plain letter is passed to the function so Iā€™m adding further input validation elsewhere in the program

#2

Not bad but thereā€™s a couple of improvements that could be made.

char Letter = Word.ToLower()[i];

Here you are making the whole word lower and then discarding that each loop. You could instead use

Word.ToLowerInline()

At the start of the function to make the whole word lower case once.

if (*std::max_element(LetterCounts, LetterCounts + 26) > 1) { return false; }

This is looping the array when it could have just checked when the increment happened and returned without needing to go through the whole word first and then looped again.

Also Unreal has itā€™s own implementations of the standard algorithms e.g.
https://docs.unrealengine.com/en-US/API/Runtime/Core/Algo/Algo__MaxElement/1/index.html
So your code could be

if (Algo::MaxElement(LetterCounts) > 1)

And hereā€™s a benchmark of 4 different solutions

Run on (16 X 3600 MHz CPU s)
CPU Caches:
  L1 Data 32K (x8)
  L1 Instruction 32K (x8)
  L2 Unified 524K (x8)
  L3 Unified 16777K (x2)
----------------------------------------------------------------
Benchmark                      Time             CPU   Iterations
----------------------------------------------------------------
NestedLoop/alphabet         1604 ns         1611 ns       407273
AdjacentFind/alphabet        144 ns          144 ns      4977778
Array1/alphabet             3774 ns         3749 ns       179200
Array2/alphabet              154 ns          153 ns      4480000

NestedLoop/planet           66.5 ns         66.3 ns      8960000
AdjacentFind/planet         28.4 ns         28.3 ns     24888889
Array1/planet                354 ns          353 ns      1947826
Array2/planet               35.8 ns         36.0 ns     18666667

NestedLoop/bob              10.1 ns         10.0 ns     64000000
AdjacentFind/bob            8.69 ns         8.72 ns     89600000
Array1/bob                   144 ns          144 ns      4977778
Array2/bob                  28.2 ns         27.8 ns     23578947

NestedLoop is what is done in the course does
AdjacentFind sorts and then finds if any adjacent pairs are the same letter
Array1 is your implementation
Array2 is with my fixes

(the alphabet test is for the actual alphabet not the word ā€œalphabetā€)

1 Like
#3

Thanks for your feedback!

bool UBullCowCartridge::IsIsogram(FString Word)
{
    // Initialise alphabet array
    //                         a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
    int32 LetterCounts[26] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

    Word.ToLowerInline();

    // Loop through word adding occurences of letter to alphabet array
    for (int32 i = 0; i < Word.Len(); i++)
    {
        char Letter = Word[i];
        if (++LetterCounts[Letter - 'a'] > 1)
        {
            return false;
        }
    }

    return true;
}

No idea how I missed something as obvious as checking the incremented value instantly. but I wouldā€™ve never spotted the fact that I was calling ToLower each loop, thank you!

#4

Oh I forgot to mention that you can just use = { 0 }; to initialise all the elements to 0

1 Like
#5

interesting. Are you going to teach us the AdjacentFind method.? It is deadly efficient.
How do I post codes here? Like this? Do I have to create a new topic?
This is my implementation of nested loop. I looked for an FString function to check that the string contains only alphabet but cannot find, however there is one for checking numeric string.
/[code]
bool UBullCowCartridge::IsIsogram(FString Guess)
{
int i{};
int j{};

for ( i = ( Guess.Len() - 1) ; i > 0; --i)
{
	//PrintLine(TEXT("i is %i ,Guess[i] is %c "), i, Guess[i]);	//debug line
	for (j = (i - 1) ; j >= 0; --j)
	{
		//PrintLine(TEXT("j is %i ,Guess[j] is %c "), j, Guess[j]);	//debug line
		if (Guess[i] == Guess[j])
		{
			return false;
		}
	}
}
return true;

}
/[code]

#6

You can create a new topic for things like this, but make sure you use the right category (this would probably be in the UE4 -> Ask category)

You format a multi-line code block with 3 grave (also called back-tick) symbols (```) on the line above the first line of code, and three more after the last line of code. You can also use HTML notation

with a <code> tag

Also if you want to check if a string contains only letters you can loop through each char and use isalpha()

#7

Well first some disclaimers. These are tested with standard C++ and not Unreal to easily benchmark with Google Benchmark, so the numbers arenā€™t accurate with Unreal but should give a good indication of how it should perform as the only difference should be with the uses of ToLower.

One thing I forgot to do in the last post was to convert all the other benchmarks to use the ToLower alternative I created for the string as the rest of the tests just did tolower in the loop to not need to convert every character if itā€™s not needed. So with Unreal you can use FChar::ToLower which is the same thing as tolower.

So here is the updated version which uses tolower in the loop. (also with an addition test for a 9 letter isogram).

Run on (16 X 3600 MHz CPU s)
CPU Caches:
  L1 Data 32K (x8)
  L1 Instruction 32K (x8)
  L2 Unified 524K (x8)
  L3 Unified 16777K (x2)
-----------------------------------------------------------------
Benchmark                       Time             CPU   Iterations
-----------------------------------------------------------------
NestedLoop/alphabet          1571 ns         1569 ns       448000
AdjacentFind/alphabet         143 ns          143 ns      4480000
Array/alphabet               75.0 ns         75.0 ns      8960000

NestedLoop/numerical          154 ns          153 ns      4072727
AdjacentFind/numerical       43.7 ns         43.9 ns     16000000
Array/numerical              24.0 ns         24.1 ns     29866667

NestedLoop/planet            66.4 ns         67.0 ns     11200000
AdjacentFind/planet          28.6 ns         28.5 ns     23578947
Array/planet                 16.5 ns         16.5 ns     40727273

NestedLoop/bob               10.2 ns         10.3 ns     64000000
AdjacentFind/bob             8.73 ns         8.79 ns     74666667
Array/bob                    8.69 ns         8.58 ns     74666667

The adjacent find method requires the string to be sorted first.

Algo::Sort(Word);
for (int32 i = 0, j = 1; j < Word.Len(); ++i, ++j)
{
    if (FChar::ToLower(Word[i]) == FChar::ToLower(Word[j]))
    {
        return false;
    }
return true;
#8

Although if youā€™re handling player input you will likely already be making sure everything is the same case to make it easier to work with.

#9

Forget it Dan,
I forgot ā€˜;ā€™ in the header file. Hopefully everything will be ok.

Thanks.

#10

Hi All,
Thought Iā€™ll share with you my version here as I believe it is pretty efficient as well (only one loop and as soon as first duplicate is found function returns false):

bool UBullCowCartridge::IsIsogram(const FString& Input)
{
    TMap<TCHAR, int32> temp;
    for (auto &&cr : Input.ToLower())
    {    
        if (!temp.Contains(cr))
        {
            temp.Add(cr, 0);
        }
        else
        {           
            return false;                
        }        
    }
    return true;
}

Privacy & Terms