逐个元素或矩阵执行

Question

我目前沉浸在机器学习和数据科学领域，重点是数学方面。我正在积极学习深度学习课程 (http://ufldl.stanford.edu/housenumbers/)，该课程要求我实施 KNN 方法。

该作业涉及创建一个距离矩阵（称为“D”），其中每个元素表示训练数据集中每个观测值与测试数据集中每个观测值之间的距离（使用数学范数）。具体来说，D[i][j] 表示训练数据集中的第“i”个观测值与测试数据集中的第“j”个观测值之间的曼哈顿距离（L1 范数）。

可以通过三种方法来实现此目的：

第一个是（有两个循环）：

def compute_distances_two_loops(train_X, test_X):
        '''
        Computes L1 distance from every sample of X to every training sample
        Uses simplest implementation with 2 Python loops

        Arguments:
        train_X, np array (num_train_samples, num_features)
        test_X,  np array (num_test_samples, num_features)


        Returns:
        dists, np array (num_test_samples, num_train_samples) - array
           with distances between each test and each train sample
        '''

        num_train = train_X.shape[0]
        num_test = test_X.shape[0]
        dists = np.zeros((num_test, num_train), np.float32)
        for i_test in range(num_test):
            for i_train in range(num_train):

                dists[i_test][i_train] = np.sum( np.abs( test_X[i_test] - train_X[i_train] ) )
     
        return dists

第二个是（一个循环）：

def compute_distances_one_loop(train_X, test_X):
        '''
        Arguments:
        train_X, np array (num_train_samples, num_features)
        test_X,  np array (num_test_samples, num_features)
        
        Returns:
        dists, np array (num_test_samples, num_train_samples) - array
           with distances between each test and each train sample
        '''

        num_train = train_X.shape[0]
        num_test = test_X.shape[0]
        dists = np.zeros((num_test, num_train), np.float32)
        for i_test in range(num_test):

            diff_matrix = np.abs(train_X - np.tile(test_X[i_test], (num_train, 1)))
            to_sum_matrix = np.ones((train_X.shape[1], 1), np.float32)

            dists[i_test] = (diff_matrix @ to_sum_matrix).T

        return dists

第三个是（没有循环）：

def compute_distances_no_loops(train_X, test_X):
        '''
        Computes L1 distance from every sample of X to every training sample
        Fully vectorizes the calculations using numpy

        Arguments:
        train_X, np array (num_train_samples, num_features)
        test_X,  np array (num_test_samples, num_features)
        
        Returns:
        dists, np array (num_test_samples, num_train_samples) - array
           with distances between each test and each train sample
        '''

        num_train = train_X.shape[0]
        num_test = test_X.shape[0]
       
        large_row_matrix_test = np.repeat(test_X, num_train, axis=0)
        large_row_matrix_train = np.tile(train_X, (num_test, 1))

        diff_matrix = np.abs(large_row_matrix_test - large_row_matrix_train)
        to_sum_matrix = np.ones((train_X.shape[1], 1), np.float32)

        dists = np.reshape( diff_matrix @ to_sum_matrix, (num_test, num_train) )

        return dists

接下来，任务要求我测量每个方法的执行时间：

# Lets look at the performance difference
%timeit knn_classifier.compute_distances_two_loops(binary_test_X)
%timeit knn_classifier.compute_distances_one_loop(binary_test_X)
%timeit knn_classifier.compute_distances_no_loops(binary_test_X)

我对结果感到惊讶，因为结果是：

每次循环 614 ms ± 27.9 ms（7 次运行的平均值 ± 标准差，每次 1 次循环）

每次循环 836 ms ± 35.1 ms（7 次运行的平均值 ± 标准差，每次 1 个循环）

每次循环 961 ms ± 30.5 ms（7 次运行的平均值 ± 标准差，每次 1 次循环）

有趣的是，最简单的方法最终是最快的，即使它使用循环，通常建议熟练的程序员避免使用循环。这种情况让我怀疑我是否犯了错误或误解了一个基本概念。或者，这个场景可能说明了一个例外，其中使用循环实际上是有利的。

请澄清此案。

Answer 1

使用 numpy 时最好避免 Python 循环，这基本上是正确的。然而，这应该被视为一般原则的一部分：尽可能多地使用 numpy 的内置功能，通过利用 C 循环和 CPU 的多数据指令，使其比原生 Python 代码更快。

这里，你的“无循环”函数确实没有循环，但是当它有循环时，它会在数据复制上花费时间

np.repeat

和

np.tile

，其程度超过了避免Python循环所节省的时间。为了避免这种数据复制，同时仍然避免循环，您可以使用 广播.

诀窍是将数组视为 3D 数组。在下面的代码中，

train_bc

具有沿轴 1 的训练样本和沿轴 2 的特征，而

test_bc

具有沿轴 0 的测试样本和沿轴 2 的特征。然后我们可以减去这些数组，以便

distance_components[i][j][k] 

给出测试样本

k

和训练样本

i

之间特征

j

的距离分量。最后，对轴 2 求和即可得到距离矩阵。

（注意，这给出了与您的

compute_distances_no_loops

相同的输出，但我认为它实际上是您的练习所需内容的转置，基于您问题中

D[i][j]

的定义）。

num_train_samples = 5000
num_test_samples = 500
num_features = 50

import numpy as np

train_X = np.random.uniform(size=(num_train_samples, num_features))
test_X = np.random.uniform(size=(num_test_samples, num_features))

def compute_distances_broadcast(train_arr, test_arr):
    # Add additional axes so the calculation can be done with broadcasting
    train_bc = train_arr[np.newaxis, :, :]  # Axes are (_, sample, feature)
    test_bc = test_arr[:, np.newaxis, :]    # Axes are (sample, _, feature)
    distance_components = np.abs(train_bc - test_bc)   # Axes are (test_sample, train_sample, feature)
    distances = np.sum(distance_components, axis=2)   # Axes are (test_sample, train_sample)
    return distances  

bc = compute_distances_broadcast(train_X, test_X)
nl = compute_distances_no_loops(train_X, test_X)
print(np.allclose(bc, nl))  # prints True, i.e. the two functions gives the same result

为我创建的随机输入计时（这显然不是您执行计时的内容）：

compute_distances_broadcast(train_X, test_X)

：每次循环 818 ms ± 33.8 ms（7 次运行的平均值 ± 标准差，每次 1 次循环）

compute_distances_no_loops(train_X, test_X)

：每次循环 1.68 秒 ± 516 毫秒（7 次运行的平均值 ± 标准差，每次 1 次循环）

因此，没有

repeat

或

tile

的解决方案大约是原始

no_loops

的两倍。