How to improve the time complexity of this code?

Question

Hello! I'm trying to solve this problem, basically I want to expand the strings given some rules:
* Each alphabet letter is mapped like this: A = 0, B = 1, C = 2, D = 3, ..., Z = 25 .
* I should get a letter of the alphabet by using the next: (code(x ) + code(y )) mod 26, where "x" and "y" are two letters, the result of this will give me the position of the letter.
I take as input a string and how many times I want to expand that string, for example:
First example:
* Input: "ACB" 3 (Here my original string is "ACB" and I want to expand it 3 times given the rules above)
* Expected string expanded should be: "ACCECGEGCHFIDHEFB" (this is the result)
Second Example:
* input: AN 5
* Result: ANNANNANNANNANNANNANNANNANNANNANN
Third example:
* input: CC 4
* result: CKIOGQKOEOKQGOIKC

I understand how I should expand the string and I have already the code that does that, here is the piece of code:

https://www.sololearn.com/compiler-playground/cDxiqBvHH8BT

My problem is, that when I upload the code to an online judge, I get "TIME LIMIT", to be honest I don't know how to make more efficient the code to avoid "TIME LIMIT" from the judge, my original solution was to use the function string "insert" to insert the proper character at a given index in the string, but I got TIME LIMIT, so I thought that maybe not using the "insert" string function and insert the character manually could be a solution, but I also get TIME LIMIT
Code:
while (iter < n) {
hash = code(current_word[i]) + code(current_word[i+1]);
int position = (hash) % 26;
string c = string(1, 'A' + position);
string previous_word = current_word;
current_word.insert(i + 1, c);
i += 2;

if (i >= previous_word.size()) {
iter++;
i = 0;
}
}

Does anyone know how I can improve the code? is O(n*m) where "n" is the number of iterations and "m" the string length

Answer 1

Here is my code with some more explanations
https://code.sololearn.com/cC8xXTF1eHcq

Answer 2

I regret to say these few things:
- your algorithm is not O(n*m) but O(2^n * m)
- i could not reduce that complexity as of yet.

But I could improve your algorithm the following ways
1) make code a macro not a function
2) avoid the STL
3) avoid string concatenations

On closer inspection of the expansion algorithm, i noticed it only depends on two neighbouring characters. Those two expand in a definitive way independent of their environment. That expansion pattern is the same for any two characters and need only be computed once and can then be reused. That will be of the more advantage the longer the input string is.

To close off with some numbers to show what I mean, on 25 AN i get a runtime of 1.39s for your version versus 1.19s for mine. Little to no improvement. For a long input string, however, i get on 20 and 100 'A's a runtime of 4.16s for your version vs. 1.9s for mine. Make that 1000 'A's and it is 41.55s for you and 11.05s for me.

Answer 3

Just in case if you can't access to the code link https://code.sololearn.com/cDxiqBvHH8BT/?ref=app

Answer 4

Ani Jona 🕊
Great code.

I always have a hard time visualising this kind of recursive expansion. And splitting it doubles the complexity😅

I will copy your code and try to understand it better.

It is interesting how you handle large numbers. Looks like you are using bit shift operators. I am not good at this at all. Is it because taking the modulo of a sum is basically bit shifting?

But yes, keeping the operations this low level and working with chars instead of strings would greatly speed up the code.

Answer 5

Bob_Li, a single bit shift right for an unsigned type is integer division by 2. It is much faster than "/2", and will be noticeable in a hot code portion like the pattern builder which runs exponentially in the iterations.

Other bit shifts are for convenience though. I don't know an easier way to write 2^N but (1L << N) 😉

Answer 6

Ani Jona 🕊
https://mziccard.me/2015/05/08/modulo-and-division-vs-bitwise-operations/

It seems like compiler optimization seems to matter, too. see the comments in the article. Maybe Eduardo Perez Regin 's higher level code was just doing unnecessary operations?

Answer 7

Eduardo Perez Regin
I've simplified your code a bit.
Maybe if it could be faster if it was working with char* instead of strings?
I'm not good in working with char[].😅
But here it is as of now.

Of course you could comment out unnecessary cout in the main function.

https://code.sololearn.com/ckR2ACzYy3VM/?ref=app

Answer 8

Bob_Li certainly 🙂 of course, in performance critical code one would use high optimisation. But in these code challenges, one cannot control the compiler flags.

For the tests I have been using no optimisation flags of any kind. Might be interesting to see, how optimisation changes the respective performances 👍

Answer 9

Ani Jona 🕊
Hardware architecture is ever changing and compilers have to continually adapt to it to stay relevant. I cannot even imagine what goes on under the hood.

Code optimization is always a tricky subject. I wonder when manual optimization becomes a zero gain pursuit? The compiler knows the machine better, if it is well updated and maintained. People are the weakest link.

Things are heading to a point where the compiler deduces what you're trying to do and writes a totally different implementation that does the same thing... only better.

Coding itself is giving way to automation.

Maybe when AI takes over the compilation, even the crappiest code would be optimized 100%.

But that is assuming people are still needed to write the crappy code.😅