7
\$\begingroup\$

I recently started playing with Python. What can I do better?

def sieve_of_sundaram(limit):
    new_limit = (limit - 1) // 2
    boolean_list = [True] * new_limit;
    i = 1
    j = i
    while (i + j + 2 * i * j <= new_limit):
        while (i + j + 2 * i * j <= new_limit):
            boolean_list[2 * i * j + i + j - 1] = False
            j += 1
        i += 1
        j = i
    primes = [2]
    for i in range(0, new_limit):
        if boolean_list[i]:
            primes.append(i * 2 + 3)
    return primes

def sieve_of_eratosthenes(limit):
    boolean_list = [True] * limit;
    for i in range(2, limit):
        if i * i > limit:
            break
        while boolean_list[i - 1] == False:
            i += 1
        for j in range(i * i, limit + 1, i):
            boolean_list[j - 1] = False
    primes = []
    for i in range(1, limit):
        if boolean_list[i] == True:
            primes.append(i + 1)
    return primes


i = 100
sundaram_primes = sieve_of_sundaram(i)
eratosthenes_primes = sieve_of_eratosthenes(i)

print("Sundaram primes count: ", len(sundaram_primes))
print(sundaram_primes)
print("Eratosthenes primes count: ", len(eratosthenes_primes))
print(eratosthenes_primes)
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review. FYI, there is no reason to add irrelevant filler text like "lorem ipsum", just explain what the code does and leave it at that. In this case it's pretty self-explaining so very little is needed. \$\endgroup\$ – Phrancis Oct 22 '17 at 16:05
  • \$\begingroup\$ @Phrancis I couldn't post it because "most of the post is code". \$\endgroup\$ – user264307 Oct 22 '17 at 16:12
  • \$\begingroup\$ Understood. I removed the extra text and moved the text to the top and had no problems. Anyways, I hope you get great answers! \$\endgroup\$ – Phrancis Oct 22 '17 at 16:23
5
\$\begingroup\$

There are some curious inconsistencies between the Eratosthenes and Sundaram code.

    for i in range(2, limit):
        if i * i > limit:
            break

is IMO more Pythonic than

    i = 1
    j = i
    while (i + j + 2 * i * j <= new_limit):
        ...
        i += 1
        j = i

We can refactor the second into something similar to the first: firstly, observe that there's no need to repeat the assignment j = i:

    i = 1
    while (i + i + 2 * i * i <= new_limit):
        j = i
        ...
        i += 1

Then simplify algebraically:

    i = 1
    while (2 * i * (i + 1) <= new_limit):
        j = i
        ...
        i += 1

And finally replace with range:

    for i in range(1, new_limit + 1):
        if 2 * i * (i + 1) > new_limit:
            break
        j = i
        ...

As noted by Janne, you can then refactor the inner loop to also use range...


The indexing of the arrays in both is a bit tricky. Are the maintenance costs worth saving four bytes of memory? If so, would it at least be worth leaving a comment to explain why (for example) the primes recovered by the Sundaram sieve are 2 * i + 3 instead of the 2 * i + 1 which someone who just read the Wikipedia page would expect?


    primes = [2]
    for i in range(0, new_limit):
        if boolean_list[i]:
            primes.append(i * 2 + 3)

can be written as a one-liner using something called list comprehensions. This is something that's worth learning because it's very common style for Python.

    primes = [2] + [i * 2 + 3 for i in range(0, new_limit) if boolean_list[i]]

        if boolean_list[i]:

...

        if boolean_list[i] == True:

What's the difference?

Answer: the first one is better style. x == True should be rewritten as x ; and y == False or y != True should be rewritten as not y. With good variable names this usually gives a very natural reading.


On the subject of names: boolean_list tells me the type, but what I care about is the meaning. For Eratosthenes that's easy: a True means that the index is a prime, and a False means that it's a composite number, so is_prime is a good name. For Sundaram the exact interpretation is a bit trickier, but is_prime would still work.

\$\endgroup\$
  • 1
    \$\begingroup\$ for i in range(2, limit): followed by if i * i > limit: is horrible IMHO. Why not just calculate the correct limit directly? \$\endgroup\$ – Eric Duminil Jan 20 '18 at 22:33
4
\$\begingroup\$
  • sieve_of_eratosthenes has an inner while loop that increments i. This is not useful because it will not advance the outer for loop, and you end up looping over the same values multiple times.
  • sieve_of_sundaram repeats the expression i + j + 2 * i * j. You could instead use for loops with an appropriate step size.
\$\endgroup\$
  • \$\begingroup\$ Hey! Thanks for the feedback, i found it very useful. Actually I managed to improve the running time of of both algorithms by a lot. Particularly proud of Sundaram's sieve. Check it out \$\endgroup\$ – user264307 Oct 25 '17 at 18:14
2
\$\begingroup\$

Theory

def sieve_of_eratosthenes(limit):
    boolean_list = [True] * limit;
  • There's no need for ;.
  • It might be easier to add one element to the list and use 1-based indexing.

    for i in range(2, limit):
        if i * i > limit:
            break
  • There's no need for this check. It will be integrated into your range later. If i * i is larger than limit, range(i * i, limit + 1, i) is empty and nothing happens.

        while boolean_list[i - 1] == False:
            i += 1
  • You also don't need this loop, you already have for i above.

        for j in range(i * i, limit + 1, i):
            boolean_list[j - 1] = False
  • This looks fine. With 1-based indexing, it becomes boolean_list[j] = False

    primes = []
    for i in range(1, limit):
        if boolean_list[i] == True:
            primes.append(i + 1)
  • You already iterated over the whole range earlier. You could append the primes directly in the above loop.

Code

Here's the refactored code. It's much shorter and 3 times faster than your original code for the primes below 1 million:

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    primes = []
    for i in range(2, limit + 1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    return primes

It's even shorter if you return a generator:

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    for i in range(2, limit + 1):
        if is_prime[i]:
            yield i
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
\$\endgroup\$
  • \$\begingroup\$ It's worth noting that if you use numpy for this, you use a fraction of the memory, and get rid of some of the loops. The two things that change are isprime = np.ones(k,dtype=np.bool) and isprime[np.arange(i * i, limit + 1, i)]=False. The result will be significantly faster. \$\endgroup\$ – Oscar Smith Jan 20 '18 at 23:11
  • \$\begingroup\$ @OscarSmith: Interesting. I might be missing something, but this code was actually slower than the pure python implementation (not taking import into account, obviously). \$\endgroup\$ – Eric Duminil Jan 20 '18 at 23:21
  • \$\begingroup\$ how high are you testing? at limit=10**7, it is about 2x as fast for me. \$\endgroup\$ – Oscar Smith Jan 20 '18 at 23:43
  • \$\begingroup\$ @EricDuminil I have implemented sieve of Sundaram for LeetCode Count Primes problem. My pure Python 3 solution is ~ 130ms. What is your best timing? \$\endgroup\$ – JulStrat Jan 21 '18 at 11:21
  • \$\begingroup\$ @JulStrat: I didn't look at Sundaram yet. Will try to do so this evening. \$\endgroup\$ – Eric Duminil Jan 21 '18 at 11:27
1
\$\begingroup\$

I suggest you some performance improvements.

  1. Sieve of Sundaram can be implemented using only addition.

  2. Rewrite inner for loop as slice assignment.

  3. Use list comprehension in last step.

  4. For sieve you can use list of integers or bytearray.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.