Увеличивает скорость продукта itertools

Я использую itertools.product для генерации всех возможных вариаций из 4 элементов длины 13. 4 и 13 могут быть произвольными, но, как есть, я получаю 4 ^ 13 результатов, что очень много. Мне нужен результат как массив Numpy и в настоящее время выполняем следующие действия:

c = it.product([1,-1,np.complex(0,1), np.complex(0,-1)], repeat=length) sendbuf = np.array(list(c)) 

С некоторым простейшим кодом профилирования между ними, похоже, первая строка довольно мгновенная, тогда как преобразование в список, а затем массив Numpy занимает около 3 часов. Есть ли способ сделать это быстрее? Вероятно, это действительно очевидно, что я не замечаю.

Благодаря!

6 Solutions collect form web for “Увеличивает скорость продукта itertools”

Эквивалент NumPy itertools.product()numpy.indices() , но он будет получать только произведение диапазонов формы 0, …, k-1:

 numpy.rollaxis(numpy.indices((2, 3, 3)), 0, 4) array([[[[0, 0, 0], [0, 0, 1], [0, 0, 2]], [[0, 1, 0], [0, 1, 1], [0, 1, 2]], [[0, 2, 0], [0, 2, 1], [0, 2, 2]]], [[[1, 0, 0], [1, 0, 1], [1, 0, 2]], [[1, 1, 0], [1, 1, 1], [1, 1, 2]], [[1, 2, 0], [1, 2, 1], [1, 2, 2]]]]) 

В вашем специальном случае вы можете использовать

 a = numpy.indices((4,)*13) b = 1j ** numpy.rollaxis(a, 0, 14) 

(Это не будет работать на 32-битной системе, потому что массив будет большим. Экстраполируя размер, который я могу проверить, он должен работать менее чем за минуту.)

EIDT: Просто упомянуть об этом: вызов numpy.rollaxis() более или менее косметический, чтобы получить тот же результат, что и itertools.product() . Если вы не заботитесь о порядке индексов, вы можете просто опустить его (но это все равно дешево, если у вас нет никаких последующих действий, которые преобразуют ваш массив в смежный массив).

EDIT2: Чтобы получить точный аналог

 numpy.array(list(itertools.product(some_list, repeat=some_length))) 

вы можете использовать

 numpy.array(some_list)[numpy.rollaxis( numpy.indices((len(some_list),) * some_length), 0, some_length + 1) .reshape(-1, some_length)] 

Это стало совершенно нечитаемым – просто скажите, нужно ли мне это объяснять дальше 🙂

Первая строка кажется мгновенной, поскольку фактическая операция не выполняется. Объект-генератор только что сконструирован и только тогда, когда вы выполняете его через операцию. Как вы сказали, вы получаете номера 4^13 = 67108864 , все они вычисляются и становятся доступными во время вашего вызова list . Я вижу, что np.array принимает только список или кортеж, поэтому вы можете попробовать создать кортеж из своего итератора и передать его np.array, чтобы увидеть, есть ли разница в производительности, и это не влияет на общую производительность вашей программы , Это можно определить, только пытаясь использовать ваш файл, хотя есть некоторые моменты, которые говорят, что кортеж немного быстрее.

Чтобы попробовать с кортежем, вместо списка просто сделайте

 sendbuf = np.array(tuple(c)) 

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

 numpy.fromiter(c, count=…) # Using count also speeds things up, but it's optional 

С помощью этой функции сначала выделяется массив NumPy, а затем инициализируется элемент за элементом, без необходимости проходить дополнительный шаг построения списка.

PS : fromiter() не обрабатывает кортежи, возвращаемые product() , поэтому пока это не может быть решением. Если fromiter() обрабатывал dtype=object , это должно работать.

PPS : Как отметил Джо Кингтон, это может быть сделано для работы, помещая кортежи в структурированный массив . Однако, похоже, это не всегда ускоряет работу.

Вы можете попробовать совершенно другой подход: сначала создайте пустой массив желаемого размера:

 result = np.empty((4**length, length), dtype=complex) 

затем используйте способности NumPy для нарезки, чтобы заполнить массив самостоятельно:

 # Set up of the last "digit": result[::4, length-1] = 1 result[1::4, length-1] = -1 result[2::4, length-1] = 1j result[3::4, length-1] = -1j 

Вы можете делать подобные вещи для других «цифр» (т. Е. Элементов результата [:, 2], результата [:, 1] и результата [:, 0]). Все это, безусловно, можно было бы ввести в цикл, который итерации над каждой цифрой.

Транспонирование всей операции ( np.empty((length, 4**length)…) ) стоит попробовать, так как это может привести к увеличению скорости (благодаря лучшему использованию кеша памяти).

Вероятно, не оптимизирован, но гораздо меньше зависит от преобразований типа python:

 ints = [1,2,3,4] repeat = 3 def prod(ints, repeat): w = repeat l = len(ints) h = l**repeat ints = np.array(ints) A = np.empty((h,w), dtype=int) rng = np.arange(h) for i in range(w): x = l**i idx = np.mod(rng,l*x)/x A[:,i] = ints[idx] return A 

Пусть numpy.meshgrid выполняет всю работу:

 length = 13 x = [1, -1, 1j, -1j] mesh = numpy.meshgrid(*([x] * length)) result = numpy.vstack([y.flat for y in mesh]).T 

на моем ноутбуке требуется ~ 2 минуты

Python - лучший язык программирования в мире.