Speed up this code?

Question

How can I speed up this code?
https://code.sololearn.com/ceWBQY0eYyJw/?ref=app

I know I can probably skip the numbers the code has already seen, for example, 16. 16 appears at least twice in the output, so we don't need to do it for each occurrence of the number. But I'm not sure how to do that.

Answer 1

Put the whole thing in a function so that the compiler can optimize it. Use a static map object to cache the results so that numbers don't have to be calculated several times. http://www.cplusplus.com/reference/map/map/

Answer 2

Louis This takes like 0.5 seconds. Seriously? 😅

Answer 3

This one will take about 14 seconds on a PC to check the numbers up to one million. It's probably terribly written because I changed plans several times while writing it. There's a lot of room for improvement :(

https://code.sololearn.com/c0iNaKcUnLLj

Answer 4

Dynamic programming.

I dont know cpp that well, but in python I would build a dictionary that contains all the answers as you calculate them. When you encounter a value you have already seen in a previous run, you copy the values from the dictionary instead of repeating the same calculations.
Edit: this is not applicable to this question since the outcome is just the value and lentgth of longest chain, not all values.

Answer 5

Next attempt: down to 7 seconds

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

Answer 6

I replaced i = i*3+1 with i=(i<<1)+i+1 and i /= 2 with i >>= 1, doesn't seem to affect the speed though 😞

Answer 7

I think I'll rewrite the whole thing tomorrow 😓 The already calculated results are stored in seq_len though

Answer 8

did it in python a while back.
https://code.sololearn.com/cREptMRiQyfF/?ref=app

Answer 9

Is there a time limitation? I wrote a code and it seems to be working, but it's somehow noticeably slower than a python script 😅

Answer 10

Python converted to Cpp
https://code.sololearn.com/c13G24lGrKeA/?ref=app

Answer 11

maybe replacing
n=n*3+1 by
n+=(n<<1)+1 and
n=n/2 by
n>>=1
could be faster. It will depend on how the compiler optimizes the code. In assembler my way is way faster than multiplying or dividing integers (something like 1 instruction against 1500+ instructions).

Answer 12

Anna Can you give me an example of how I would do that? I can't figure it out.

I have pretty much figured out how to calculate and count the terms in the sequence, but my method would take a while xD

I'm not sure if you're familiar with Project Euler Problem #14, but I can explain it if you need me to.

Answer 13

Nope. Won't be running it via code playground. Lol

Answer 14

Anna so probably your compiler is optimizing the code in a decent way. My comment is mainly valid when you lack of a math coprocessor (pre-pentium era), and must use a crappy 8 bit processor (i.e. embedded) were you must implement multiplication and division in software ;)
Your seq_len is already your linked list.

Answer 15

And the response is clearly a linked list. You could work using a linked list to store prior results and retrieve any result already calculated.

Answer 16

Empirical confirmation that odds are longer than evens.

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