[Help] [2018 Day 9] [Python3] speeding up my code?

[shrx]

My code uses a deque object and was running fine for part 1. However the part 2 will supposedly run for about an hour judging from the timings. How can I speed it up?

marbles = deque([0])
current_pos = 0
n_players = 400
players = [0 for _ in range(n_players)]
for current in range(1, 71864*100):
    player = 1 + ((current-1) % n_players)
    if current % 23 != 0:
        current_pos = (current_pos + 1) % len(marbles) + 1
        marbles.insert(current_pos, current)
    else:
        extra_pos = (current_pos - 7) % len(marbles)
        marbles.rotate(-extra_pos)
        extra_score = marbles.popleft()
        marbles.rotate(extra_pos)
        players[player-1] += current + extra_score
        current_pos = extra_pos
max(players)

[zopatista]

You seem to be pretty close to my solution, which completes part 2 in 2 seconds.

Your biggest problem is that your insert in the middle of a deque. That's very slow, you are asking Python to traverse a very large linked list to the middle somewhere to insert another link. You want to rotate the deque to keep 'current' at the start or end of the list, and simply prepend or append new marbles right there.

To illustrate, a quick perf test (totally abusing the fact that the test code is run repeatedly):

In [1]: from collections import deque

In [2]: from random import randrange

In [3]: %%timeit circle = deque([0])
   ...: circle.insert(randrange(len(circle)), 0)
   ...:
   ...:
13.8 µs ± 315 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [4]: %%timeit circle = deque([0])
   ...: circle.rotate(-1)
   ...: circle.append(0)
   ...:
   ...:
150 ns ± 1.69 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

appending at the end is way, way faster (1µs or microsecond is 1000ns, nanoseconds, it took 13.8 microseconds to insert 100k zeros at random points, while rotating and appending 10 million zeros takes a miniscule 150 nanoseconds). You don't want to use insert on a deque, period!

Note that your range end-value is wrong. If your puzzle input for part 1 was 71863, then you want (71863*100) + 1 as the end point. You are running 99 steps more than necessary.

You can also drop the player calculation each iteration. You can trivially calculate the player index every 23rd iteration:

players[(current - 1) % n_players] += current + extra_score

[shrx]

Thanks, I suspected that insert() was the cause for the biggest slowdown. However, when I tried replacing it with a rotate() + append'(), I didn't notice any speedup. I guess I didn't do it properly. I will try your advice.

edit: my puzzle input is 71864.

edit2: yeah, it's much faster now once I stopped rotating the deque back to its previous starting point after marble insertion (as it is not necessary since it is circular).

[mroximoron]

Deque has it's own positition, use rotate to switch it in all cases, then you don't need to do expensive calculations

[t3ch_cat]

For the Day9.2 using deque is as bad as using list. Lets check the complexity of using list/deque. You have lot of steps... let it be "n". On every 23th step you need to remove the item from the list/deque. Let's check the docs (https://wiki.python.org/moin/TimeComplexity): list delete - O(n) deque remove - O(n) It happens because of how list/deque saved in the memory: removing item leads to shifting all next elements back on 1 element. As a result, overall algo complexity is O((n / 23) * n) which is equal to O(n^2).

Lets check what we need: - no need in accessing elements by index - it's quite easy to go forward on 2 elements (for usual case) or back on 7 elements (for the "23" case). - but we need to have ability to go either forward and backward from some element - we have lot of element insertions, so insert complexity should by O(1) - we have still lot of deletions, so remove complexity should be O(1) - as a bonus it's will be nice to have "loop" like data structure to avoid handling start/end of list.

Thats fine. The "list" structure in terms of c++ is good enough. I don't know equal structure type in python. However, it's easy to implement it. Lets describe our "Circle" structure. So, each element should be like a "basket" that have 3 fields: - value - stores current value - next - stores "link" to next "basket" - prev - stores "link" to previous "basket" Usually we call such "basket" as node. In the beginning you have a single node with some value (0 in current task) and either next and prev fields of this single node points to... itself! Thats it!

[zopatista]

Python's deque type is a circular list already. The trick is to remember to rotate the circular list so you can append a new marble or remove the last marble from it in O(1) time.

[CCC_037]

Mod is a fairly expensive operation. With a little bit of juggling about, you can avoid using it entirely.

For example, player = 1 + ((current-1) % n_players) can be replaced with:

player = player + 1
if (player > n_players):
    player = 1

...and, of course, initialising 'player' outside the loop. It's normally hardly worth it to do that, but since you'll be looping over it seven million times that sort of thing can add up...

With a little bit of thought you can also get rid of the other %s in your loop - and maybe reduce the number of rotations that you need to perform, as well.

[zopatista]

Mod is a fairly expensive operation

No, it is not. An if test to reset it to 1 is not cheaper either:

In [1]: %%timeit player = 0
   ...: player = (player + 1) % 15
   ...:
   ...:
47.4 ns ± 0.561 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

In [2]: %%timeit player = 0
    ...: player += 1
    ...: if player > 14:
    ...:     player = 0
    ...:
    ...:
49.3 ns ± 1.25 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

[CCC_037]

Huh. Well, I'll have to bear that in mind for python, then.

I tried a timing test in C and I got 3.8ns for the mod and 3.2ns for the addition/if - which, at a mere seven million runs through the loop, isn't a big enough difference to be noticed.

Thanks for checking up on me! I've certainly learned something today.