实现Strassen算法

Question

斯特拉森算法是第一种以子立方时间复杂度进行矩阵乘法的方法，即对一对n*n矩阵的O(n**log2(7)) (假设其中的数字足够大，它们的O(n*log2(n))精确乘法已成为对性能的限制，任何嵌套结构和函数调用相比都是可以忽略不计的)。

对于2*2矩阵，它被定义为

lambda a,b: (lambda a,b,c,d,e,f,g: (a+d-e+g,c+e,b+d,a-b+c+f))((a[0]+a[3])*(b[0]+b[3]),(a[2]+a[3])*b[0],a[0]*(b[1]-b[3]),a[3]*(b[2]-b[0]),(a[0]+a[1])*b[3],(a[2]-a[0])*(b[0]+b[1]),(a[1]-a[3])*(b[2]+b[3]))

对于较大的方格，把它们分成四分之一，然后调用它，但是用数字的加法、否定和乘法代替矩阵(特别是用它自己来代替矩阵，它的宽度和高度每翻一倍就是指数的原因)。

为了简单(因此您不需要处理实现标准矩阵乘法和细分为可Strassen的矩阵)，您的输入将是两个由整数组成的2**n*2**n矩阵，表示为length-2**(2*n)元组(或列表或您的语言的等效值)，用元素按读取顺序编码，然后返回另一个这样的元组。例如，当输入这两个

(5,2,0,0,
 4,0,5,2,
 3,4,5,0,
 3,1,4,2)

(7,4,5,3,
 4,0,2,7,
 1,4,1,1,
 0,5,3,5)

，它应该会回来

(43,20,29,29,
 33,46,31,27,
 42,32,28,42,
 29,38,27,30)

Answer 1

单行Python (1027字节)

(在这个要旨中解释过，如果你不那么拘泥于一句话的话，那将是很难接受的)

from functools import reduce
from math import isqrt
from random import random
lap=(lambda f,*a: list(map(f,*a)))
strassen=(lambda a,b: tuple((lambda f: f(a,b) if len(a)==4 else (lambda m: (lambda m,d: ((m[y*2+x][d*j+i] for y in range(2) for j in range(d) for x in range(2) for i in range(d))))(m,isqrt(len(m[0]))))(f(*(map((lambda m: (lambda m,d: tuple((tuple((m[i*d+j] for i in range(d//2*y,d//(2-y)) for j in range(d//2*x,d//(2-x)))) for y in range(2) for x in range(2))))(m,isqrt(len(m)))),(a,b))))))((lambda a,b: (lambda s,n,o,m: (lambda a,b,c,d,e,f,g: lap(s,((a,d,n(e),g),(c,e),(b,d),(a,n(b),c,f))))(*map(m,*map(lambda x: map(o,x),(((a[0],a[3]),(a[2],a[3]),(a[0],),(a[3],),(a[0],a[1]),(a[2],n(a[0])),(a[1],n(a[3]))),((b[0],b[3]),(b[0],),(b[1],n(b[3])),(b[2],n(b[0])),(b[3],),(b[0],b[1]),(b[2],b[3])))))))(*((sum,int.__neg__,sum,int.__mul__) if type(a[0])==int else ((lambda x: reduce(lambda a,b: lap(int.__add__,a,b),x)),(lambda x: map(int.__neg__,x)),(lambda t: t[0] if len(t)==1 else lap(int.__add__,*t)),strassen)))))))