Sugestões sobre como acelerar um cálculo de distância

Question

Considere a seguinte aula:

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

Eu o uso para calcular a distância entre dois elementos de um vetor. Eu basicamente crio uma instância dessa classe para cada dimensão do vetor que usa essa medida de distância (existem dimensões que usam outras medidas de distância). Perfil revela que o __call__ A função desta classe é responsável por 90% do tempo de execução da minha implementação de KNN (que teria pensado). Eu não acho que exista uma maneira pura-python de acelerar isso, mas talvez se eu implementar em C?

Se eu executar um programa C simples que apenas calcula distâncias para valores aleatórios usando a fórmula acima, ele é ordens de magnitude mais rápido que o Python. Então eu tentei usar ctypes e chame uma função C que faz o cálculo, mas aparentemente a conversão dos parâmetros e valores de retorno é muito caro, porque o código resultante é muito mais lento.

É claro que eu poderia implementar o KNN inteiro em C e apenas chamar isso, mas o problema é que, como descrevi, uso diferentes funções de distância para alguma dimensão dos vetores, e traduzi -los para C seria muito trabalho.

Então, quais são minhas alternativas? Escreverá a função C usando o Python c-api Livre -se da sobrecarga? Existem outras maneiras de acelerar esse cálculo?

Answer 1

O seguinte código do Cython (eu percebo a primeira linha de __init__ é diferente, eu o substituí por coisas aleatórias porque não sei var E porque não importa de qualquer maneira - você declarou __call__ é o gargalo):

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

Compilado por meio de um simples setup.py (apenas o exemplo dos documentos com o nome do arquivo alterado), ele tem um desempenho quase 20 vezes melhor do que o python puro equivalente em um simples contrato timeit referência. Observe que os únicos alterados foram cdefs para o _norm campo e o __call__ parâmetros. Eu considero isso bastante impressionante.

Answer 2

Isso provavelmente não ajudará muito, mas você pode reescrevê -lo usando funções aninhadas:

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