python - 为什么 numpy 在查找矩阵中的非零元素方面更快？

Question

def nonzero(a):      
    row,colum = a.shape
    nonzero_row = np.array([],dtype=int)
    nonzero_col = np.array([],dtype=int)
    for i in range(0,row):
        for j in range(0,colum):
            if a[i,j] != 0:
                nonzero_row = np.append(nonzero_row,i)
                nonzero_col = np.append(nonzero_col,j)
    return (nonzero_row,nonzero_col) 

上面的代码比

慢得多

(row,col) = np.nonzero(edges_canny)

如果我能得到任何关于如何提高速度以及为什么 numpy 函数更快的指导，那就太好了？

Answer 1

NumPy 函数优于 Python 类型的原因有两个:

• 数组内的值是 native 类型，而不是 Python 类型。这意味着 NumPy 不需要经过 Python 所具有的抽象层。
• NumPy 函数(大部分)是用 C 编写的。这实际上只在某些情况下很重要，因为许多 Python 函数也是用 C 编写的，例如 sum。

在你的情况下，你还做了一些非常低效的事情:你附加到一个数组。这是双循环中间的一个非常昂贵的操作。这是一个明显的(也是不必要的)瓶颈。只需使用列表作为 nonzero_row 和 nonzero_col 并仅在返回之前将它们转换为数组，您将获得惊人的加速:

def nonzero_list_based(a):      
    row,colum = a.shape
    a = a.tolist()
    nonzero_row = []
    nonzero_col = []
    for i in range(0,row):
        for j in range(0,colum):
            if a[i][j] != 0:
                nonzero_row.append(i)
                nonzero_col.append(j)
    return (np.array(nonzero_row), np.array(nonzero_col)) 

时间安排:

import numpy as np

def nonzero_original(a):      
    row,colum = a.shape
    nonzero_row = np.array([],dtype=int)
    nonzero_col = np.array([],dtype=int)
    for i in range(0,row):
        for j in range(0,colum):
            if a[i,j] != 0:
                nonzero_row = np.append(nonzero_row,i)
                nonzero_col = np.append(nonzero_col,j)
    return (nonzero_row,nonzero_col) 


arr = np.random.randint(0, 10, (100, 100))
%timeit np.nonzero(arr)
# 315 µs ± 5.39 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit nonzero_original(arr)
# 759 ms ± 12.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit nonzero_list_based(arr)
# 13.1 ms ± 492 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

尽管它比 NumPy 操作慢 40 倍，但它仍然比您的方法快 60 倍以上。这里有一个重要的教训:尽可能避免 np.append!

<小时/>

NumPy 优于替代方法的另一点是因为它们(大多数)使用最先进的方法(或者“导入”它们，即 BLAS/LAPACK/ATLAS/MKL)来解决问题。这些算法已经在数年(如果不是几十年)的正确性和速度方面进行了优化。您不应该期望找到更快甚至类似的解决方案。