Предложения по ускорению расчета расстояния - PullRequest
Новая
       6

Предложения по ускорению расчета расстояния

6 голосов
/ 21 ноября 2010

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

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-реализации (кто бы мог подумать).Я не думаю, что есть какой-либо чистый Python способ ускорить это, но, может быть, если я реализую это в C?

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

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

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

Ответы [ 2 ]

2 голосов
/ 21 ноября 2010

Следующий код 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.Обратите внимание, что были изменены только cdef s для поля _norm и параметров __call__.Я считаю это довольно впечатляющим.

0 голосов
/ 21 ноября 2010

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

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
...