1- try to run the last version of python, there is speed improvement in 3.10 and 3.11<p><pre><code> >>> import sys; sys.version
'3.10.4 (main, Dec 2 2022, 17:52:13) [Clang 14.0.0 (clang-1400.0.29.202)]'
51.94417405128479
37.79175686836243
100.8145821094513
</code></pre>
2- global variable lookup is costly in python, putting the whole thing in a main() function halves the running time<p><pre><code> 22.97948908805847
22.47922682762146
59.1025867462158
</code></pre>
link to my code:<p><a href="https://gist.github.com/xcombelle/8ac84ccb276f8996ed1a458ee2b3efa7" rel="nofollow">https://gist.github.com/xcombelle/8ac84ccb276f8996ed1a458ee2...</a>