Самая быстрая попарная метрика расстояния в питоне

У меня есть одномерный массив чисел, и я хочу вычислить все попарно евклидовы расстояния. У меня есть метод (благодаря SO) сделать это с вещанием, но он неэффективен, потому что он рассчитывает каждое расстояние дважды. И это плохо масштабируется.

Вот пример, который дает мне то, что я хочу с массивом из 1000 чисел.

import numpy as np
import random
r = np.array([random.randrange(1, 1000) for _ in range(0, 1000)])
dists = np.abs(r - r[:, None])

Какая самая быстрая реализация в scipy/numpy/scikit-learn, которую я могу использовать для этого, учитывая, что она должна масштабироваться до ситуаций, когда массив 1D имеет значения>10k.

Примечание: матрица симметрична, так что я предполагаю, что можно увеличить ее как минимум в 2 раза, просто не знаю как.

Источник

3 ответа

Решение

Ни один из других ответов полностью не ответил на вопрос - 1 был на Cython, один был медленнее. Но оба предоставили очень полезные советы. Вслед за ними предполагается, что scipy.spatial.distance.pdist это путь

Вот некоторый код:

import numpy as np
import random
import sklearn.metrics.pairwise
import scipy.spatial.distance

r = np.array([random.randrange(1, 1000) for _ in range(0, 1000)])
c = r[:, None]

def option1(r):
    dists = np.abs(r - r[:, None])

def option2(r):
    dists = scipy.spatial.distance.pdist(r, 'cityblock')

def option3(r):
    dists = sklearn.metrics.pairwise.manhattan_distances(r)

Сроки с IPython:

In [36]: timeit option1(r)
100 loops, best of 3: 5.31 ms per loop

In [37]: timeit option2(c)
1000 loops, best of 3: 1.84 ms per loop

In [38]: timeit option3(c)
100 loops, best of 3: 11.5 ms per loop

Я не пробовал реализацию Cython (я не могу использовать это для этого проекта), но сравнивая мои результаты с другим ответом, который сделал, похоже, scipy.spatial.distance.pdist примерно на треть медленнее, чем реализация Cython (с учетом разных машин путем сравнения с решением np.abs).

Источник

Использование половины памяти, но в 6 раз медленнее, чем np.abs(r - r[:, None]):

triu = np.triu_indices(r.shape[0],1)
dists2 = abs(r[triu[1]]-r[triu[0]])
Источник

Вот реализация Cython, которая дает более чем 3-кратное улучшение скорости для этого примера на моем компьютере. Это время должно быть пересмотрено для больших массивов, потому что подпрограммы BLAS, вероятно, могут масштабироваться намного лучше, чем этот довольно наивный код.

Я знаю, что вы спрашивали что-то внутри scipy / numpy / scikit-learn, но, возможно, это откроет вам новые возможности:

файл my_cython.pyx:

import numpy as np
cimport numpy as np
import cython

cdef extern from "math.h":
    double abs(double t)

@cython.wraparound(False)
@cython.boundscheck(False)
def pairwise_distance(np.ndarray[np.double_t, ndim=1] r):
    cdef int i, j, c, size
    cdef np.ndarray[np.double_t, ndim=1] ans
    size = sum(range(1, r.shape[0]+1))
    ans = np.empty(size, dtype=r.dtype)
    c = -1
    for i in range(r.shape[0]):
        for j in range(i, r.shape[0]):
            c += 1
            ans[c] = abs(r[i] - r[j])
    return ans

Ответ - одномерный массив, содержащий все неповторяющиеся оценки.

Чтобы импортировать в Python:

import numpy as np
import random

import pyximport; pyximport.install()
from my_cython import pairwise_distance

r = np.array([random.randrange(1, 1000) for _ in range(0, 1000)], dtype=float)

def solOP(r):
    return np.abs(r - r[:, None])

Сроки с IPython:

In [2]: timeit solOP(r)
100 loops, best of 3: 7.38 ms per loop

In [3]: timeit pairwise_distance(r)
1000 loops, best of 3: 1.77 ms per loop
Источник
Другие вопросы по тегам