速度提升到邻接矩阵

Question

我目前有一个算法，可以在大小为n的邻接矩阵上运算。在我的算法中，我需要一次将整行或列整除。我的实现目前是O（m）或O（n），取决于它是列还是行。

有什么办法零出在O（1）时间一列或行？

Answer 1

本质上，这取决于您正在处理的芯片架构。对于大多数CPU而言，不可能在整个过程中将整个存储器清零，因此无论编程语言提供什么设施，每个单词都需要单独的存储器操作。

它帮助很大，如果你的内存是连续的内存访问时间，因为毗邻刚刚访问内存的内存将被缓存，以及随后的访问将命中缓存，导致快速的性能。

这样做的结果是，如果矩阵很大，一次一行或一列零列可能会更快，而反之亦然，这取决于您的数据是按列写入还是按列写入按行。

编辑：我认为你的矩阵是不疏，或三角形，或其他特殊的，因为你谈论“归零一整排”。如果你知道你的矩阵大部分是空的或者以某种方式适合一种特殊的模式，你可以用不同的方式表示你的矩阵（而不是一个简单的nxm数组），故事会有所不同。但是如果你现在有一个nxm矩阵，那么情况就是这样。

Answer 2

是距离度量，并且是无向图？ （在这种情况下矩阵是对称的）。在这种情况下，您可以在整个程序中对较低或较高的三角形矩阵进行操作。用这种方法，你只需要输出一行（或者如果你正在处理上三角）。即使如此，它也不会是整排，平均一半。

Answer 3

这取决于你的矩阵是如何实现的。

如果你有一个表示诸如数组的数组，可以为您检查不随后写入它指向一个共享归零元件阵列，只要。这意味着一行或一行中的一行可以在O（N）中归零，而在所有其他写操作上的成本不变。

你也可以有一对数组 - 一个用于行，一个列 - 这缩放值矩阵。将零置入其中将是O（1）操作来屏蔽掉一行或一列，但以每次读取的额外处理为代价;但是如果这是一个常见的用例，它可能是一种临时从图形中删除节点的方式。它也会保持矩阵的原始版本不变，因此您可以对算法进行并行处理（假设它需要的唯一操作是修剪所有边缘进入或离开节点）。