Python: вычисление всех пар scipy / numpy между двумя одномерными векторами - PullRequest
Новая
       56

Python: вычисление всех пар scipy / numpy между двумя одномерными векторами

1 голос
/ 25 сентября 2019

У меня есть два списка l1 и l2, содержащие целые числа, которые могут иметь разную длину, и я хочу выполнить вычисление между всеми возможными парами между этими двумя векторами.

В частности, я проверяю расстояние Хэмминга между каждой парой и, если расстояние достаточно мало, я хочу его «посчитать».

Наивно, это можно реализовать 

def hamming_distance(n1: int, n2: int) -> float:
    return bin(n1 ^ n2).count('1')/32.0

matches = 0

for n1 in l1:
    for n2 in l2:
        sim = 1 - hamming_distance(n1, n2)

        if sim >= threshold:
            matches += 1

Но это не очень быстро.

Я безуспешно пытался использовать scipy.spatial.distance.cdist, где я решил, что сначала вычислю расстояние Хемминга между всеми парами, так как документация scipy.spatial.cdist заявляет , что это будет

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

и затем подсчитать количество элементов, удовлетворяющих предикату, что 1 - d >= threshold, где d - этоРасстояние Хэмминга, т.е. 

from scipy.spatial.distance import cdist

l1 = l1.reshape(-1, 2)  # After np.array
l2 = l2.reshape(-1, 2)
r = cdist(l1, l2, 'hamming')
matches = np.count_nonzero(1 - r >= threshold)

, но количество совпадений, найденных соответствующими решениями, различается.Я заметил, что можно вызывать cdist с функцией cdist(XA, XB, f), но мне не удалось написать мою реализацию hamming_distance, чтобы она правильно вещала.

Я смотрел на этот вопрос / ответ , но он предполагает, что оба списка имеют одинаковую длину, что здесь не так.

Ответы [ 2 ]

1 голос
/ 25 сентября 2019

Вот три подхода, использующих

  1. scipy.spatial.KDTree
  2. scipy.spatial.distance.cdist
  3. справочную таблицу

На пареиз 32-битных векторов длиной 100 и 200 все они дают одинаковый результат;по скорости они сравниваются следующим образом: 

count_sim_kd 16.408800622448325 ms
count_sim_cd 12.41896384395659 ms
count_sim_lu 0.8755046688020229 ms

Таким образом, при этой задаче размер поиска выигрывает с огромным запасом.

Код: 

import numpy as np
from scipy.spatial import cKDTree as KDTree
from scipy.spatial.distance import cdist

l1 = np.random.randint(0,2**32,100)
l2 = np.random.randint(0,2**32,200)
threshold = 10/32

def hamming_distance(n1: int, n2: int) -> float:
    return bin(n1 ^ n2).count('1')/32.0

matches = 0

for n1 in l1:
    for n2 in l2:
        sim = 1 - hamming_distance(n1, n2)

        if sim >= threshold:
            matches += 1

def count_sim_kd(a,b,th):
    A,B = (KDTree(np.unpackbits(x[:,None].view(np.uint8),axis=1))
           for x in (a,b))
    return A.sparse_distance_matrix(B,max_distance=32-int(32*th),p=1).nnz

def count_sim_cd(a,b,th):
    A,B = (np.unpackbits(x[:,None].view(np.uint8),axis=1) for x in (a,b))
    return np.count_nonzero(cdist(A,B,"minkowski",p=1)<=32-int(32*th))


lu = sum(np.unravel_index(np.arange(256),8*(2,)))
def count_sim_lu(a,b,th):
    return np.count_nonzero(lu[(a[:,None,None]^b[None,:,None])
                               .view(np.uint8)].sum(2)<=32-int(32*th))

from timeit import timeit
for f in (count_sim_kd,count_sim_cd,count_sim_lu):
    assert f(l1,l2,threshold)==matches
    print(f.__name__,timeit(lambda:f(l1,l2,threshold),number=100)*10,'ms')
1 голос
/ 25 сентября 2019

Вы можете использовать np.bitwise_xor.outer вместе с np.binary_repr и np.char.count: 

import numpy as np

a = np.random.randint(0, 10, size=5)
b = np.random.randint(0, 10, size=5)

binary_repr = np.vectorize(np.binary_repr)
distance = np.char.count(binary_repr(np.bitwise_xor.outer(a, b)), '1') / 32

Затем, чтобы получить совпадения: 

matches = np.sum(distance >= threshold)
...