Numpy/Python: Эффективная матрица как умножение декартово произведение входной матрицы

Question

Задача:

вход является (I, J) -матрица М. Требуемый выход представляет собой (я^п, J^п) матрица K, где n - количество принятых изделий. Многословный способ, чтобы получить желаемый результат заключается в следующем

• Генерировать все массивы строк п перестановок I (в общей сложности I ** N, N-массивы)
• генерировать все массивы п перестановок столбцов J (всего j ** n n-массивы)
• K [i, j] = m [I [0], J [0]] * ... * m [I [n], J [n]] для всех n в диапазоне (LEN (J))

простой способ я сделал это путем создания списка меток всех п-перестановок чисел в диапазоне (LEN (np.shape (м) [0])) и range (len (np.shape (m) [1])) для строк и столбцов соответственно. Впоследствии вы можете их размножать, как в последней указанной выше отметке. Это, однако, нецелесообразно для больших входных матриц - поэтому я ищу способы оптимизации вышеизложенного. Спасибо заранее

Пример:

Входной

np.array ([[1,2,3], [4,5,6]])

Выход для n = 3

[[1. 2. 3. 2. 4. 6. 3. 6. 9. 2. 4. 6. 4. 8. 12. 6. 12. 18. 3 6. 9. 6. 12. 18. 9. 18. 27.]

[4. 5. 6. 8. 10. 12. 12. 15. 18. 8. 10. 12. 16. 20. 24. 24. 30. 36. 12. 15. 18. 24. 30. 36. 36. 45. 54.]

[4. 8. 12. 5. 10. 15. 6. 12. 18. 8. 16. 24. 10. 20. 30. 12. 24. 36. 12. 24. 36. 15. 30. 45. 18. 36. 54.]

[16. 20. 24. 20. 25. 30. 24 30. 36. 32. 40. 48. 40. 50. 60. 48. 60. 72. 48. 60. 72. 60. 75. 90. 72. 90. 108.]

[4. 8. 12. 8. 16. 24. 12. 24. 36. 5. 10. 15. 10. 20. 30. 15. 30. 45. 6. 12. 18. 12. 24. 36. 18. 36. 54.]

[16. 20. 24. 32. 40. 48. 48. 60. 72. 20. 25. 30. 40. 50. 60. 60. 75. 90. 24. 30. 36. 48. 60. 72. 72. 90. 108.]

[16. 32. 48. 20. 40. 60. 24. 48. 72. 20. 40. 60 . 25. 50. 75. 30. 60. 90. 24. 48. 72. 30. 60. 90. 36. 72. 108.]

[64. 80. 96. 80. 100. 120 96. 120. 144. 80. 100. 120. 100. 125. 150. 120. 150. 180. 96. 120. 144. 120. 150. 180. 144. 180. 216.]]

Частичное решение:

Лучшее, что я нашел это функция для создания декартово произведение матриц, предложенный здесь: https://stackoverflow.com/a/1235363/4003747 Проблема заключается в том, что выход не матрица, а массив массивы. Умножение элемента каждого массива дает значения, за которыми я следую, но неупорядоченно. Я пробовал какое-то время, но я понятия не имею, как разумно переупорядочить их.

Неэффективное решения при п = 3:

import numpy as np 
import itertools 

m=np.array([[1,2,3],[4,5,6]]) 

def f(m): 
    labels_i = [list(p) for p in itertools.product(range(np.shape(m)[0]),repeat=3)] 
    labels_j = [list(p) for p in itertools.product(range(np.shape(m)[1]),repeat=3)] 


    out = np.zeros([len(labels_i),len(labels_j)]) 
    for i in range(len(labels_i)): 
     for j in range(len(labels_j)): 
      out[i,j] = m[labels_i[i][0],labels_j[j][0]] * m[labels_i[i][1],labels_j[j][1]] * m[labels_i[i][2],labels_j[j][2]] 
    return out 

Answer 1

Вот Векторизованный подход с использованием комбинации broadcasting и linear indexing -

from itertools import product 

# Get input array's shape 
r,c = A.shape 

# Setup arrays corresponding to labels i and j 
arr_i = np.array(list(product(range(r), repeat=n))) 
arr_j = np.array(list(product(range(c), repeat=n))) 

# Use linear indexing with ".ravel()" to extract elements. 
# Perform elementwise product along the rows for the final output 
out = A.ravel()[(arr_i*c)[:,None,:] + arr_j].prod(2) 

время выполнение тестовой и проверка вывода -

In [167]: # Inputs   
    ...: n = 4 
    ...: A = np.array([[1,2,3],[4,5,6]]) 
    ...: 
    ...: def f(m): 
    ...: labels_i = [list(p) for p in product(range(np.shape(m)[0]),repeat=n)] 
    ...: labels_j = [list(p) for p in product(range(np.shape(m)[1]),repeat=n)] 
    ...: 
    ...: out = np.zeros([len(labels_i),len(labels_j)]) 
    ...: for i in range(len(labels_i)): 
    ...:  for j in range(len(labels_j)): 
    ...:   out[i,j] = m[labels_i[i][0],labels_j[j][0]] \ 
    ...:     * m[labels_i[i][1],labels_j[j][1]] \ 
    ...:     * m[labels_i[i][2],labels_j[j][2]] \ 
    ...:     * m[labels_i[i][3],labels_j[j][3]] 
    ...: return out 
    ...: 
    ...: def f_vectorized(A,n): 
    ...: r,c = A.shape 
    ...: arr_i = np.array(list(product(range(r), repeat=n))) 
    ...: arr_j = np.array(list(product(range(c), repeat=n))) 
    ...: return A.ravel()[(arr_i*c)[:,None,:] + arr_j].prod(2) 
    ...: 

In [168]: np.allclose(f_vectorized(A,n),f(A)) 
Out[168]: True 

In [169]: %timeit f(A) 
100 loops, best of 3: 2.37 ms per loop 

In [170]: %timeit f_vectorized(A,n) 
1000 loops, best of 3: 202 µs per loop 

Answer 2

это должно работать:

import numpy as np 
import itertools 

m=np.array([[1,2,3],[4,5,6]]) 
n=3 # change your n here 


def f(m): 
    labels_i = [list(p) for p in itertools.product(range(np.shape(m)[0]),repeat=n)] 
    labels_j = [list(p) for p in itertools.product(range(np.shape(m)[1]),repeat=n)] 


    out = np.zeros([len(labels_i),len(labels_j)]) 
    for i in range(len(labels_i)): 
     for j in range(len(labels_j)): 
      out[i,j] = np.prod([m[labels_i[i][k],labels_j[j][k]] for k in range(n)]) 
    return out