Tại sao tôi nhận được một MemoryError với itertools.product?

Question

Tôi mong chờ đoạn sau đây để cho tôi một iterator năng suất cặp từ sản phẩm Descartes của hai iterables đầu vào:

$ 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 

Thay vào đó, tôi nhận được một MemoryError. Nhưng tôi nghĩ rằng itertools.product không lưu trữ kết quả trung gian trong bộ nhớ, vì vậy điều gì gây ra MemoryError?

Answer 1

Không lưu trữ các kết quả trung gian , nhưng phải lưu trữ các giá trị đầu vào vì mỗi giá trị này có thể cần nhiều lần cho một số giá trị đầu ra.

Vì bạn chỉ có thể lặp một lần trong một iterator, product không thể được thực hiện tương đương như sau:

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

Nếu đây b là một iterator, nó sẽ bị cạn kiệt sau phiên đầu tiên của vòng ngoài và không có nhiều yếu tố hơn sẽ được sản xuất trong các lần thực hiện tiếp theo là for y in b.

product công trình xung quanh vấn đề này bằng cách lưu trữ tất cả các yếu tố đó được sản xuất bởi b, do đó chúng có thể được sử dụng nhiều lần:

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) 

Trong thực tế, product cố gắng để lưu trữ các yếu tố sản xuất bởi tất cả các iterables nó được đưa ra, mặc dù điều đó có thể tránh được cho tham số đầu tiên của nó. Hàm này chỉ cần đi qua lần lặp đầu tiên một lần, vì vậy nó sẽ không phải cache các giá trị đó. Nhưng nó vẫn cố gắng làm, dẫn đến số MemoryError bạn thấy.

Answer 2

itertools.product không lưu trữ các sản phẩm trung gian trong bộ nhớ, nhưng nó lưu trữ tuple phiên bản của trình lặp vòng ban đầu.

Điều này có thể được nhìn thấy bằng cách xem nguồn của mô-đun itertools. Nó nằm trong tập tin Modules/itertoolsmodule.c trong bản phân phối nguồn Python 2.7.2. Ở đó chúng ta tìm thấy, trong hàm product_new (về cơ bản các nhà xây dựng cho các đối tượng product) từ dòng 1828 trở đi:

for (i=0; i < nargs ; ++i) { 
    PyObject *item = PyTuple_GET_ITEM(args, i); 
    PyObject *pool = PySequence_Tuple(item); 
    if (pool == NULL) 
     goto error; 
    PyTuple_SET_ITEM(pools, i, pool); 
    indices[i] = 0; 
} 

Trong mã đó, args là những lập luận để product. Trong dòng thứ ba của đoạn mã này, đối số thứđược chuyển đổi thành một bộ dữ liệu. Do đó, mã cố gắng chuyển đổi trình lặp của bạn xrange(0, 10**9) thành một bộ tuple, dẫn đến một số MemoryError.

Tôi không chắc chắn lý do tại sao itertools.product hoạt động như thế này. Thay vì lưu trữ mỗi iterator đầu vào như một bộ túp, nó đủ để lưu trữ mục cuối cùng được trả về từ mỗi trình lặp. (EDIT: Xem câu trả lời của sth vì lý do)

Answer 3

Tôi nghĩ rằng vấn đề có thể là xrange trả về loại đối tượng đặc biệt của riêng nó.

xrange được thực hiện theo cách (như danh sách) mà bạn có thể lặp lại đối tượng nhiều lần, trong khi bạn có thể lặp qua đối tượng bộ tạo thông thường chỉ một lần. Vì vậy, có lẽ một cái gì đó từ chức năng này chịu trách nhiệm về lỗi bộ nhớ.