numpy массивы: быстрое заполнение и извлечение данных

Question

См. Важные разъяснения внизу этого вопроса.

Я использую numpy для ускорения обработки координат долготы / широты. К сожалению, из-за моих «неловких» оптимизаций мой код выполнялся примерно в 5 раз медленнее , чем без использования 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.) На другом конце есть аналогичная медлительность; после того, как я обработал пустые массивы, я получаю доступ к каждой измененной координатной паре в цикле, снова как

some_python_tuple = point_buffer[ index ]

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

Я читаю данные из файла формы, используя библиотеку C, которая передает мне данные в виде обычного списка Python. Я понимаю, что если бы библиотека передавала мне координаты уже в массиве NumPy, не было бы необходимости в "заполнении" NUMPY массива. Но, к сожалению, отправной точкой для меня с данными является обычный список питонов. И что еще важнее, в общем, я хочу понять, как вы быстро заполняете массивный массив данными из Python.

Разъяснение

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

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

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

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

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

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

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

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

Answer 1

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

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. Вы получаете скорость, выполняя массовые операции с данными. Не зная больше о том, что вы делаете с этими данными, трудно предложить, как это исправить.

UPDATE:

Я пошел вперед и сделал все, используя 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 в значительной степени предполагает мир данных однородной формы.

Answer 2

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

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

point_buffer = np.array(point_list)

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

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

point_buffer[:,0] * 0.5

Answer 3

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

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

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

Редактировать 1: профилирование

Вот некоторый тестовый код, который демонстрирует, насколько эффективно numy преобразует списки в массивы (это хорошо).И что моя идея списка в буфере сравнима только с тем, что делает 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)