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

Question

Я хочу вычислить расстояния между каждой парой узлов на обычной 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 "Может быть, это путь...": я вижу, что в meshgrid есть опция "разреженная", так что мне было бы приятно использовать

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 () с разреженной сеткой.

Answer 1

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

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

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

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

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

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

Answer 2

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 делать неявные повторения.