умное вычисление расстояний по (разреженному?) numpy.meshgrid - PullRequest
Новая
       13

умное вычисление расстояний по (разреженному?) numpy.meshgrid

0 голосов
/ 15 января 2019

Я хочу вычислить расстояния между каждой парой узлов на обычной 3D-сетке. Сетка может быть огромной, поэтому я хочу оптимизировать вычисления (привилегия для процессора).

После многих многочисленных тестов я отказался от модуля «scitools», который удобен только для python2, и использовал комбинацию numpy.meshgrid () и scipy.spatial.distance.pdist (). Например, для сетки 20x20x20: 

distances = scipy.spatial.distance.pdist(np.transpose(np.array(np.meshgrid(range(-10,10,1),range(-10,10,1),range(-10,10,1)))).reshape([20**3,3]))

Оптимизировано ли это?

first 'Может быть, это и есть путь ...' 

np.meshgrid(range(-10,10,1),range(-10,10,1),range(-10,10,1),sparse=True)

вместо 

np.meshgrid(range(-10,10,1),range(-10,10,1),range(-10,10,1))

Действительно, я мог бы даже сохранить разреженную форму в памяти, так как это было бы удобно позже в коде. Но я не нахожу удовлетворительного синтаксиса для объединения pdist () с разреженной сеткой.

Ответы [ 2 ]

0 голосов
/ 15 января 2019 
In [494]: [x.shape for x in np.meshgrid(range(-10,10,1),range(-10,10,1),range(-1
     ...: 0,10,1),sparse=False)]
Out[494]: [(20, 20, 20), (20, 20, 20), (20, 20, 20)]
In [495]: [x.shape for x in np.meshgrid(range(-10,10,1),range(-10,10,1),range(-1
     ...: 0,10,1),sparse=True)]
Out[495]: [(1, 20, 1), (20, 1, 1), (1, 1, 20)]

Не разреженная сетка создает 3 трехмерных массива, которые вы присоединяете и преобразуете в массив из 3 столбцов. Редкая версия также производит 3D-массивы, но каждый из них имеет свою форму. С broadcasting они могут использоваться таким же образом. Например, если сумма или умножена, результатом в обоих случаях является (20,20,20) массив. Но редкие из них не могут быть превращены в этот (20 * 20 * 20,3) массив без расширения.

Это не scipy sparse массивы. Это совершенно другая концепция.

Посмотрите на один из этих (20,20,20) массивов. Видите все повторяющиеся столбцы или строки? sparse просто избегает повторять это. Он просто берет 20 элементов range и изменяет их. Это позволяет broadcasting делать неявные повторения.

0 голосов
/ 15 января 2019

Я не уверен, что использование разреженной сетки поможет вам. Вы можете сэкономить место в самой сетке, но все равно необходимо будет вычислить такое же количество парных расстояний, и конечный результат все равно будет «сжатой» матрицей согласно документации на pdist.

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

Вот алгоритм:

  1. Перебрать все пары координат

  2. Создайте «кэш расстояния», который использует разницу между парами координат в качестве ключа. Например, distance_cache [(3,4)] = 5. Таким образом, если найдены две координаты, имеющие одинаковое относительное расстояние друг от друга, расстояние между координатами просто ищется из кэша, а не пересчитывается.

  3. Бонусные баллы: в кеше расстояния хранятся только те ключи, у которых x и y относительно простые. Из-за сходства треугольников одна и та же запись кэша может быть повторно использована для кратных ключа. Например, расстояние ([6,8], [0,0]) = 2 * d [(3,4)] = 10

...