3

I have the following program:

def main():
    print "Running"
    primes = sieve(100000)
    print "Sieve is done"

def sieve(n):
    print "starting sieve"
    primes = []
    times = 0

    numbers = range(2, n):
    print "sieve array filled"

    while len(numbers) > 0:
        current = numbers[0]
        primes.append(current)
        numbers.remove(current)

        times = times + 1
        if (times % 10 == 0):
            print str(times) + "th prime is " + str(current)

        # Remove every multiple
        for i in numbers:
            if (i % current == 0):
                numbers.remove(i)

When finding all the primes up to a large number (lets say ten thousand) I wanted to be able to see how far along the program is by looking at the output. So I decided I would print out every tenth prime. However, when printing it out, it waits until the very end of the program to print it. I added in sys.stdout.flush() right after the print statement but it didn't make any difference. I then tried running the script with python -u <file name> and still, no difference at all.

This is what I get as output:

Running
starting sieve
sieve array filled

Then after about a minute the rest of the output is shown at once.

Why can't I turn the buffer off? I'm trying to modify the code as little as possible.

Improve this question
10
  • 2
    Not answering the question, but you should just use numbers = range(2,n) rather than doing that append thing. Commented Nov 28, 2012 at 23:50
  • You are completely right. I had other code inside the for i in range(2, n) loop but I removed it earlier, but I hadn't noticed until now that I could simplify it even further. Good eye! Commented Nov 28, 2012 at 23:54
  • 2
    You are removing elements from the numbers list while iterating over it. This could cause unseen problems. Not sure if it's related to this problem. Also the print statement hardly does any buffering at all, which means it just isn't ever executed. Commented Nov 28, 2012 at 23:56
  • 4
    That is the craziest sieve I have ever seen. Eratosthenes is turning in his grave! Commented Nov 28, 2012 at 23:59
  • 1
    You probably shouldn't be .removeing elements from numbers while you iterate over it. Commented Nov 29, 2012 at 0:26

3 Answers 3

Reset to default
3

Having tested a few things, I'm not sure that your problem is actually the output buffering, it's just the behaviour of your algorithm. Try printing current near the top of your while loop, and you'll see that the early numbers take a very long time to work through, and then as numbers gets shorter and shorter, each new value of current gets much faster to process and you start seeing the primes pop up.

Try:

while len(numbers) > 0:
    current = numbers[0]
    print current
    primes.append(current)
    numbers.remove(current)
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

The output buffering is definitely an issue though. When running the sieve with one million, for example, I don't see any output (which, as you said, could be the cause of the logarithmic nature of the for loop). However, when running a number like ten thousand, that still takes a about a minute to execute, and it is clear that it does not print until after it is completely finished executing. Whatever the size of the data set, it still waits until the last minute, and then everything is printed at once.
I think the main problem is that when current == 2, everything takes a very, very long time, since you're removing all the even numbers between 2 and your limit. Seeing it jump from current == 2 to basically being finished might make you think it's buffering, but I'm not sure that's true
I modified the code to print out every prime number instead of every 10th, and then set the sieve to find all prime numbers less than 50,000, and I noticed what you said: the first one prints immediately, the second one a long time afterward, and then all the ones after print almost immediately. I had thought before that it was an output buffering issue because I hadn't realized how quickly it speeds up (so I thought it was all being saved until the end, when really it was printing at once).
2

The reason this is so slow is the loop where you remove elements from numbers:

    # Remove every multiple
    for i in numbers:
        if (i % current == 0):
            numbers.remove(i)

Every time you remove a number, Python has to go and shift all the elements after that number that you removed back one place. Every delete is O(n)*, and you do O(n) deletes, so each iteration of this step takes O(n^2) time.

If you replace this with a list comprehension, then Python builds a new list from the old list -- no moving involved -- which is an O(n) operation. Here's the way I would do that step: 

    # Remove every multiple
    numbers = [i for i in numbers if (i % current) != 0]

With this change, your code runs way faster for me. It's done in under 5 seconds, and there's no output buffering problem.

*There's a nice table of time complexities for Python list operations here.

Improve this answer

1 Comment

I wasn't sure which answer to choose here. I chose Marius's answer because it was what he said a while ago that made me realize that my issue wasn't being caused by output buffering. However, thank you very much for the link and for telling me about list comprehensions (I'm new to Python, having used PHP for a long time, which doesn't have list comprehensions).
0

Try using sys.stdout.write instead of print. This should work better with sys.stdout.flush.

Improve this answer

1 Comment

I've already tried; no dice.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.