如何得到O（mn）中两个稀疏向量的点积，其中m和n是两个向量中的元素数

Question

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

Answer 1

 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

Answer 2

假设非零元素是通过两个向量中的坐标索引排序的，那么它是通过合并算法实现的。这是计算机科学中的一个标准算法，它将两个排序序列合并成一个排序序列，并且在O（mn）中工作。

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

第二种方法是先合并，然后检查相等（它们必须是连续的）：

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::合并复杂度为O（M N）。

上面的示例假设数据存储在数组中（这是稀疏向量和矩阵的最佳选择）。如果您想使用链表，还可以在O（M N）时间内执行合并，请参见此问题。

即使列表未排序，也可以在O（MN）时间内执行点积。其思想是首先将A的所有元素放入哈希表，然后遍历B的元素，查看哈希表中是否有具有相同索引的元素。

如果索引非常大（例如超过百万），那么您可能真的应该使用一个非平凡的哈希函数。然而，若索引很小，那个么可以避免使用哈希函数。只需使用大于向量维数的数组。为了快速清除此阵列，您可以使用“世代”技巧。

//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;
}

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

Answer 3

如果向量存储为元组的链接列表，每个元组包含索引和非零元素的值，并按索引排序，则可以执行此操作。

通过从位于较低索引处的向量中选择下一个元素，可以遍历这两个向量。如果索引相同，则将元素相乘并存储结果。

重复此操作，直到一个列表到达末尾。

由于在每个列表中每个非零元素都有一个步骤，因此所需的复杂度为O（m n）。

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