[Python-il] Why is a pypy2 self-balancing binary tree program so much slower than its C++ translation?

Shlomi Fish shlomif at shlomifish.org
Fri Feb 17 15:00:54 IST 2017


Hi all!

I have written a solution to this Project Euler problem -
https://projecteuler.net/problem=581 first in python 2 / pypy2 (see
https://github.com/shlomif/project-euler/blob/master/project-euler/581/euler_581_v2.py
) and later made a straightforward translation of it to C++ v14 using the
standard template library (STL) here -
https://github.com/shlomif/project-euler/blob/master/project-euler/581/euler_581_v2.cpp .

Now, the pypy2 version was slow, and didn't finish within several minutes and
so I concluded that perhaps my algorithm was too slow. But the C++ version was
much faster and finished within a minute.

Can anyone tell me how I can improve the performance of the python code
(without changing the underlying algorithm)? Note that I tried converting the
code to use heapq - see
https://github.com/shlomif/project-euler/blob/master/project-euler/581/euler_581_v4_with_heapq.py
but it ended up consuming too much RAM (over 50% of my 8 GB of RAM) before
finishing.

Shabbath Shalom!

Regards,

	Shlomi Fish

-- 
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
List of Text Editors and IDEs - http://shlom.in/IDEs

There is an IGLU Cabal, but its only purpose is to deny the existence of an
IGLU Cabal.
    — Martha Greenberg

Please reply to list if it's a mailing list post - http://shlom.in/reply .


More information about the Python-il mailing list