1

我的应用程序将在密集矩阵上执行大量矩阵运算（例如，加/乘）。我想缓存唯一的结果以避免重复计算。

密集矩阵：

typdef struct denseMatrix{
 int m;
 int n;
 double **d;            // actual matrix
 multiplyTable **entry; // key & result
} dns;

表项：

typedef struct multiplyTable{
 dns *rightOperand; // key
 dns *result;       // value
} multiplyTable;   // or something like that

dns *A, *B, *C, *D...; // allocated internally

C = mult(A,B); //may be called many many times.

在这种情况下，mult 将向表中添加一个条目（操作数，结果）对

add(A->entry, B, C); //B is the right operand and C is the result

稍后如果再次调用 D = mult(A, B)，则 search(A->entry,B) 将检索 C。另一方面，如果特定操作数不在列表中，则将其与指向结果矩阵的指针。

我以前从未做过这样的事情，我什至不确定这是否是解决问题的方法。根据我有限的理解，哈希表可以用来实现这样的东西。

我遇到的实际问题包括：（a）哈希表首先是解决该问题的适当解决方案吗？他们允许指针地址作为键和值吗？

(b) 将“哈希表”作为“字段”保留在结构中是否有意义？这样，我已经有了左操作数，我只需要在乘法表中搜索右操作数。或者，是否应该有一个独立的表，左右操作数都作为键？

(c) 我是否为加法/乘法等创建单独的表，还是应该有一个带有操作数和运算符的表？

(d) 跟踪所有创建的对象以便适当释放这些对象的最佳方式是什么？

(e) 什么公共可用的库（在 c 中）适合实施这样的事情？

我正在寻求有关（a）可以解决问题的替代方法以及（b）此类替代方法的优点/缺点的输入/建议。

最后，我发现这个论坛非常有帮助，并想表达我的感激之情。++谢谢。

4

3 回答 3

1

你必须非常小心哈希。如果您有冲突（不同原始值的哈希值相同），您最终可能会得到错误的结果。您确定计算矩阵的哈希会比执行实际操作更有效吗（这显然取决于这些操作的数量/复杂性）

第二个问题 - 你没有说任何关于你的缓存驱逐政策的事情。你打算只添加到哈希表而不删除吗？根据不同矩阵的数量，您可能会耗尽内存......

于 2009-08-17T03:00:02.637 回答
0

此功能称为记忆化 - 有关详细信息，请参阅维基百科文章。

本文还提到了一些可以帮助您的库。

于 2009-08-17T06:29:20.957 回答
0

首先回答简单的部分：对于矩阵运算的 C++ 库，请查看newmat，它具有大量内置功能，并且在性能方面非常有效。

对于您构建哈希以加速计算的特定情况 - 除非您要在非常有限的矩阵集上执行操作，否则缓存才是值得的。要为矩阵构建唯一哈希，您需要访问每个条目 - 并根据每个条目的位置和值计算哈希。更糟糕的是，矩阵并不总是可交换的，例如 A B != B A 除非在特殊情况下。

这意味着您的缓存必须为每个特定计算存储一个条目。因此，除非您处理的输入矩阵范围非常小，否则保存所有结果的内存成本将是巨大的。

  1. 对于非常小的矩阵或列/行向量，完整计算与计算哈希的边际开销很小......所以缓存将提供很少的额外好处，除非您进行如此多的计算，以至于毫秒的时间差异将积累到足以产生影响。
  2. 对于非常大的矩阵，如果您可能的输入矩阵非常有限，您可能会看到缓存的好处。如果它们可以是任何东西，那么可能的好处被缓存重复攻击的罕见性以及管理缓存的内存成本和复杂性所抵消。

缓存会加速结果，但仅限于非常有限的情况。

鉴于您也向图书馆寻求建议，这听起来像是过早优化的情况。我会在没有缓存的情况下实现您的程序，对其进行性能分析，如果您在数组算术中发现性能瓶颈，然后考虑优化数字运算的方法。

编辑：关于计算哈希：如果你有一个 n×m 矩阵 X，那么计算该矩阵的哈希至少与操作 R X C 一样复杂，其中 R 是行向量 [1,.., n] 和 C 是列向量 [1,..,m]。我还没有计算出最佳收益，但是对于 2x2、3x3 量级的非常小的矩阵，进行原始计算将比计算哈希更便宜。

于 2009-08-17T03:41:04.597 回答