Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ)

[George Sakkis]

On Jun 13, 1:12 pm, jzakiya <jzak... at gmail.com> wrote:

> The paper presents benchmarks with Ruby 1.9.0-1 (YARV).  I would love
> to see my various prime generators benchmarked with optimized
> implementations in other languages.  I'm hoping Python gurus will do
> better than I, though the methodology is very very simple, since all I
> do is additions, multiplications, and array reads/writes.

After playing a little with it, I managed to get a 32-47% improvement
on average for the pure Python version, and a 230-650% improvement
with an extra "import psyco; psyco.full()" (pasted at http://codepad.org/C2nQ8syr)
The changes are:

- Replaced range() with xrange()
- Replaced x**2 with x*x
- Replaced (a,b) = (c,d) with a=c; b=d
- Replaced generator expressions with list comprehensions. This was
the big one for letting psyco do its magic.

I also tried adding type declarations and running it through Cython
but the improvement was much less impressive than Psyco. I'm not a
Pyrex/Cython expert though so I may have missed something obvious.

George