高效地生成python中點的點陣

Question

幫助我更快地編寫代碼：我的python代碼需要生成位於邊界矩形內的點的二維點陣。我將一些代碼（如下所示）彙集在一起​​生成此格。然而，這個函數被多次調用，並且已經成爲我應用程序中的一個嚴重瓶頸。

我相信有一個更快的方法來做到這一點，可能涉及numpy數組而不是列表。任何建議更快，更優雅的方式來做到這一點？

功能描述： 我有兩個2D矢量，v1和v2。這些載體define a lattice。就我而言，我的矢量定義了一個幾乎但不完全是六角形的格子。我想生成一些邊界矩形中的這個點陣上的所有二維點的集合。在我的情況下，矩形的其中一個角位於（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

如果你想要矢量化整個事物，生成一個正方形格子然後剪切它。然後切掉落在你盒子外面的邊緣。

這是我想出來的。還有很多可以改進的地方，但這是基本的想法。

def generate_lattice(image_shape, lattice_vectors) : 
    center_pix = numpy.array(image_shape) // 2 
    # Get the lower limit on the cell size. 
    dx_cell = max(abs(lattice_vectors[0][0]), abs(lattice_vectors[1][0])) 
    dy_cell = max(abs(lattice_vectors[0][1]), abs(lattice_vectors[1][1])) 
    # Get an over estimate of how many cells across and up. 
    nx = image_shape[0]//dx_cell 
    ny = image_shape[1]//dy_cell 
    # Generate a square lattice, with too many points. 
    # Here I generate a factor of 4 more points than I need, which ensures 
    # coverage for highly sheared lattices. If your lattice is not highly 
    # sheared, than you can generate fewer points. 
    x_sq = np.arange(-nx, nx, dtype=float) 
    y_sq = np.arange(-ny, nx, dtype=float) 
    x_sq.shape = x_sq.shape + (1,) 
    y_sq.shape = (1,) + y_sq.shape 
    # Now shear the whole thing using the lattice vectors 
    x_lattice = lattice_vectors[0][0]*x_sq + lattice_vectors[1][0]*y_sq 
    y_lattice = lattice_vectors[0][1]*x_sq + lattice_vectors[1][1]*y_sq 
    # Trim to fit in box. 
    mask = ((x_lattice < image_shape[0]/2.0) 
      & (x_lattice > -image_shape[0]/2.0)) 
    mask = mask & ((y_lattice < image_shape[1]/2.0) 
        & (y_lattice > -image_shape[1]/2.0)) 
    x_lattice = x_lattice[mask] 
    y_lattice = y_lattice[mask] 
    # Translate to the centre pix. 
    x_lattice += center_pix[0] 
    y_lattice += center_pix[1] 
    # Make output compatible with original version. 
    out = np.empty((len(x_lattice), 2), dtype=float) 
    out[:, 0] = y_lattice 
    out[:, 1] = x_lattice 
    return out 

Answer 2

由於lower_bounds和upper_bounds只有2個元素組成的數組，numpy的可能不是這裏的正確選擇。嘗試使用基本的Python的東西來代替

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

：

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-diminsional數據，如果你不需要雙精度浮點數，使用基本的Python數據類型和構造inst通常會更快ead of numpy，在這種情況下有點過載 - 請看this other question。

---

另一個小的改進可能是隻計算一次range(-num_vectors, num_vectors)然後重新使用它。此外，您可能希望使用product iterator而不是嵌套循環 - 儘管我不認爲這些更改會對性能產生重大影響。

Answer 3

也許你可以用這個替換兩個for循環。

i,j = numpy.mgrid[-num_vectors:num_vectors, -num_vectors:num_vectors] 
numel = num_vectors ** 2; 
i = i.reshape(numel, 1) 
j = j.reshape(numel, 1) 
lp = i * lattice_vectors[0] + j * lattice_vectors[1] + center_pix 
valid = numpy.all(lower_bounds < lp, 1) and numpy.all(lp < upper_bounds, 1) 
lattice_points = lp[valid] 

可能會有一些小錯誤，但您明白了。

編輯

我做編輯的 「numpy.all（lower_bounds ..）」 考慮到正確的尺寸。

Answer 4

我得到了比2X加速更通過重複添加而不是乘法免去您的lp計算。 xrange優化似乎是無足輕重的（儘管它可能不會受傷）;重複添加似乎比乘法更有效。將這與上面提到的其他優化結合起來應該會給你更多的加速。但是，當然，最好的你可以得到一個恆定的因素加速，因爲你的輸出的大小是二次的，就像你的原始代碼一樣。

lv0, lv1 = lattice_vectors[0], lattice_vectors[1] 
lv0_i = -num_vectors * lv0 + center_pix 
lv1_orig = -num_vectors * lv1 
lv1_j = lv1_orig 
for i in xrange(-num_vectors, num_vectors): 
    for j in xrange(-num_vectors, num_vectors): 
     lp = lv0_i + lv1_j 
     if all(lower_bounds < lp) and all(lp < upper_bounds): 
      lattice_points.append(lp) 
     lv1_j += lv1 
    lv0_i += lv0 
    lv1_j = lv1_orig 

定時器結果：

>>> t = Timer("generate_lattice(image_shape, lattice_vectors, orig=True)", "from __main__ import generate_lattice, lattice_vectors, image_shape") 
>>> print t.timeit(number=50) 
5.20121788979 
>>> t = Timer("generate_lattice(image_shape, lattice_vectors, orig=False)", "from __main__ import generate_lattice, lattice_vectors, image_shape") 
>>> print t.timeit(number=50) 
2.17463898659