On 2/18/2013 4:55 PM, Chris Angelico wrote:
Running under Python 2.6, both your version and mine take about 90
seconds to run. But under Python 3.3, where (among other things)
range() yields values lazily, my version is significantly faster than
yours. BUT! Both versions, under 3.3, are significantly *slower* than
under 2.6. My first thought is that it's because Py2 has different
types for 'int' and 'long', and Py3 doesn't (effectively, everything's
a long), so I added an L suffix to every number and ran each of them
under 2.6 again. Seems that was the bulk of the difference, though not
all.
Pythonistas, does this count as a regression, or is Python
sufficiently "not a number crunching language" that we don't care?
Both. This brute-force algorithm is almost pure number crunching. This
is the sort of thing pypy and cython are good at speeding up. (I leave
out numpy only because it is not an array-oriented problem.)
I put a counter in the inner loop of my improved version the does
(3*n+1)//2 in one step and got 87 826 478 in 40 seconds (without the
counter). That is 2 million loops per second and each loop does a
compare, one or two integer ops, and creates and releases one or two ints.
If I were doing a lot of int crunching like this with CPython and were
building my own interpreter, I would greatly expand the range of
pre-allocated 'small' ints to avoid some of the repeated allocation and
de-allocation. On a multi-gibibyte machine, allocating up to 1000000
instead of 256 would be feasible.
As Ian noted, an intelligent algorithm in CPython can match pypy and is
in the ballpark of C, but is much easier to write in Python than C. It
is possible that Ian's code could be improved further. A pre-allocated
arrray + dict might be faster. Whenever an odd value is filled in,
powers of 2 times that value can also be.
--
Terry Jan Reedy
--
http://mail.python.org/mailman/listinfo/python-list
