Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
615 views
in Technique[技术] by (71.8m points)

python - Why do I get a MemoryError with itertools.product?

I would expect the following snippet to give me an iterator yielding pairs from the Cartesian product of the two input iterables:

$ python
Python 2.7.1+ (r271:86832, Apr 11 2011, 18:13:53) 
[GCC 4.5.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import itertools
>>> one = xrange(0, 10**9)
>>> two = (1,)
>>> prods = itertools.product(one, two)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError

Instead, I get a MemoryError. But I thought that itertools.product did not store the intermediate results in memory, so what's causing the MemoryError?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

It doesn't store intermediate results, but it has to store the input values because each of those might be needed several times for several output values.

Since you can only iterate once over an iterator, product cannot be implemented equivalent to this:

def prod(a, b):
  for x in a:
    for y in b:
       yield (x, y)

If here b is an iterator, it will be exhausted after the first iteration of the outer loop and no more elements will be produced in subsequent executions of for y in b.

product works around this problem by storing all the elements that are produced by b, so that they can be used repeatedly:

def prod(a, b):
  b_ = tuple(b)  # create tuple with all the elements produced by b
  for x in a:
    for y in b_:
       yield (x, y)

In fact, product tries to store the elements produced by all the iterables it is given, even though that could be avoided for its first parameter. The function only needs to walk over the first iterable once, so it wouldn't have to cache those values. But it tries to do anyway, which leads to the MemoryError you see.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...