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

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

首先，在内存中，一个数组是一个连续的地址块，它存储的方式是 a [ 0 ] [ 0 ] , a [ ] [ 0 ] [ 1 ] . . . a [ 0 ] [ n − 1 ] ; a [ 1 ] [ 0 ] . . . a[0][0],a[][0][1]...a[0][n-1];a[1][0]... 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矩阵

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) # 按行

得证