在pythonnumpy中，有没有一种更快的方法来高效地执行这些伪代码？

Question

我有三个数组，在numpy中分别称为RowIndex、ColIndex和Entry。从本质上说，这是矩阵中的一个子集，其中行索引、列索引和该项的值分别位于这三个变量中。我有两个numpy2d数组（矩阵）U和M。设alpha和beta为两个给定常数。我需要遍历矩阵项的子集，如果我遍历RowIndex、ColIndex和Value，这是可能的。说

i=RowIndex[0], j=ColIndex[0], value = Entry[0] 

然后我需要根据一些等式分别更新U和M的i行和j列。那么，我要

i=RowIndex[1], j=ColIndex[1], value = Entry[1]

等等。详情如下。你知道吗

for iter in np.arange(length(RowIndex)):
    i = RowIndex[iter]
    j = ColIndex[iter]
    value = Entry[iter]
    e = value - np.dot(U[i,:],M[:,j])
    OldUi = U[i,:]
    OldMj = M[:,j]
    U[i,:] = OldUi + beta * (e*OldMj - alpha*OldUi)
    M[:,j] = OldMj + beta * (e*OldUi - alpha*OldMj)

问题是代码非常慢。有没有代码的任何部分可以让我加快速度？你知道吗

PS：对于好奇的人来说，这是著名的NetFlix百万奖金问题的获奖解决方案的变体。RowIndex对应于用户，ColIndex对应于电影，值对应于他们的收视率。大多数评级都不见了。已知的评级在RowIndex、ColIndex和Entry中堆积起来。现在你试着找到矩阵U和M，这样，第i个用户对第j个电影的评分由np.dot(U[i,:],M[:,j])给出。现在，根据可用的评级，您可以尝试使用更新公式来查找矩阵U和M（或它们的行和列），如上面的代码所示。你知道吗

Answer 1

我想如果我没有理解错，你的代码可以矢量化如下：

import numpy as np

U, M = # two 2D matrices
rows_idx = # list of indexes
cols_idx = # list of indexes
values   = # np.array() of values

e = values - np.dot(U[rows_idx, :], M[:, cols_idx]).diagonal()
Uo = U.copy()
Mo = M.copy()
U[rows_idx, :] += beta * ((e * Mo[:, cols_idx]).T - alpha * Uo[rows_idx, :])
M[:, cols_idx] += beta * ((e * Uo[rows_idx, :].T) - alpha * Mo[:, cols_idx])

在这里

e = values - np.dot(U[rows_idx, :], M[:, cols_idx]).diagonal()

计算你的

e = value - np.dot(U[i,:],M[:,j])

请注意，您想要的结果位于矩阵之间点积的对角线上。你知道吗

这不会处理顺序更新（因为没有可用的矢量化），但它允许您以矢量化和更快的方式执行一批独立的更新。你知道吗

---

如上所述，我向您建议的代码不能处理顺序更新，因为根据定义，顺序更新方案不能矢量化。任何形式的

A(t) = A(t-1) +/* something

其中t定义时间，不能并行更新。你知道吗

所以，我提议的是一个向量化的更新，用于独立的更新。你知道吗

假设您有M和U，每行有10x10行，并且您有以下行和列索引：

rows_idx = [1, 1, 3, 4, 5, 0]
cols_idx = [7, 1, 7, 5, 6, 5]

您可以从中识别两个独立的集合（考虑到索引是有序的）：

rows_idx = [1, 4, 5], [1, 3, 0]
cols_idx = [7, 5, 6], [1, 7, 5]

请注意，独立集是由行和列中唯一的索引组成的。在这种情况下，您可以将循环的数量从2减少到：

for i in len(rows_idx):
    ridx = rows_idx[i]
    cidx = cols_idx[i]
    # Use the vectorized scheme proposed above the edit
    e = values - np.dot(U[ridx, :], M[:, cidx]).diagonal()
    Uo = U.copy()
    Mo = M.copy()
    U[ridx, :] += beta * ((e * Mo[:, cidx]).T - alpha * Uo[ridx, :])
    M[:, cidx] += beta * ((e * Uo[ridx, :].T) - alpha * Mo[:, cidx])

因此，如果您有一种手动（或轻松）提取独立更新的方法，或者您使用搜索算法计算列表，那么上面的代码将对独立更新进行矢量化。你知道吗

---

为了以防万一，在上面的例子中：

rows_idx = [1, 1, 3, 4, 5, 0]
cols_idx = [7, 1, 7, 5, 6, 5]

第二行无法并行化，因为1以前出现过，第三列和最后一列无法并行化，原因相同（使用7和5）。因此，由于行和列都需要是唯一的，因此我们最终得到两组元组：

rows_idx = [1, 4, 5], [1, 3, 0]
cols_idx = [7, 5, 6], [1, 7, 5]

从这里开始，要走的路取决于你的数据。寻找独立集的问题可能非常昂贵，特别是如果其中大多数依赖于以前的一些更新。你知道吗

如果你有办法从你的数据（比如说你有你的数据记录的时间）提取独立的集，那么批量更新将帮助你。另一方面，如果您将所有数据放在一起（这是常见的），它将取决于一个因素：

如果您可以确保独立集的长度N远远大于独立集的数量M（这或多或少意味着，如果您的N = 100000, with N >> M行/列索引最终会有几个M = {2,3,4}独立集），那么可能值得寻找独立集。你知道吗

换言之，如果您要以10000种不同的组合更新30位作者和30部电影，则您的数据可能与以前的更新相关，但是，如果您要以30种组合更新100000位作者和100000部电影，则您的数据可能是独立的。你知道吗

如果你没有办法在没有信息的情况下提取独立集，那么可以使用一些伪代码来查找独立集，如下所示：

independent_sets = [] # list with sets

for row, col in zip(rows_idx, cols_idx):
    for iset in independent_sets:
        if row and col DONT exist in iset:
            insert row and col
            break
    if nothing inserted:
        add new set to independent set
        add current (row, col) to the new set

要找到独立的行/列集合，您需要按行/列的顺序进行迭代。上面的伪代码并不是最有效的，我很肯定会有具体的算法来实现这一点。但是，如果您的更新可能依赖于以前的更新，那么查找独立集的成本可能比执行所有顺序更新的成本要高。你知道吗

完成：在整个帖子之后，这完全取决于你的数据。你知道吗

• 如果可以预先从获取要更新的行/列的方式中提取独立集，则可以轻松地将它们矢量化。

• 如果你能确保你的大多数更新都是独立的（比如说，990中的10000），那么寻找990集可能是值得的。一种近似集合的方法是使用np.unique：你知道吗

  # Just get the index of the unique rows and columns
  _, idx_rows = np.unique(rows_idx, return_index=True) 
  _, idx_cols = np.unique(cols_idx, return_index=True)
  
  # Get the index where both rows and columns are unique
  idx = np.intersection1d(idx_rows, idx_cols)
  

  现在idx包含unique的行idx和列idx的位置，希望这可以大大降低计算成本。您可以使用我的批更新来快速更新与这些索引对应的行和列。然后，您可以使用初始方法更新少数在非唯一索引上重复迭代的条目。

• 如果你对同一个演员或电影有多个更新，那么。。。保留顺序更新方案，因为寻找独立集比迭代更新更困难。