297 Collatz in the Range
Back to General discussions forum
Hi Experts,
I used the following methods to optimize the timing.
1. Removed all even numbers
2. Filtered some modulos
value % 2 == 0 or (value - 2) % 3 == 0 or (value - 4) % 9 == 0 or (value - 5) % 9 == 0 or (
value - 8) % 9 == 0
3.Sieve table of 2^23
but still, my program takes ~90S to process (far away from the allowed time of 60S). Appreciate it if you suggest any optimization tricks.
Cheers, Sam
No optimisation on my part. My code contains the follwoing comment: "run with pypy for acceptable speed". See pypy.
To quantify this a bit, here is an example run: 265 seconds with standard Python, 9 seconds with pypy (30 times faster!), and 4 seconds with java open jdk. There is room for improvement (e.g. caching), but brute force works in this case.
yep, I believe the problem supposed there could be some naive optimization - either caching, or some precalculation - but limit is not strong so even straightforward solution may be sufficient (if it satisfies curiosity of the author).
I tried some simple caching, and the speed-up was about 60%. Nice, but not an order of magnitude better and thus I preferred the simple straightforward solution.
Thanks guys, I try to go with PyPy. And let you know the outcome. Cheers, Sam.
Finaly, PyPy works guys, super fast. Cpython took 85.3S and PyPy just only 7.8S. Thanks!!
less radical but still enough is using the numba module