Блог

Смотрите важное разъяснение в нижней части этого вопроса.

Я использую numpy для ускорения некоторой обработки координат долготы / широты. К сожалению, из-за моей «оптимизации» numpy мой код выполнялся примерно в 5 раз медленнее, чем без использования numpy.

Узким местом, по-видимому, является заполнение массива numpy моими данными, а затем извлечение этих данных после того, как я выполнил математические преобразования. Для заполнения массива у меня в основном есть цикл, подобный:

 point_list = GetMyPoints() # returns a long list of ( lon, lat ) coordinate pairs
n = len( point_list )
point_buffer = numpy.empty( ( n, 2 ), numpy.float32 )

for point_index in xrange( 0, n ):
    point_buffer[ point_index ] = point_list[ point_index ]
  

Этот цикл, просто заполняющий массив numpy, прежде чем даже работать с ним, выполняется чрезвычайно медленно, намного медленнее, чем все вычисления без numpy. (То есть дело не только в медлительности самого цикла python, но, по-видимому, в каких-то огромных накладных расходах на фактическую передачу каждого небольшого блока данных из python в numpy.) Аналогичная медлительность наблюдается и на другом конце; после обработки массивов numpy я обращаюсь к каждой измененной паре координат в цикле, опять же как

 some_python_tuple = point_buffer[ index ]
  

И снова этот цикл извлечения данных выполняется намного медленнее, чем все исходные вычисления без numpy. Итак, как мне на самом деле заполнить массив numpy и извлечь данные из массива numpy таким образом, чтобы это не противоречило цели использования numpy в первую очередь?

Я считываю данные из файла shape, используя библиотеку C, которая передает мне данные в виде обычного списка python. Я понимаю, что если бы библиотека передала мне координаты, уже находящиеся в массиве numpy, не было бы необходимости в «заполнении» массива numpy. Но, к сожалению, отправной точкой для меня с данными является обычный список python. И, что более важно, в целом я хочу понять, как вы быстро заполняете массив numpy данными из python.

Разъяснение

Цикл, показанный выше, на самом деле упрощен. Я написал это таким образом в этом вопросе, потому что хотел сосредоточиться на проблеме, с которой я столкнулся, пытаясь медленно заполнить массив numpy в цикле. Теперь я понимаю, что делать это просто медленно.

В моем реальном приложении у меня есть файл формы с координатными точками, и у меня есть API для извлечения точек для данного объекта. Существует что-то вроде 200 000 объектов. Поэтому я неоднократно вызываю функцию GetShapeCoords( i ) , чтобы получить координаты для объекта i. Это возвращает список списков, где каждый подсписок представляет собой список пар lon / lat, и причина, по которой это список списков, заключается в том, что некоторые объекты состоят из нескольких частей (т. Е. многоугольников). Затем, в моем исходном коде, когда я читал в точках каждого объекта, я выполнял преобразование в каждой точке, вызывая обычную функцию python, а затем выводил преобразованные точки с помощью PIL. На отрисовку всех 200 000 полигонов ушло около 20 секунд. Не страшно, но много возможностей для улучшения. Я заметил, что по крайней мере половина из этих 20 секунд была потрачена на выполнение логики преобразования, поэтому я подумал, что сделаю это в numpy. И моя первоначальная реализация заключалась в том, чтобы просто считывать объекты по одному и продолжать добавлять все точки из подсписков в один большой массив numpy, с которым я затем мог выполнять математические операции в numpy.

Итак, теперь я понимаю, что простая передача всего списка python в numpy — это правильный способ настроить большой массив. Но в моем случае я читаю только один объект за раз. Итак, одна вещь, которую я мог бы сделать, это продолжать добавлять точки вместе в большой список списков списков на python. И затем, когда я скомпилирую таким образом некоторое большое количество точек объектов (скажем, 10000 объектов), я мог бы просто назначить этот список монстров numpy.

Итак, мой вопрос теперь состоит из трех частей:

(a) Правда ли, что numpy может взять этот большой список списков неправильной формы и быстро его обработать?

(b) Затем я хочу иметь возможность преобразовывать все точки в листьях этого дерева-монстра. Какое выражение позволяет заставить numpy, например, «перейти в каждый подсписок, а затем в каждую подпублику, а затем для каждой пары координат, которую вы найдете в этих подпубликах, умножить первую (lon-координату) на 0,5»? Могу ли я это сделать?

(c) Наконец, мне нужно вернуть эти преобразованные координаты обратно, чтобы построить их график.

Приведенный ниже ответ Уинстона, кажется, дает некоторый намек на то, как я мог бы сделать все это с помощью itertools. То, что я хочу сделать, очень похоже на то, что делает Winston, выравнивая список. Но я не могу просто сгладить это. Когда я приступаю к рисованию данных, мне нужно знать, когда заканчивается один полигон и начинается следующий. Итак, я думаю, я мог бы заставить это работать, если бы существовал способ быстро отмечать конец каждого полигона (т. Е. каждого подсписка) специальной парой координат, такой как (-1000, -1000) или что-то в этом роде. Тогда я мог бы сгладить с помощью itertools, как в ответе Уинстона, а затем выполнить преобразования в numpy. Затем мне нужно на самом деле рисовать от точки к точке, используя PIL, и здесь, я думаю, мне нужно было бы переназначить измененный массив numpy обратно в список python, а затем выполнить итерацию по этому списку в обычном цикле python для выполнения рисования. Похоже ли это на мой лучший вариант, если не считать простого написания модуля C для обработки всего чтения и рисования за один шаг?

Вы описываете свои данные как «списки списков списков координат». Исходя из этого, я предполагаю, что ваше извлечение выглядит следующим образом:

 for x in points:
   for y in x:
       for Z in y:
           # z is a tuple with GPS coordinates
  

Сделайте это:

 # initially, points is a list of lists of lists
points = itertools.chain.from_iterable(points)
# now points is an iterable producing lists
points = itertools.chain.from_iterable(points)
# now points is an iterable producing coordinates
points = itertools.chain.from_iterable(points)
# now points is an iterable producing individual floating points values
data = numpy.fromiter(points, float)
# data is a numpy array containing all the coordinates
data = data.reshape( data.size/2,2)
# data has now been reshaped to be an nx2 array
  

itertools и numpy.fromiter реализованы на c и действительно эффективны. В результате преобразование должно выполняться очень быстро.

Вторая часть вашего вопроса на самом деле не указывает, что вы хотите сделать с данными. Индексирование массива numpy происходит медленнее, чем индексирование списков python. Вы получаете скорость, выполняя массовые операции с данными. Не зная больше о том, что вы делаете с этими данными, трудно предложить, как это исправить.

Обновить:

Я пошел дальше и сделал все, используя itertools и numpy. Я не несу ответственности за какие-либо повреждения мозга в результате попытки понять этот код.

 # firstly, we use imap to call GetMyPoints a bunch of times
objects = itertools.imap(GetMyPoints, xrange(100))
# next, we use itertools.chain to flatten it into all of the polygons
polygons = itertools.chain.from_iterable(objects)
# tee gives us two iterators over the polygons
polygons_a, polygons_b = itertools.tee(polygons)
# the lengths will be the length of each polygon
polygon_lengths = itertools.imap(len, polygons_a)
# for the actual points, we'll flatten the polygons into points
points = itertools.chain.from_iterable(polygons_b)
# then we'll flatten the points into values
values = itertools.chain.from_iterable(points)

# package all of that into a numpy array
all_points = numpy.fromiter(values, float)
# reshape the numpy array so we have two values for each coordinate
all_points = all_points.reshape(all_points.size // 2, 2)

# produce an iterator of lengths, but put a zero in front
polygon_positions = itertools.chain([0], polygon_lengths)
# produce another numpy array from this
# however, we take the cumulative sum
# so that each index will be the starting index of a polygon
polygon_positions = numpy.cumsum( numpy.fromiter(polygon_positions, int) )

# now for the transformation
# multiply the first coordinate of every point by *.5
all_points[:,0] *= .5

# now to get it out

# polygon_positions is all of the starting positions
# polygon_postions[1:] is the same, but shifted on forward,
# thus it gives us the end of each slice
# slice makes these all slice objects
slices = itertools.starmap(slice, itertools.izip(polygon_positions, polygon_positions[1:]))
# polygons produces an iterator which uses the slices to fetch
# each polygon
polygons = itertools.imap(all_points.__getitem__, slices)

# just iterate over the polygon normally
# each one will be a slice of the numpy array
for polygon in polygons:
    draw_polygon(polygon)
  

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

Это сложнее, чем большинство numpy-материалов, из-за ваших данных странной формы. Numpy в значительной степени предполагает использование данных одинаковой формы.

Смысл использования массивов numpy в том, чтобы максимально избегать циклов for. Самостоятельное написание циклов for приведет к замедлению кода, но с массивами numpy вы можете использовать предопределенные векторизованные функции, которые намного быстрее (и проще!).

Итак, для преобразования списка в массив вы можете использовать:

 point_buffer = np.array(point_list)
  

Если список содержит элементы типа (lat, lon) , то он будет преобразован в массив с двумя столбцами.

С помощью этого массива numpy вы можете легко манипулировать всеми элементами одновременно. Например, чтобы умножить первый элемент каждой пары координат на 0,5, как в вашем вопросе, вы можете сделать просто (предполагая, что первые элементы, например, находятся в первом столбце):

 point_buffer[:,0] * 0.5
  

Это будет быстрее:

 numpy.array(point_buffer, dtype=numpy.float32)
  

Модифицируйте массив, а не список. Очевидно, что было бы лучше по возможности избегать создания списка в первую очередь.

Правка 1: профилирование

Вот некоторый тестовый код, который демонстрирует, насколько эффективно numpy преобразует списки в массивы (это хорошо). И что моя идея преобразования списка в буфер сравнима только с тем, что делает numpy, не лучше.

 import timeit

setup = '''
import numpy
import itertools
import struct
big_list = numpy.random.random((10000,2)).tolist()'''

old_way = '''
a = numpy.empty(( len(big_list), 2), numpy.float32)
for i,e in enumerate(big_list):
    a[i] = e
'''

normal_way = '''
a = numpy.array(big_list, dtype=numpy.float32)
'''

iter_way = '''
chain = itertools.chain.from_iterable(big_list)
a = numpy.fromiter(chain, dtype=numpy.float32)
'''

my_way = '''
chain = itertools.chain.from_iterable(big_list)
buffer = struct.pack('f'*len(big_list)*2,*chain)
a = numpy.frombuffer(buffer, numpy.float32)
'''

for way in [old_way, normal_way, iter_way, my_way]:
    print timeit.Timer(way, setup).timeit(1)
  

Результаты:

 0.22445492374
0.00450378469941
0.00523579114088
0.00451488946237
  

Правка 2: относительно иерархического характера данных

Если я понимаю, что данные всегда представляют собой список списков списков (объект — полигон — координата), то я бы выбрал такой подход: уменьшите данные до наименьшего размера, который создает квадратный массив (в данном случае 2D) и отслеживайте индексы ветвей более высокого уровня с помощью отдельного массива. По сути, это реализация идеи Уинстона об использовании numpy.fromiter объекта цепочки itertools. Единственная добавленная идея — индексирование ветвей.

 import numpy, itertools

# heirarchical list of lists of coord pairs
polys = [numpy.random.random((n,2)).tolist() for n in [5,7,12,6]]

# get the indices of the polygons:
lengs = numpy.array([0] [len(l) for l in polys])
p_idxs = numpy.add.accumulate(lengs)

# convert the flattend list to an array:
chain = itertools.chain.from_iterable
a = numpy.fromiter(chain(chain(polys)), dtype=numpy.float32).reshape(lengs.sum(), 2)

# transform the coords
a *= .5

# get a transformed polygon (using the indices)
def get_poly(n):
    i0 = p_idxs[n]
    i1 = p_idxs[n 1]
    return a[i0:i1]

print 'poly2', get_poly(2)
print 'poly0', get_poly(0)