矩阵按行按列访问的效率差异

100 阅读 0 评论 66 点赞

我是靠谱客的博主现代故事，这篇文章主要介绍矩阵按行按列访问的效率差异，现在分享给大家，希望可以做个参考。

最早接触这个问题是在面试字节的时候，当时也答得大差不差，今天在学计算机组成原理的时候又想起了这个问题，于是blog上记录一下

原理

首先，在内存中，一个数组是一个连续的地址块，它存储的方式是 $a [0] [0], a [] [0] [1] . . . a [0] [n - 1]; a [1] [0] . . .$ 也就是一行一行的存储
其次在计算机体系结构中，由于cpu速度与主存速度的差异，所以产生了cache这样的高速缓存，它速度介于二者之间，价格较高，容量较小，集成度较低
在计算机中，会基于这样的思想，最近的未来将要使用的信息很有空能在现在使用信息的周围，也就是局部性原理（空间）。于是计算机会将矩阵数组的部分给放进cache，方便我们在for循环时快速访问
而由于cache不够大，同时，cache中是分块的，没有必要将整个矩阵放进去，无法保证整个矩阵都会被使用，所以只放进去部分
此时，按行访问，则实际上是连续读取，刚好大多次都能够cache命中；而按列读取，则是非连续读取，cache命中的理论可能性不大，所以需要访问主存的次数增多，于是，所花费时间变多

实验证明

python，numpy矩阵，20000*20000的全0矩阵

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def scanRow(matrix):
    '''
    按行遍历矩阵
    :param matrix:
    :return:
    '''
    m,n = np.shape(matrix)
    print(m,n)
    sTime = time.time()
    sum = 0
    for i in range(m):
        for j in range(n):
           sum += matrix[i][j]

    print("总耗时：",int(time.time()-sTime))

def scanCol(matrix):
    '''
    按列遍历矩阵
    :param matrix:
    :return:
    '''
    m,n = np.shape(matrix)
    print(m,n)
    sTime = time.time()
    sum = 0
    for j in range(n):
        for i in range(m):
           sum += matrix[i][j]

    print("总耗时：",int(time.time()-sTime))

if __name__=="__main__":
    matrix = np.zeros((20000,20000))
    scanCol(matrix) # 按列
    scanRow(matrix) # 按行