Вот один с broadcasting
и masking
для получения верхние треугольные, а затем возведенные в квадрат только для повышения эффективности работы -
def pairwise_squared_diff(x1, x2):
x1 = np.asarray(x1)
x2 = np.asarray(x2)
diffs = x1[:,None] - x2
mask = np.arange(len(x1))[:,None] <= np.arange(len(x2))
return (diffs[mask])**2
Пробный запуск -
In [85]: x1
Out[85]: array([1, 3, 5, 6, 8])
In [86]: x2
Out[86]: array([ 3, 6, 7, 9, 12])
In [87]: pairwise_squared_diff(x1, x2)
Out[87]:
array([ 4, 25, 36, 64, 121, 9, 16, 36, 81, 4, 16, 49, 9,
36, 16])
Возможные улучшения
Улучшение №1:
Мы также могли бы использовать np.tri
для генерации mask
-
mask = ~np.tri(len(x1),len(x2),dtype=bool,k=-1)
Улучшение №2:
Если у нас все в порядке с выходом 2D
с нижними треугольными, установленными как 0s
, то простое поэлементное умножение с mask
также решает это, чтобы получить окончательный результат -
(diffs*mask)**2
Это будет хорошо работать с модулем numexpr
< /a> для больших данных и повышения эффективности использования памяти и, следовательно, производительности.
Улучшение №3:
Мы также могли бы вычислить различия с помощью numexpr
и, следовательно, вычислить замаскированный вывод с помощью того же метода evaulate
, чтобы получить совершенно новое решение:
def pairwise_squared_diff_numexpr(x1, x2):
x1 = np.asarray(x1)
x2 = np.asarray(x2)
mask = ~np.tri(len(x1),len(x2),dtype=bool,k=-1)
return ne.evaluate('mask*((x1D-x2)**2)',{'x1D':x1[:,None]})
Время с улучшениями
Давайте изучим эти предложения по производительности для больших массивов —
Настраивать :
In [136]: x1 = np.random.randint(0,9,(1000))
In [137]: x2 = np.random.randint(0,9,(1000))
С улучшением №1:
In [138]: %timeit np.arange(len(x1))[:,None] <= np.arange(len(x2))
1000 loops, best of 3: 772 µs per loop
In [139]: %timeit ~np.tri(len(x1),len(x2),dtype=bool,k=-1)
1000 loops, best of 3: 243 µs per loop
С улучшением №2:
In [140]: import numexpr as ne
In [141]: diffs = x1[:,None] - x2
...: mask = np.arange(len(x1))[:,None] <= np.arange(len(x2))
In [142]: %timeit (diffs[mask])**2
1000 loops, best of 3: 1.46 ms per loop
In [143]: %timeit ne.evaluate('(diffs*mask)**2')
1000 loops, best of 3: 1.05 ms per loop
С Улучшением № 3 для полных решений:
In [170]: %timeit pairwise_squared_diff(x1, x2)
100 loops, best of 3: 3.66 ms per loop
In [171]: %timeit pairwise_squared_diff_numexpr(x1, x2)
1000 loops, best of 3: 1.54 ms per loop
Loopy один
Для полноты картины, вот зацикленный, который использует slicing
, чтобы работать лучше, чем чистый broadcasting
, из-за эффективности памяти:
def pairwise_squared_diff_loopy(x1,x2):
n = len(x2)
idx = np.concatenate(( [0], np.arange(n,0,-1).cumsum() ))
start, stop = idx[:-1], idx[1:]
L = n*(n+1)//2
out = np.empty(L,dtype=np.result_type(x1,x2))
for i,(s0,s1) in enumerate(zip(start,stop)):
out[s0:s1] = x1[i] - x2[i:]
return out**2
Тайминги -
In [300]: x1 = np.random.randint(0,9,(1000))
...: x2 = np.random.randint(0,9,(1000))
In [301]: %timeit pairwise_squared_diff(x1, x2)
100 loops, best of 3: 3.44 ms per loop
In [302]: %timeit pairwise_squared_diff_loopy(x1, x2)
100 loops, best of 3: 2.73 ms per loop
person
Divakar
schedule
24.10.2018