3

我在 1000 x 1000 网格中使用 scipy.interpolate.griddata 进行插值。当我有一个具有 1,000 个 (x,y,z) 值的点云时，计算只需要几秒钟。但现在我有 1,000,000 个值。所以我创建了一个循环来从这 1,000,000 个值中提取 1,000 个值，如下所示：

p = [...]
z = [...]
#p and z are my lists with 1,000,000 values
p_new = []
z_new = []
for i in range(1000000):
    if condition:
        #condition is True for about 1000 times
        p_new.append(p[i])
        z_new.append(z[i])
print 'loop finished'

points = np.array(p_new)
values = np.array(z_new)
grid_z1 = griddata(points, values, (grid_x, grid_y), method='cubic')
plt.imshow(grid_z1.T, origin='lower')
plt.show()

print len(p_new)返回 me 1000，所以我的循环按预期工作。但是在我的循环完成后，我在等待 15 分钟后取消了我的程序，因为什么也没发生。

所以最后我的问题是：尽管在这两种情况下（默认情况下为 1000 个值和从 1000000 中提取它们的 1000 个值）我有相同数量的值，为什么要花这么长时间？在我的输出loop finished中，我可以看到循环只需要大约 10 秒，所以它应该与我的循环无关 =/

4

1 回答 1

1

我在这里看不到任何异常情况——据我所知，插值所需的时间大致与点云中元素的数量成正比。

下面是一些测试数据：

def fake_data(n):

    # xy coordinates for an n-by-n grid
    grid = np.indices((n,n),dtype=np.float32).reshape(2,-1).T

    # interpolated coordinates
    xy_i = grid.copy()
    # not monotonically increasing
    np.random.shuffle(xy_i)

    # values
    z = np.random.rand(n**2)

    # input coordinates
    xy = grid.copy()
    # not regularly gridded 
    xy += np.random.rand(*xy_i.shape)*0.25

    # pick n random points to use
    inc = np.random.choice(np.arange(n**2),(n,),replace=False)
    xy = grid[inc,:]
    z = z[inc]

    return xy, z, xy_i

在此处输入图像描述

对于所有三种方法， N与时间的对数图大致是一条直线，斜率为~2，即它们都需要O(N^2)时间。

如果在您的情况下，您看到线条不是直的，而是向上偏离N的较大值，这可能表明您遇到了其他问题，例如内存不足和命中交换。

于 2013-10-02T01:38:49.917 回答