如何在 O(m+n) 中获取两个稀疏向量的点积，其中 m 和 n 是两个向量中的元素数

Question

我有两个稀疏向量 X 和 Y，想得到 O(m+n) 的点积，其中 m 和 n 是 X 和 Y 中非零元素的数量。我能想到的唯一方法of 正在选取向量 X 中的每个元素并遍历向量 Y 以查找是否存在具有相同索引的元素。但这需要 O(m * n)。我将向量实现为链表，每个节点都有一个元素。

Answer 1

如果您的向量存储为元组的链接列表，每个元组包含索引和非零元素的值并按索引排序，则可以这样做。

您通过从较低索引处的向量中选择下一个元素来迭代这两个向量。如果索引相同，则将元素相乘并存储结果。

重复直到一个列表结束。

由于每个列表中的每个非零元素都有一个步骤，因此根据需要复杂度为 O(m+n)。

脚注：数据结构不必是链表，但必须提供 O(1) 的方式来访问下一个非 0 元素及其索引。

Answer 2

排序列表

鉴于您的非零元素在两个向量中均按坐标索引排序，因此可以通过 merge 算法实现。那是计算机科学中的一种标准算法，它将两个已排序的序列合并为一个已排序的序列，并且工作在O(M + N).

有两种方法可以做到。第一个是检查合并中的相等元素。而且确实是最好的方法。

第二种方式是先合并，再判断是否相等（必须是连续的）：

std::pair<int, double> vecA[n], vecB[m], vecBoth[n+m];
std::merge(vecA, vecA+n, vecB, vecB+m, vecBoth);
double dotP = 0.0;
for (int i = 0; i+1 < n+m; i++)
  if (vecBoth[i].first == vecBoth[i+1].first)
    dotP += vecBoth[i].second * vecBoth[i+1].second;

std::merge 的复杂度是 O(M + N).

上面的示例假设数据存储在数组中（这是稀疏向量和矩阵的最佳选择）。如果要使用链表，也可以在O(M + N)时间内执行merge，见this question.

未排序列表

即使您的列表未排序，您仍然可以在 O(M + N) 时间内执行点积。思路是先把A的所有元素放入hashtable，然后遍历B的元素，看有没有哈希中具有相同索引的元素。

如果索引非常大（例如超过百万），那么也许您真的应该使用非平凡的哈希函数。但是，如果您的索引相当小，那么您可以避免使用哈希函数。只需使用大小大于向量维度的数组。为了快速清除这个数组，你可以使用 "generations".

的技巧

//global data! must be threadlocal in case of concurrent access
double elemsTable[1<<20];
int whenUsed[1<<20] = {0};
int usedGeneration = 0;

double CalcDotProduct(std::pair<int, double> vecA[n], vecB[m]) {
  usedGeneration++;   //clear used array in O(1)
  for (int i = 0; i < n; i++) {
    elemsTable[vecA[i].first] = vecA[i].second;
    whenUsed[vecA[i].first] = usedGeneration;
  }
  double dotP = 0.0;
  for (int i = 0; i < m; i++)
    if (whenUsed[vecB[i].first] == usedGeneration)
      dotP += elemsTable[vecB[i].first] * vecB[i].second;
  return dotP;
}

请注意，您可能需要清除 whenUsed 每十亿个点积一次。

Answer 3

 Use Map to store each vector.
 Each entry of map has index as key and value as the vector value at the particular index. Insert only the non zero values 
 Iterate on one map and for each entry check whether the particular key is present in the other map.If yes update the product else ignore the current key
 Time Complexity :  n -> vector size
                   O(n) - for map construction 
                   O(n) - for iteration 
 Space Complexity :  O(n) - for maps

如何在 O(m+n) 中获取两个稀疏向量的点积，其中 m 和 n 是两个向量中的元素数

How to get dot product of two sparsevectors in O(m+n) , where m and n are the number of elements in both vectors

algorithm

big-o

linear-algebra

排序列表

未排序列表