List comprehension has excruciatingly slow load time than regular code that does the same thing-CodePudding

I have a list comprehension that prints all the prime numbers from 1 to 1000. For some strange reason, my list comprehension takes 1:46 to load in the terminal. I find this very weird because when I write the same code out normally, it loads instantaneously.

Here is my comprehension: print([x for x in range(2, 1000) if x not in [y * z for y in range(2, 1001) for z in range(2, 1001)if y * z < 1000]]) As you can see, it makes a list of number from 2 and 1000 and prints the (prime) ones that are not in the list of composite numbers under 1000. When I run this, it correctly outputs, but takes ages on every computer I try. I thought maybe my code was just erroneous. However, when I isolate the [y * z for y in range(2, 1001) for z in range(2, 1001)if y * z < 1000] line, there is no delay in displaying the composites. And when I generate the regular list of number for comparison, there is also no lag. It's just when I use the "not in" operator that the comprehension takes ridiculously long to print them.

I thought that perhaps the not in comparison was being extra slow. But to my frustration, I noticed that when I wrote out the comparison part of the code normally and not in comprehension, there was absolutely no delay. See this:

x = [y * z for y in range(2, 1001) for z in range(2, 1001)if y * z < 1000]
newlist = []
for z in range(2, 1000):
  if z not in x:
    newlist.append(z)
print(newlist)

As you can see, I slapped the composite list into a variable and did the if statement and loop regularly. If x wasn't in the list, then it was added to a new list. Achieving the same goal of my list comprehension. I was wondering, if there was a solution to my list comprehension being so slow. The logic matches my original comprehension so why is it taking longer in comprehension format if it is essentially the same?

Please try to not add any additional features to my code, I'm to trying to use list comprehension and only list comprehension.

CodePudding user response：

The inner list is recreated on every iteration of x. Simply separate it out:

composites = [y*z for y in range(2, 1001) for z in range(2, 1001) if y*z < 1000]
[x for x in range(2, 1000) if x not in composites]

By the way, if you make composites a set, lookups (in and not in) are much faster (O(1) instead of O(n), where n=len(composites)).

composites = {y*z for y ...}