samedi 22 mai 2021

How to replace a char in string with another char fast(I think test didn't want common way)

I was asked this question in tech test.
They asked how to change ' ' to '_' in string.
I think they didn't want common answer. like this (I can assure this)

void replaceChar(char originalStr[], size_t strLength, char originalChar, char newChar 
{
    for(size_t i = 0 ; i < strLength ; i++)
    {
        if(originalStr[i] == originalChar)
        {
            originalStr[i] = newChar ;
        }
    }
}

So I answered like this. Use WORD. ( Actually I didn't write code, They want just explaining how to do)
I think comparing Each 8 byte(64bit OS) of string with mask 8 byte.
if They eqaul, replace 8byte in a time.

When Cpu read data with size less than WORD , Cpu should do operation clearing rest bits.
It's slow. So I tried to use WORD in comparing chars.

void replaceChar(char originalStr[], size_t strLength, char originalChar, char newChar // 
    {
        size_t mask = 0;
        size_t replaced = 0;
        for(size_t i = 0 ; i < sizeof(size_t) ; i++)
        {
            mask |= originalChar << i;
            replaced |= newChar << i;
        }
        
        for(size_t i = 0 ; i < strLength ; i++)
        {
            
            // if 8 byte data equal with 8 byte data filled with originalChar
            // replace 8 byte data with 8 byte data filled with newChar 
            if(i % sizeof(size_t) == 0 && 
               strLength  - i > sizeof(size_t) && 
               *(size_t*)(originalStr + i) == mask)
            {
                *(size_t*)(originalStr + i) = replaced;
                i += sizeof(size_t);
                continue;
            }

            if(originalStr[i] == originalChar)
            {
                originalStr[i] = newChar ;
            }
        }
    }

Is There any faster way??

Aucun commentaire:

Enregistrer un commentaire