python - 在python中高效地生成点阵

Question

帮助使我的代码更快:我的 python 代码需要生成落在边界矩形内的点的二维点阵。我拼凑了一些生成这个格子的代码(如下所示)。然而，这个函数被调用了很多次，已经成为我应用程序的严重瓶颈。

我确信有一种更快的方法可以做到这一点，可能涉及 numpy 数组而不是列表。对于更快、更优雅的方法有什么建议吗？

功能说明:我有两个二维向量，v1 和 v2。这些载体 define a lattice .在我的例子中，我的向量定义了一个几乎但不完全是六边形的格子。我想生成此晶格上位于某个边界矩形中的所有 2D 点的集合。在我的例子中，矩形的一个角位于 (0, 0)，其他角位于正坐标。

示例:如果我的边界矩形的远角位于 (3, 3)，并且我的点阵向量是:

v1 = (1.2, 0.1)
v2 = (0.2, 1.1)

我希望我的函数返回点数:

(1.2, 0.1) #v1
(2.4, 0.2) #2*v1
(0.2, 1.1) #v2
(0.4, 2.2) #2*v2
(1.4, 1.2) #v1 + v2
(2.6, 1.3) #2*v1 + v2
(1.6, 2.3) #v1 + 2*v2
(2.8, 2.4) #2*v1 + 2*v2

我不关心边缘情况；例如，函数是否返回 (0, 0) 并不重要。

我目前做的比较慢:

import numpy, pylab

def generate_lattice( #Help me speed up this function, please!
    image_shape, lattice_vectors, center_pix='image', edge_buffer=2):

    ##Preprocessing. Not much of a bottleneck:
    if center_pix == 'image':
        center_pix = numpy.array(image_shape) // 2
    else: ##Express the center pixel in terms of the lattice vectors
        center_pix = numpy.array(center_pix) - (numpy.array(image_shape) // 2)
        lattice_components = numpy.linalg.solve(
            numpy.vstack(lattice_vectors[:2]).T,
            center_pix)
        lattice_components -= lattice_components // 1
        center_pix = (lattice_vectors[0] * lattice_components[0] +
                      lattice_vectors[1] * lattice_components[1] +
                      numpy.array(image_shape)//2)
    num_vectors = int( ##Estimate how many lattice points we need
        max(image_shape) / numpy.sqrt(lattice_vectors[0]**2).sum())
    lattice_points = []
    lower_bounds = numpy.array((edge_buffer, edge_buffer))
    upper_bounds = numpy.array(image_shape) - edge_buffer

    ##SLOW LOOP HERE. 'num_vectors' is often quite large.
    for i in range(-num_vectors, num_vectors):
        for j in range(-num_vectors, num_vectors):
            lp = i * lattice_vectors[0] + j * lattice_vectors[1] + center_pix
            if all(lower_bounds < lp) and all(lp < upper_bounds):
                lattice_points.append(lp)
    return lattice_points


##Test the function and display the output.
##No optimization needed past this point.
lattice_vectors = [
    numpy.array([-40., -1.]),
    numpy.array([ 18., -37.])]
image_shape = (1000, 1000)
spots = generate_lattice(image_shape, lattice_vectors)

fig=pylab.figure()
pylab.plot([p[1] for p in spots], [p[0] for p in spots], '.')
pylab.axis('equal')
fig.show()

Answer 1

因为 lower_bounds 和 upper_bounds 只是二元数组，numpy 在这里可能不是正确的选择。尝试替换

if all(lower_bounds < lp) and all(lp < upper_bounds):

使用基本的 Python 内容:

if lower1 < lp and lower2 < lp and lp < upper1 and lp < upper2:

根据timeit，第二种方法要快得多:

>>> timeit.timeit('all(lower < lp)', 'import numpy\nlp=4\nlower = numpy.array((1,5))') 
3.7948939800262451
>>> timeit.timeit('lower1 < 4 and lower2 < 4', 'lp = 4\nlower1, lower2 = 1,5') 
0.074192047119140625

根据我的经验，只要您不需要处理 n 维数据并且不需要 double float ，通常使用基本 Python 数据类型和构造而不是 numpy 会更快，在这种情况下有点过载——看看 this other question .

---

另一个小的改进可能是只计算一次 range(-num_vectors, num_vectors) 然后重新使用它。此外，您可能想使用 product iterator而不是嵌套的 for 循环——尽管我认为这些更改不会对性能产生重大影响。