Декартово произведение без повторного использования ⇐ Python

[Anonymous]

Например, у меня есть два генератора, генерирующих данные:

Код: Выделить всё

def xs():
yield [1, 2]
yield [3, 4]

def ys():
yield [5, 6]
yield [7, 8]

И я хочу обработать все возможные пары (x,y):

Код: Выделить всё

process([1, 2], [5, 6])
process([1, 2], [7, 8])
process([3, 4], [5, 6])
process([3, 4], [7, 8])

Я могу это сделать:

Код: Выделить всё

from itertools import product

for x, y in product(xs(), ys()):
process(x, y)

Вот проблема: процесс может изменить данные, например так:

Код: Выделить всё

def process(x, y):
print(f'process({x}, {y})')
x.pop()
y.pop()

Тогда происходит следующее:

Код: Выделить всё

process([1, 2], [5, 6])
process([1], [7, 8])
process([3, 4], [5])
process([3], [7])

Это потому, что product(xs(), ys()) создает все x и y только один раз и повторно использует их. Таким образом, более ранние вызовы процесса влияют на данные для последующих вызовов. Мне нужно избегать повторного использования.
Это немного лучше:

Код: Выделить всё

for x in xs():
for y in ys():
process(x, y)

При этом каждый x используется повторно, но каждый y создается заново, что приводит к следующему:

Код: Выделить всё

process([1, 2], [5, 6])
process([1], [7, 8])
process([3, 4], [5, 6])
process([3], [7, 8])

Один из способов избежать повторного использования каждого x — всегда делать глубокую копию:

Код: Выделить всё

from copy import deepcopy

for x in xs():
for y in ys():
process(deepcopy(x), y)

Это обеспечивает желаемое поведение. Проблема в том, что глубокая копия может работать намного медленнее, чем генерация данных заново. Вот случаи, когда xs() и ys() дают 100 списков по 100 целых чисел (и процесс ничего не делает) с помощью трех вышеуказанных методов:

Код: Выделить всё

  0.6 ± 0.0 ms  using_product
3.1 ± 0.0 ms  nested_loops
404.7 ± 25.9 ms  with_deepcopy

Как мы можем всегда использовать свежий x и свежий y без глубокого копирования, чтобы это было намного быстрее? Должно быть возможно занять примерно вдвое больше времени, чем neged_loops, поскольку он уже генерирует половину всех значений заново.
Сценарий бенчмарка/тестирования:

Код: Выделить всё

def using_product(xs, ys, process):
for x, y in product(xs(), ys()):
process(x, y)

def nested_loops(xs, ys, process):
for x in xs():
for y in ys():
process(x, y)

def with_deepcopy(xs, ys, process):
for x in xs():
for y in ys():
process(deepcopy(x), y)

funcs = [
using_product,
nested_loops,
with_deepcopy,
]

from itertools import *
from copy import deepcopy
from timeit import timeit
from statistics import mean, stdev
import sys
import random

# The little example
def xs():
yield [1, 2]
yield [3, 4]
def ys():
yield [5, 6]
yield [7, 8]
def process(x, y):
print(f'process({x}, {y})')
x.pop()
y.pop()
for f in funcs:
print(f.__name__ + ':')
f(xs, ys, process)
print()

# Arguments for benchmark
def xs():
for _ in range(100):
yield [1] * 100
ys = xs
def process(x, y):
pass

# Run the benchmark
times = {f: [] for f in funcs}
def stats(f):
ts = [t * 1e3 for t in sorted(times[f])[:5]]
return f'{mean(ts):5.1f} ± {stdev(ts):3.1f} ms '
for _ in range(25):
random.shuffle(funcs)
for f in funcs:
t = timeit(lambda: f(xs, ys, process), number=1)
times[f].append(t)
for f in sorted(funcs, key=stats):
print(stats(f), f.__name__)

print('\nPython:', sys.version)

Попробуйте это онлайн!


Подробнее здесь: https://stackoverflow.com/questions/783 ... hout-reuse