Предложения о том, как ускорить расчет расстояния

Question

Рассмотрим следующий класс:

class SquareErrorDistance(object):
    def __init__(self, dataSample):
        variance = var(list(dataSample))
        if variance == 0:
            self._norm = 1.0
        else:
            self._norm = 1.0 / (2 * variance)

    def __call__(self, u, v): # u and v are floats
        return (u - v) ** 2 * self._norm

Я использую его для расчета расстояния между двумя элементами вектора. Я в основном создаю один экземпляр этого класса для каждого измерения вектора, который использует это измерение расстояния (есть размеры, которые используют другие меры расстояния). Профилирование показывает, что __call__ Функция этого класса составляет 90% от времени работы моего вновья в KNN-реализации (кто бы подумал). Я не думаю, что есть какой-либо пункт Pure-Python, чтобы ускорить это, но, может быть, если я реализую его в C?

Если я запускаю простую C программу C, которая только что рассчитывает расстояния для случайных значений с использованием формулы выше, это порядки быстрее, чем Python. Так что я пытался использовать Ctypes. И вызовите функцию C, которая выполняет вычисление, но, по-видимому, преобразование параметров и значения возврата далеко до дорогих, потому что полученный код намного медленнее.

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

Так каковы мои альтернативы? Записываю C-функцию с помощью Python C-API избавиться от накладных расходов? Есть ли другие способы ускорить этот расчет?

Answer 1

Следующий код Cython (я понимаю первую строку __init__ другой, я заменил его случайным материалом, потому что я не знаю var и потому что это все равно не имеет значения - вы заявили __call__ это узкое место):

cdef class SquareErrorDistance:
    cdef double _norm

    def __init__(self, dataSample):
        variance = round(sum(dataSample)/len(dataSample))
        if variance == 0:
            self._norm = 1.0
        else:
            self._norm = 1.0 / (2 * variance)

    def __call__(self, double u, double v): # u and v are floats
        return (u - v) ** 2 * self._norm

Скомпилирован через простой Setup.py (просто Пример от документов С именем файла изменено), он выполняет почти в 20 раз лучше, чем эквивалентный чистый Python в простой оформлении timeit ориентир. Обратите внимание, что только изменилось cdefS для _norm поле и то __call__ Параметры. Я считаю эту довольно впечатляю.

Answer 2

Это, вероятно, не так много поможет, но вы можете переписать его, используя вложенные функции:

def SquareErrorDistance(dataSample):
    variance = var(list(dataSample))
    if variance == 0:
        def f(u, v):
            x = u - v
            return x * x
    else:
        norm = 1.0 / (2 * variance)
        def f(u, v):
            x = u - v
            return x * x * norm
    return f