Numpy.dot矩阵乘法：(n x m)*(m x k)和(m x k)*(k x n)的速度非常不同。

Question

我有以下Python代码：

import numpy
import time

A = numpy.random.random((10,60000))
B = numpy.random.random((60000,785))
C = numpy.random.random((785,10))

t = time.time()
D = A.dot(B)
print "%.2f s" % (time.time() - t)

t = time.time()
E = B.dot(C)
print "%.2f s" % (time.time() - t)

我认为矩阵乘法A * B和B * C应该花费大致相同的时间，因为两个乘法都涉及到10 * 60000 * 785次乘法操作。

然而，在不同的机器上，我得到了非常不同的时间。在我的笔记本电脑上（Windows 7，2.40 GHz CPU，8G内存，Python 2.7，Numpy 1.7.1），我得到了以下结果：

0.21 s
0.21 s

这是正常的。在一个集群机器上（Linux CentOS 5.6，2.66 GHz CPU，16G内存，Python 2.7.3，Numpy 1.8.1），我得到了：

6.77 s
1.10 s

其中 A * B 比 B * C 慢得多。

有人能解释一下为什么这两个乘法需要不同的时间吗？我不确定哪些配置是相关的，但我会尽可能提供必要的信息。

- Maigo

---

numpy.transpose(B).dot(numpy.transpose(A)) 比 B*C 慢很多吗？如果不是，我怀疑这是一个内存布局问题。 - user14717

请注意，机器之间的差异可能是由于不同的BLAS库造成的。我敢打赌，你的CentOS numpy没有链接到“完整”的BLAS库，并且正在使用numpy内置（但速度较慢）的BLAS替代品。查看两个系统上numpy.show_config()的输出进行比较。 - Joe Kington

@JoeKington 配置确实不同。在Windows上，我有以下配置：blas_opt_info（库：f77blas、cblas、atlas，语言：c），lapack_opt_info（库：lapack、f77blas、cblas、atlas，语言：f77），atlas_info（库：lapack、f77blas、cblas、atlas，语言：f77），atlas_blas_info（库：f77blas、cblas、atlas，语言：c）。在Linux上，我有：blas_info（库：blas，语言：f77），lapack_info（库：lapack，语言：f77），blas_opt_info（库：blas，语言：f77），lapack_opt_info（库：lapack、blas，语言：f77）。 - Maigo

@JoeKington 对于这么长的列表我很抱歉，但是配置差异很大。这是否导致了不同的速度？ - Maigo

@Magio - 嗯，Linux版本的numpy没有链接Atlas或MKL版本的BLAS或LAPACK，这就解释了整体速度较慢的原因。您有机会尝试安装Anaconda的Python吗（它将安装在您的主目录或任何您具有写入权限的位置），并使用完全链接的numpy重新测试时间吗？ - Joe Kington

@JoeKington 谢谢！我刚刚安装了Anaconda的Python，现在我得到的时间是：A * B: 0.22秒; B' * A': 0.22秒; B * C: 0.27秒; C' * B': 0.27秒。我认为这很正常 :) - Maigo

Answer 1

如果你运行以下代码，你会发现性能上是否存在较大差异？

#!/usr/bin/env python3.4                                                                 
import numpy
import time

A = numpy.random.random((10,60000))
B = numpy.random.random((60000,785))
C = numpy.random.random((785,10))

t = time.time()
D = A.dot(B)
print("%.2f s" % (time.time() - t))

t = time.time()
D = numpy.transpose(B).dot(numpy.transpose(A))
print("%.2f s" % (time.time() - t))

t = time.time()
D = B.dot(C)
print("%.2f s" % (time.time() - t))

t = time.time()
D = numpy.transpose(C).dot(numpy.transpose(B))
print("%.2f s" % (time.time() - t))

当我运行这个程序时，我得到的结果是：

0.21 s
0.22 s
0.44 s
0.22 s

这强烈表明了内存访问模式的差异。

- user14717

---

我得到了有趣的模式： 在Windows上：0.20秒，1.15秒，0.20秒，1.16秒； 在Linux上：6.82秒，6.79秒，1.10秒，1.31秒。 - Maigo

我刚按照@JoeKington的评论安装了Anaconda的Python，现在我的运行时间是0.22秒、0.22秒、0.27秒、0.27秒。这似乎很正常。谢谢！ - Maigo

Answer 2

A中的元素比C多，因此结果是直观的。

- Andrew F

---

我不明白你的意思。将一个n行m列的矩阵和一个m行k列的矩阵相乘的时间复杂度为O(nmk)。此外，不同机器的计时差异表明可能与配置有关。 - Maigo