6

即使所有内容似乎都已矢量化，以下代码运行速度也很慢。

from numpy import *
from scipy.sparse import *

n = 100000;
i = xrange(n); j = xrange(n);
data = ones(n);

A=csr_matrix((data,(i,j)));

x = A[i,j]

问题似乎是索引操作是作为python函数实现的，调用A[i,j]结果会产生以下分析输出

         500033 function calls in 8.718 CPU seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   100000    7.933    0.000    8.156    0.000 csr.py:265(_get_single_element)
        1    0.271    0.271    8.705    8.705 csr.py:177(__getitem__)
(...)

也就是说，python 函数_get_single_element被调用了 100000 次，这确实是低效的。为什么这不是在纯 C 中实现的？有人知道绕过这个限制并加快上述代码的方法吗？我应该使用不同的稀疏矩阵类型吗？

4

2 回答 2

7

您可以A.diagonal()更快地检索对角线（在我的机器上为 0.0009 秒与 3.8 秒）。但是，如果您想进行任意索引，那么这是一个更复杂的问题，因为您使用的不是切片，而是索引列表。_get_single_element 函数被调用了 100000 次，因为它只是遍历您传递给它的迭代器（i 和 j）。切片将是 A[30:60,10] 或类似的东西。

此外，csr_matrix(eye(n,n))为了简单起见，我会使用迭代器制作相同的矩阵。

更新：

好的，因为您的问题确实是关于能够快速访问大量随机元素，所以我会尽我所能回答您的问题。

  • 为什么这不是在纯 C 中实现的？

答案很简单：没有人能解决这个问题。据我所见，在 Scipy 的稀疏矩阵模块领域还有很多工作要做。在 C 中实现的一部分是不同稀疏矩阵格式之间的转换。

  • 有人知道绕过这个限制并加快上述代码的方法吗？

您可以尝试深入研究稀疏矩阵模块并尝试加快它们的速度。我这样做了，并且在尝试上面的代码以使用 csr 矩阵进行随机访问时，能够将时间减少到原来的三分之一以下。我必须直接访问 _get_single_element 并大幅削减代码才能做到这一点，包括进行绑定检查。

但是，使用 lil_matrix 仍然更快（尽管初始化矩阵的速度较慢），但我必须使用列表理解进行访问，因为 lil 矩阵没有针对您正在执行的索引类型设置。顺便说一下，对 csr_matrix 使用列表推导仍然使 lil 矩阵方法遥遥领先。最终，lil 矩阵在访问随机元素时更快，因为它没有被压缩。

使用原始形式的 lil_matrix 运行的时间大约是上面列出的代码的五分之一。如果我取出一些绑定检查并直接调用 lil_matrix 的 _get1() 方法，我可以将时间进一步降低大约 7% 的原始时间。为了清楚起见，这是从 3.4-3.8 秒到大约 0.261 秒的加速。

最后，我尝试制作自己的函数，直接访问 lil 矩阵的数据并避免重复的函数调用。时间约为 0.136 秒。这没有利用正在排序的数据，这是另一个潜在的优化（特别是如果您正在访问同一行上的许多元素）。

如果您想要比这更快，那么您可能必须编写自己的 C 代码稀疏矩阵实现。

  • 我应该使用不同的稀疏矩阵类型吗？

好吧，如果您的意图是访问大量元素，我建议使用 lil 矩阵，但这完全取决于您需要做什么。例如，您是否还需要乘以矩阵？请记住，至少有时（在某些情况下）矩阵之间的更改可能会非常快，因此不排除更改为不同的矩阵格式来执行不同的操作。

如果您实际上不需要对矩阵进行任何代数运算，那么也许您应该只使用 defaultdict 或类似的东西。defaultdicts 的危险在于，每当请求一个不在字典中的元素时，它都会将该项目设置为默认值并将其存储起来，这样可能会出现问题。

于 2010-03-08T21:14:23.027 回答
0

我认为 _get_single_element 仅在使用“object”的默认 dtype 时才被调用。您是否尝试过提供 dtype，例如csr_matrix((data, (i,j)), dtype=int32)

于 2010-03-08T21:30:17.837 回答