Entry

Sieves / List size hints

Jul 5th, 2000 09:59
Nathan Wallace, unknown unknown, Hans Nowak, Snippet 38, Christian Tismer

"""
Packages: maths.sieves;basic_datatypes.lists
"""

"""
> 
> Oh, goody, speed tests again!
> 
> 1)  if not p: continue  is fairly expensive compared to if p: dosomething
> 2) roll the (q-3)/2 into the xrange parameters and you should save some
> processing power
> 3) not sure about the adding lists versus inserting, didn't seem to hurt
> 4) results seem to be identical

Well, I knew, leaving things more readable :)

Here my results:
tissieve1 78498 8.889
tissieve2 78498 4.353
tissieve3 78498 4.309
mcfsieve2 78498 6.753
timsieve 78498 6.627

In fact, your hint to do an insert instead of
list add, lead tissieve3 perform marginally better.

You missed to see that doing the insert *after* the filter
is more efficient since the list is much smaller.
It could also make sense to shuffle the first
list elements a little to include the 2 without an insert.
"""

def tissieve3(n):
    candidates = range(3, n+1, 2)
    sq = int(n**0.5)
    for p in candidates:
        if p and p<sq: 
          for q in xrange(((p*p)-3)/2, ( (n+1)-3)/2, p):\
            candidates[q] = 0
    candidates = filter(None, candidates)
    candidates.insert(0, 2)
    return candidates

"""
Two things made me win here:

1) The test against sq pays off
2) that tiny little backslash helps :-)

I also tried to remove multiples of 3, but the
extra complications produced too much code,
and the win (saving loop cycles) can be only 1/6.
The xrange loop seems to be not beatable by
other iterative approaches.
"""