itertools.product: как улучшить производительность?

Question

Мне нужно создать продукт списка itertool.permutation генератора, и использует следующий код:

def iter_version(): 
    l = [itertools.permutations(range(10)) for _ in range(10)] 
    g = itertools.product(*l) 
    for i in g: 
    yield i 

Но этот код является слишком медленным. Это занимает 16 секунд на моем рабочем столе. cProfile ничего не показывает, кроме как сказать мне, что эта функция занимает 16 секунд.

Если я просто создать некоторые неработоспособную петлю так:

def for_loop(): 
    l = [itertools.permutations(range(10)) for _ in range(10)] 
    for i0 in l[0]: 
    for i1 in l[1]: 
     for i2 in l[2]: 
     for i3 in l[3]: 
      for i4 in l[4]: 
      for i5 in l[5]: 
       for i6 in l[6]: 
       for i7 in l[7]: 
        for i8 in l[8]: 
        for i9 in l[9]: 
         yield (i0, i1, i2, i3, i4, i5, i6, i7, i8, i9) 

Это работает почти мгновенно.

В моей ситуации список генераторов перестановок не является фиксированным размером, поэтому я не могу использовать версию цикла for.

Answer 1

С уважением, я не считаю, что ваш первый код занимает 16 секунд для запуска. Есть (3628800)^10 или 395940866122425193243875570782668457763038822400000000000000000000, элементы должны быть приведены. Я мог представить, что для вычисления 3628800 * 10 = 36288000 перестановок требуется некоторое время на одной системе. (Так как вы не показывают, как вы звоните iter_version, вы могли бы быть только после того, как next(iter_version()) или что-то, я думаю, хотя, если так есть гораздо более простые способы получить его ..)

Реальная разница между iter_version и for_loop состоит в том, что itertools.product не материализует декартово произведение, но оно делает сначала преобразовывает каждый из аргументов в список, и списки могут повторяться повторно. В for_loop вы исчерпываете свои итераторы, и поэтому вы не делаете почти столько работы.

Это, вероятно, легче увидеть с меньшим случае, скажем, (2,2) вместо (10,10):

>>> list(iter_version()) 
[((0, 1), (0, 1)), ((0, 1), (1, 0)), ((1, 0), (0, 1)), ((1, 0), (1, 0))] 
>>> list(for_loop()) 
[((0, 1), (0, 1)), ((0, 1), (1, 0))] 

Если добавить list вокруг itertools.permutations вызова, хотя, они становятся эквивалентными снова :

>>> list(for_loop_materialized_list()) 
[((0, 1), (0, 1)), ((0, 1), (1, 0)), ((1, 0), (0, 1)), ((1, 0), (1, 0))] 

Если вы действительно хотите, чтобы результаты iter_version, я предлагаю вам начать желающих что-то другое вместо. :-)

Answer 2

Как ответ @ DSM, itertools.product преобразует итерируемый в конкретную последовательность. Это можно подтвердить с http://bugs.python.org/issue10109

Чтобы решить эту проблему без преобразования итерации в список, я использовал эту функцию. Обратите внимание, что эта функция использует рекурсию, поэтому перед ее использованием.

def product(*args): 
    if len(args) == 1: 
     for i in args[0]: 
      yield [i] 
    else: 
     for i in args[0]: 
      for j in product(*args[1:]): 
       j.append(i) 
       yield j