CS231n-assignment1 K近邻算法实现 two loops/one loop/no loop

 

1. 两重循环

def compute_distances_two_loops(self, X):
    """
    Compute the distance between each test point in X and each training point
    in self.X_train using a nested loop over both the training data and the 
    test data.

    Inputs:
    - X: A numpy array of shape (num_test, D) containing test data.

    Returns:
    - dists: A numpy array of shape (num_test, num_train) where dists[i, j]
      is the Euclidean distance between the ith test point and the jth training
      point.
    """
    num_test = X.shape[0]
    num_train = self.X_train.shape[0]
    dists = np.zeros((num_test, num_train))
    for i in range(num_test):
      for j in range(num_train):
        dists[i,j] = np.sqrt(np.sum((X[i]-self.X_train[j])*(X[i]-self.X_train[j])))
    return dists

2. 一重循环

  def compute_distances_one_loop(self, X):
    """
    Compute the distance between each test point in X and each training point
    in self.X_train using a single loop over the test data.

    Input / Output: Same as compute_distances_two_loops
    """
    num_test = X.shape[0]
    num_train = self.X_train.shape[0]
    dists = np.zeros((num_test, num_train))
    for i in range(num_test):
      dists[i,:] = np.sqrt(np.sum((self.X_train-X[i])*(self.X_train-X[i]),axis=1))  
    return dists

3. 没有循环

  def compute_distances_no_loops(self, X):
    """
    Compute the distance between each test point in X and each training point
    in self.X_train using no explicit loops.

    Input / Output: Same as compute_distances_two_loops
    """
    num_test = X.shape[0]
    num_train = self.X_train.shape[0]
    dists = np.zeros((num_test, num_train)) 
    A = np.sum(np.square(self.X_train), axis = 1)
    B = np.transpose([np.sum(np.square(X), axis = 1)])
    C = -2*np.dot(X, self.X_train.T)   

    dists = np.sqrt(C + A + B)
    return dists

Two loop version took 75.968964 seconds
One loop version took 132.806771 seconds
No loop version took 0.374766 seconds