0

我想计算常规 3D 网格上每对节点之间的距离。网格可能很大，所以我想优化计算（CPU 特权）。

经过多次测试，我放弃了仅对python2方便的'scitools'模块，并使用了numpy.meshgrid()和scipy.spatial.distance.pdist()的组合。例如，对于 20x20x20 网格：

distances = scipy.spatial.distance.pdist(np.transpose(np.array(np.meshgrid(range(-10,10,1),range(-10,10,1),range(-10,10,1)))).reshape([20**3,3]))

优化了吗？

第一个'也许这是要走的路......'：我看到meshgrid中有一个'sparse'选项，所以我很乐意使用

np.meshgrid(range(-10,10,1),range(-10,10,1),range(-10,10,1),sparse=True)

而不是

np.meshgrid(range(-10,10,1),range(-10,10,1),range(-10,10,1))

事实上，我什至可以将稀疏形状保留在内存中，因为它在代码的后面会很方便。但是我没有找到令人满意的语法来将 pdist() 与稀疏网格网格结合起来。

4

2 回答 2

1

我不确定使用稀疏网格会为您带来什么。您可以节省网格网格本身的空间，但仍需要计算相同数量的成对距离，最终结果仍将是根据 pdist 上的文档的“压缩”矩阵。

如果您正在尝试优化将要执行的距离计算的数量，那么网格定期间隔的事实立即暗示了一些优化。

这是一个算法：

  1. 循环遍历所有坐标对

  2. 创建一个“距离缓存”，它使用坐标对之间的差异作为键。例如，distance_cache[(3,4)] = 5。这样，如果找到两个相对距离相同的坐标，则只需从缓存中查找坐标之间的距离，而不是重新计算。

  3. 加分项：仅将 x 和 y 互质的键存储在距离缓存中。由于三角形相似性，相同的缓存条目可以重复用于多个键。例如，距离([6,8], [0,0]) = 2 * d[(3,4)] = 10

于 2019-01-15T17:38:07.620 回答
0 
In [494]: [x.shape for x in np.meshgrid(range(-10,10,1),range(-10,10,1),range(-1
     ...: 0,10,1),sparse=False)]
Out[494]: [(20, 20, 20), (20, 20, 20), (20, 20, 20)]
In [495]: [x.shape for x in np.meshgrid(range(-10,10,1),range(-10,10,1),range(-1
     ...: 0,10,1),sparse=True)]
Out[495]: [(1, 20, 1), (20, 1, 1), (1, 1, 20)]

非稀疏网格生成 3 个 3d 数组，您可以将它们加入并重塑为 3 列数组。稀疏版本也产生 3d 数组，但每个都有不同的形状。broadcasting它们可以以相同的方式使用。例如，如果求和或相乘，两种情况下的结果都是 (20,20,20) 数组。但是稀疏的不能在没有扩展的情况下变成 (20*20*20,3) 数组。

这些不是scipy sparse数组。那是一个完全不同的概念。

看看其中一个(20,20,20)数组。查看所有重复的列或行？ sparse只是避免重复这些。它只需要 20 个元素range并对其进行重塑。它可以broadcasting进行隐式重复。

于 2019-01-15T19:57:08.253 回答