如何提高 scipy.sparse.csgraph.breadth_first_order 性能？
How to improve scipy.sparse.csgraph.breadth_first_order performance?
import numpy as np
from scipy.sparse import csgraph, dia_matrix
n = 1000
g = dia_matrix((np.ones(n), 1), shape=(n, n)).tocsr()
for i in range(100):
for j in range(n):
csgraph.breadth_first_order(g, j)
我写了这段代码并分析了它。
breadth_first_order函数大部分时间都在验证我传入的图g。如何提高这个函数的性能？
有没有办法让 SciPy 只验证一次图表？
在不更改现有代码的情况下，没有什么可做的：您已经在 happy path 上，所有验证所做的就是创建相同 dtype 的新 csr_matrix不创建任何副本。
但是，如果您的工作流程可以使用 Cython，您也可以完全跳过验证，直接使用底层方法，_breadth_first_directed。请注意，这样做会失去 SciPy 的 API 稳定性承诺，并且该功能可能会在未来版本中更改（或完全删除），恕不另行通知。
或者，如果您不介意猴子补丁，您可以简单地用身份替换导入的验证函数（再次依赖实现细节）；这有效地删除了所有验证并确实创建了您正在寻找的性能改进：
In [2]: import scipy.sparse.csgraph
In [3]: %timeit scipy.sparse.csgraph.breadth_first_order(g, 0)
34.9 µs ± 315 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [4]: scipy.sparse.csgraph._traversal.validate_graph = lambda csgraph, *args, **kwargs: csgraph
In [5]: %timeit scipy.sparse.csgraph.breadth_first_order(g, 0)
8.6 µs ± 82.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
如果您认为这通常是一个 useful/common 用例，您可以在 SciPy GitHub issue page requesting a way to skip validation. Or, open up the discussion on the SciPy-Dev mailing list.
上提出问题
import numpy as np
from scipy.sparse import csgraph, dia_matrix
n = 1000
g = dia_matrix((np.ones(n), 1), shape=(n, n)).tocsr()
for i in range(100):
for j in range(n):
csgraph.breadth_first_order(g, j)
我写了这段代码并分析了它。
breadth_first_order函数大部分时间都在验证我传入的图g。如何提高这个函数的性能？
有没有办法让 SciPy 只验证一次图表？
在不更改现有代码的情况下，没有什么可做的：您已经在 happy path 上，所有验证所做的就是创建相同 dtype 的新 csr_matrix不创建任何副本。
但是，如果您的工作流程可以使用 Cython，您也可以完全跳过验证，直接使用底层方法，_breadth_first_directed。请注意，这样做会失去 SciPy 的 API 稳定性承诺，并且该功能可能会在未来版本中更改（或完全删除），恕不另行通知。
或者，如果您不介意猴子补丁，您可以简单地用身份替换导入的验证函数（再次依赖实现细节）；这有效地删除了所有验证并确实创建了您正在寻找的性能改进：
In [2]: import scipy.sparse.csgraph
In [3]: %timeit scipy.sparse.csgraph.breadth_first_order(g, 0)
34.9 µs ± 315 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [4]: scipy.sparse.csgraph._traversal.validate_graph = lambda csgraph, *args, **kwargs: csgraph
In [5]: %timeit scipy.sparse.csgraph.breadth_first_order(g, 0)
8.6 µs ± 82.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
如果您认为这通常是一个 useful/common 用例，您可以在 SciPy GitHub issue page requesting a way to skip validation. Or, open up the discussion on the SciPy-Dev mailing list.
上提出问题