Python 3.3 vs. MSDOS Basic
tjreedy at udel.edu
Tue Feb 19 06:28:38 CET 2013
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
> 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
More information about the Python-list