Эффективно генерировать решетку точек в питоне - PullRequest
8 голосов
/ 26 мая 2011

Помогите ускорить мой код : моему коду Python необходимо создать двумерную решетку точек, которые попадают в ограничивающий прямоугольник. Я собрал воедино некоторый код (показанный ниже), который генерирует эту решетку. Однако эта функция вызывается много раз и стала серьезным узким местом в моем приложении.

Я уверен, что есть более быстрый способ сделать это, возможно, задействуя массивы вместо списков. Любые предложения для более быстрого и элегантного способа сделать это?

Описание функции : У меня есть два 2D вектора, v1 и v2. Эти векторы определяют решетку . В моем случае мои векторы определяют решетку, которая почти, но не совсем, шестиугольная. Я хочу сгенерировать набор всех 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()

Ответы [ 4 ]

6 голосов
/ 27 мая 2011

Поскольку 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-уменьшенные данные и если вам не нужны плавающие числа с двойной точностью, обычно быстрее использовать основные типы данных и конструкции Python вместо numpy , что в некоторых случаях немного перегружено - посмотрите на этот другой вопрос .


Еще одним незначительным улучшением может быть вычисление range(-num_vectors, num_vectors) только один раз, а затемиспользовать егоКроме того, вы можете захотеть использовать итератор продукта вместо вложенного цикла for - хотя я не думаю, что эти изменения окажут существенное влияние на производительность.

4 голосов
/ 27 мая 2011

Если вы хотите векторизовать все это, создайте квадратную решетку, а затем срежьте ее. Затем отрежьте края, которые приземляются за пределами вашей коробки.

Вот то, что я придумал. Есть еще много улучшений, которые можно сделать, но это основная идея.

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
3 голосов
/ 27 мая 2011

Может быть, вы можете заменить две петли для этого.

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]

Могут быть небольшие ошибки, но вы понимаете ...

EDIT

Я внес правку в «numpy.all (lower_bounds ..)», чтобы учесть правильный размер.

1 голос
/ 27 мая 2011

Я получил более чем двукратное ускорение, заменив вычисление lp повторными сложениями, а не умножениями.Оптимизация xrange кажется несущественной (хотя, вероятно, это не повредит);повторные добавления кажутся более эффективными, чем умножения.Объединение этого с другими оптимизациями, упомянутыми выше, даст вам больше ускорения.Но, конечно, лучшее, что вы можете получить - это ускорение на постоянный коэффициент, поскольку размер вашего вывода является квадратичным, как и ваш исходный код.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...