1

I'm trying to build a sieve for project Euler solutions. I need primes up until about 100M, preferably with option to go much higher.

This implementation I have works fine, but is very slow:

class Primes:
__size = None
__sieve = []
__primes = []

def __init__(self, size):
    self.__size = size
    self.__sieve = [True] * size
    for x in range(2, size):
        if self.__sieve[x]:
            self.foundPrime(x);

def foundPrime(self, x):
    self.__primes.append(x)
    for duplicate in range(2 * x, self.__size, x):
        self.__sieve[duplicate] = False

For a sieve sized 100M, this initialization takes about 70 seconds on my fairly high-end computer. Does anyone know why? Because in Java and C# this took me about 1 second...

So, this post is different from other posts in that I do not want to know how to implement the algorithm, I want to understand why it is so slow in Python.

Some prints give me the information that about 50% of the time is spent on finding the first 100K primes.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Feamar
  • 21
  • 3
  • 2
    Possible duplicate of [Sieve of Eratosthenes - Finding Primes Python](https://stackoverflow.com/questions/3939660/sieve-of-eratosthenes-finding-primes-python) – user3483203 Jul 02 '18 at 11:07
  • 1
    Please write a clearer code without magic methods. A class is here useless. –  Jul 02 '18 at 11:07
  • Its not a duplicate of that post, since this is an implementation that works straightforward and works in different programming languages – Feamar Jul 02 '18 at 11:18
  • Is this actually slower than expected for Python? – harold Jul 02 '18 at 17:05
  • You're not making the usual mistake of implementing trial division and thinking it's a sieve. You *are* making the common mistake of declaring a bunch of class variables that you probably thought were instance variables, which will cause problems if you try to make two instances of this class. There are other trying-to-write-Java-in-Python problems (pointless name mangling, pointless class in general), but no major efficiency bugs. You're probably just running into the overhead of a JITless dynamic language implementation. – user2357112 Jul 02 '18 at 17:07
  • A list of 100M booleans also uses a *lot* more memory than you might expect. You might think it would be around 100 million bits or about 11 MB. It's really more like 2288 MB; each boolean value is a 24-byte Python object. (And I'm ignoring the 100M pointers in the list object *to* each of the boolean values.) – chepner Jul 02 '18 at 17:18
  • You might want to try implementing your algorithm with something like the [bitarray](https://pypi.org/project/bitarray/) module. – chepner Jul 02 '18 at 17:24
  • 1
    @chepner: CPython only ever has one `True` object and one `False` object; a list of booleans is a list of references to the two canonical boolean objects. You don't have to pay the 24-byte cost for every list cell. You *do* have to pay the pointer cost, though. – user2357112 Jul 02 '18 at 17:36
  • 1
    I'll blame the heat for forgetting that `True` and `False` are singletons. – chepner Jul 02 '18 at 17:42
  • For fun I ran it with pypy. With python 53 seconds, with pypy: 13. – Hack Saw Jul 02 '18 at 18:02
  • eliminating the function `foundPrime(self, x)` altogether and moving its code into `__init__(self, size)` should give *some* speedup. how much? please try it and tell us here. :) also, *always* measure the [ O Gℎ](http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth) to see the true algorithmic nature of your implementation. – Will Ness Jul 05 '18 at 11:18

1 Answers1

0

In various benchmarks, for what they are worth, Python is anywhere from the same speed to 50 times slower than Java, dependent on the problem. This is largely due to Python being interpreted, and Java being compiled (even if not to native). Ruby posts similar scores as Python.

Language design also gives Java and C# some advantages.

There are two good ways to speed things up, aside of more efficient Python methods: use pypy, which essentially bytecompiles your python, similar to Java, or write the critical sections in a faster language such as C, and call those routines from Python, a task which is actually pretty easy, assuming you are good with the fast language.

Hack Saw
  • 2,741
  • 1
  • 18
  • 33
  • Thank you for this answer! That is exactly what I wanted to know. – Feamar Jul 03 '18 at 07:21
  • Excellent! Glad I could help. Please consider "accepting" the answer by clicking the checkmark, to the left of the answer. – Hack Saw Jul 03 '18 at 12:51
  • I thought python and java were both typically compiled into their respective byte code intermediate languages. – President James K. Polk Jul 04 '18 at 00:51
  • Java was designed for this, and is complied into a sort of assembly code aimed at the VM. Python's byte compilation gives a very modest speedup, being more of a pre-parsing and tokenization. – Hack Saw Jul 04 '18 at 03:42
  • In addition, the JVM will apply a Just-In-Time compilation of 'hot' methods (run often) to machine-specific (optimized) assembly on the fly at runtime. – Mark Rotteveel Jul 05 '18 at 11:56