我有三个数组RowIndex,ColIndex并且Entry在numpy中.实质上,这是来自矩阵的条目子集,分别具有行索引,列索引和这三个变量中该条目的值.我有两个numpy二维数组(矩阵)U和M.设alpha和beta是两个给定的常数.我需要通过,如果我遍历这是可能的矩阵的条目的子集进行迭代RowIndex,ColIndex和Value.说,
i=RowIndex[0], j=ColIndex[0], value = Entry[0]
然后我需要更新i"行第j"的第n列U,并M根据一些方程分别.然后,我做
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(或它们的行和列).
我想如果我没理解错的话，你的代码可以向量化如下：
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]
请注意，独立集是由行和列中唯一的索引组成的。通过该定义，您可以将所需的循环数量从 6 个（在本例中）减少到 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）。因此，由于行和列都必须是唯一的，我们最终得到 2 组元组：
rows_idx = [1, 4, 5], [1, 3, 0]
cols_idx = [7, 5, 6], [1, 7, 5]
从这里开始，要走的路将取决于您的数据。寻找独立集合的问题可能非常昂贵，特别是如果它们中的大多数依赖于某些先前的更新。
如果您有办法从您的数据（假设您已按时记录数据）中提取独立集，那么批量更新将对您有所帮助。另一方面，如果您将所有数据放在一起（这很常见），则这将取决于一个因素：
如果您可以确保独立集的长度N远大于独立集的数量M（这或多或少意味着，如果您最终会M = {2,3,4}为N = 100000, with N >> M行/列索引得到一些独立集），那么它可能值得寻找独立套装。
换句话说，如果您要以 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包含 rows_idx 和 cols_idx 的位置unique，希望这可以大大减少您的计算成本。您可以使用我的批量更新来快速更新那些索引对应的行和列。然后，您可以使用初始方法来更新在非唯一索引上重复迭代的少数条目。
如果您对相同的演员或电影有多个更新，那么...保留顺序更新方案，因为找到独立的集合将比迭代更新更困难。