Рекурсивная итерация по вложенному списку без Numpy - PullRequest
Новая
       14

Рекурсивная итерация по вложенному списку без Numpy

0 голосов
/ 27 мая 2018

Я бы хотел перебрать вложенный список.Я нашел решение только с Numpy (-> в другом случае), но мне было интересно, возможно ли это без Numpy.

import numpy as np

def matrix_mulitplication(A, B):
    n = A.shape[0]

    if n == 1:
        return A * B
    else:
        i = int(n / 2)

        C = np.zeros((n, n), dtype=np.int)

        C[:i, :i] = matrix_mulitplication(A[:i, :i], B[:i, :i]) + matrix_mulitplication(A[:i, i:], B[i:, :i])

        C[:i, i:] = matrix_mulitplication(A[:i, :i], B[:i, i:]) + matrix_mulitplication(A[:i, i:], B[i:, i:])

        C[i:, :i] = matrix_mulitplication(A[i:, :i], B[:i, :i]) + matrix_mulitplication(A[i:, i:], B[i:, :i])

        C[i:, i:] = matrix_mulitplication(A[i:, :i], B[:i, i:]) + matrix_mulitplication(A[i:, i:], B[i:, i:])

        return C

x = np.array([[1, 2], [3, 4]])
y = np.array([[1, 2], [3, 4]])

print(matrix_mulitplication(x, y))

Вывод: 

[[ 7 10]
 [15 22]]

Моя идея для первого случая нарезки: 

c_one = [C[i][0:int(len(C) / 2)] for i in range(0,int(len(C) / 2))]

Ответы [ 2 ]

0 голосов
/ 27 мая 2018

Попытка скопировать ваше подразделение nxn.Я использовал вспомогательную функцию blk для репликации среза массива 2d: 

import numpy as np

def matrix_mulitplication(A, B):
    def blk(x,i1,i2):
        return [row[i2] for row in x[i1]]

    n = len(A) # A.shape[0]

    if n == 1:
        #print(A)
        return A[0][0] * B[0][0]
    else:
        i = int(n / 2)
        i1, i2 = slice(None,i), slice(i,None)
        #C = np.zeros((n, n), dtype=np.int)
        C1 = matrix_mulitplication(blk(A, i1, i1), blk(B,i1,i1)) +\
             matrix_mulitplication(blk(A, i1, i2), blk(B,i2,i1))

        C2 = matrix_mulitplication(blk(A, i1, i1), blk(B,i1,i2)) +\
             matrix_mulitplication(blk(A, i1, i2), blk(B,i2,i2))

        C3 = matrix_mulitplication(blk(A, i2, i1), blk(B,i1,i1)) +\
             matrix_mulitplication(blk(A, i2, i2), blk(B,i2,i1))

        C4 = matrix_mulitplication(blk(A, i2, i1), blk(B,i1,i2)) +\
             matrix_mulitplication(blk(A, i2, i2), blk(B,i2,i2))
        C = [[C1,C2],[C3,C4]]
        return C

x = np.array([[1, 2], [3, 4]])
y = np.arange(16).reshape(4,4)

z = matrix_mulitplication([[1]],[[2]])
print(z)
z = matrix_mulitplication(x.tolist(), x.tolist())
print(z)
print(x@x)
z = matrix_mulitplication(y.tolist(), y.tolist())
print(z)
print(y@y)

Это работает для одного уровня рекурсии, но не для двух: 

1253:~/mypy$ python3 stack50552791.py 
2
[[7, 10], [15, 22]]
[[ 7 10]
 [15 22]]
[[[[4, 5], [20, 29], [52, 57], [132, 145]], [[6, 7], [38, 47], [62, 67], [158, 171]]], [[[36, 53], [52, 77], [212, 233], [292, 321]], [[70, 87], [102, 127], [254, 275], [350, 379]]]]
[[ 56  62  68  74]
 [152 174 196 218]
 [248 286 324 362]
 [344 398 452 506]]

Проблема со вторымУровень в том, что matrix_mulitplication возвращает вложенный список, а список + определяется как конкатенация, а не добавление элемента.Поэтому мне нужно определить другую вспомогательную функцию (или 2) для правильного решения этой проблемы.

чуть лучше 

def matrix_mulitplication(A, B):
    def blk(x,i1,i2):
        return [row[i2] for row in x[i1]]
    def add(x,y):
        if isinstance(x, list):
            return [add(i,j) for i,j in zip(x,y)]
        else:
            return x+y
    n = len(A) # A.shape[0]

    if n == 1:
        return A[0][0] * B[0][0]
    else:
        i = int(n / 2)
        i1, i2 = slice(None,i), slice(i,None)
        #C = np.zeros((n, n), dtype=np.int)
        C1 = add(matrix_mulitplication(blk(A, i1, i1), blk(B,i1,i1)) ,\
             matrix_mulitplication(blk(A, i1, i2), blk(B,i2,i1)))

        C2 = add(matrix_mulitplication(blk(A, i1, i1), blk(B,i1,i2)) ,\
             matrix_mulitplication(blk(A, i1, i2), blk(B,i2,i2)))

        C3 = add(matrix_mulitplication(blk(A, i2, i1), blk(B,i1,i1)) ,\
             matrix_mulitplication(blk(A, i2, i2), blk(B,i2,i1)))

        C4 = add(matrix_mulitplication(blk(A, i2, i1), blk(B,i1,i2)) ,\
             matrix_mulitplication(blk(A, i2, i2), blk(B,i2,i2)))
        C = [[C1,C2],[C3,C4]]
        return C

и для случая 4x4 

[[[[56, 62], [152, 174]], [[68, 74], [196, 218]]], [[[248, 286], [344, 398]], [[324, 362], [452, 506]]]]
[[ 56  62  68  74]
 [152 174 196 218]
 [248 286 324 362]
 [344 398 452 506]]

Все числа есть, но во вложенном списке из 4 глубин.

Так что не только разбивать вложенный список на 2d блоки более неудобно, чем с массивами, их сборка также неудобна.

https://en.wikipedia.org/wiki/Strassen_algorithm

Без подробного ознакомления с алгоритмом Штрассена очевидно, что любые утверждения о его эффективности предполагают, что индексирование A_ij (для отдельных элементов или блоков) является эффективным, какпри получении значений и настроек (C_ij).Со списками A[i] или A[i:j] довольно эффективны, но [row[i2] for row in x[i1] - нет.

Сборка блоков с [[a,b],[c,d]] - это нормально, но все, что сопоставимо с [[C_11,C_12],[C_21,C_22]], где элементы CБлоки, в отличие от скаляров, сложны.

Кажется, что целью Штрассена является уменьшение необходимого количества умножений.Это предполагает, что (скалярные) умножения являются самой дорогой частью умножения матриц.Со списками Python это явно не так.Доступ к элементам обходится дороже.

нудистский чит

Я мог бы переделать z из корпуса 4x4 с 

arr = np.array(z)
arr = arr.transpose(0,2,1,3).reshape(4,4)

Это намного проще в numpy.

0 голосов
/ 27 мая 2018

В numpy вы просто выполняете двумерное матричное умножение, которое может быть выражено несколькими способами, например, np.dot, np.einsum или оператор (newish) @ 

In [1]: x = np.array([[1, 2], [3, 4]])
In [2]: x@x
Out[2]: 
array([[ 7, 10],
       [15, 22]])

Чтобы сделать то же самое со списками, давайте подойдем к задаче поэтапно

В алгебре я научился бегать одним пальцем по строкам, а другим - по столбцам.Итак, давайте разберемся со списком: 

In [6]: x1 = x.tolist()
In [7]: x2 = x.tolist()
In [8]: [[(row1,col2) for col2 in zip(*x2)] for row1 in x1]
Out[8]: [[([1, 2], (1, 3)), ([1, 2], (2, 4))], [([3, 4], (1, 3)), ([3, 4], (2, 4))]]

Спаривание строк и столбцов выглядит правильно.zip(*xl) - это идиома для «транспонирования» списка (эквивалент x.T в numpy)

Теперь определите вспомогательную функцию, которая выполняет умножение 1d: 

In [9]: def mult(row,col):
   ...:     return [i*j for i,j in zip(row,col)]
   ...: 
   ...: 
In [10]: [[mult(row1,col2) for col2 in zip(*x2)] for row1 in x1]
Out[10]: [[[1, 6], [2, 8]], [[3, 12], [6, 16]]]

Теперь добавьте суммирование,Я мог бы вернуться к изменению mult, но сделать это во внешнем понимании так же просто. 

In [12]: [[sum(mult(row1,col2)) for col2 in zip(*x2)] for row1 in x1]
Out[12]: [[7, 10], [15, 22]]

Или объединить все списочные понимания, чтобы сделать одну нечитаемую строку: 

In [14]: [[sum(i*j for i,j in zip(row1,col2)) for col2 in zip(*x2)] for row1 in x1]
Out[14]: [[7, 10], [15, 22]]

Для этого примера 2x2 мои результаты те же, что и у вас, но вы придерживаетесь другого подхода, разбивая исходные массивы на блоки.Может нормально работать с numpy массивами, которые хорошо нарезаются.Но я не уверен, что это помогает со списками.Нам пришлось бы поиграться с другими примерами.

Шахта работает с массивом 3x3 

In [29]: y = np.arange(9).reshape(3,3)
In [30]: [[sum(mult(row1,col2)) for col2 in zip(*y.tolist())] for row1 in y.toli
    ...: st()]
Out[30]: [[15, 18, 21], [42, 54, 66], [69, 90, 111]]
In [31]: y@y
Out[31]: 
array([[ 15,  18,  21],
       [ 42,  54,  66],
       [ 69,  90, 111]])

У вас не получается с ошибкой трансляции формы на 3x3, но работает так же на 4x4. 

In [32]: y = np.arange(16).reshape(4,4)
In [33]: y@y
Out[33]: 
array([[ 56,  62,  68,  74],
       [152, 174, 196, 218],
       [248, 286, 324, 362],
       [344, 398, 452, 506]])
In [34]: [[sum(mult(row1,col2)) for col2 in zip(*y.tolist())] for row1 in y.toli
    ...: st()]
Out[34]: 
[[56, 62, 68, 74],
 [152, 174, 196, 218],
 [248, 286, 324, 362],
 [344, 398, 452, 506]]
In [35]: matrix_mulitplication(y,y)
Out[35]: 
array([[ 56,  62,  68,  74],
       [152, 174, 196, 218],
       [248, 286, 324, 362],
       [344, 398, 452, 506]])

Итак, ваша рекурсия состоит в том, чтобы разбить 4x4 на блоки 2x2, а затем до 1x1.Шахта разбивает 2d массивы на 1d суммы продуктов.

...