Получите пересекающиеся строки в двух двумерных массивах

Question

Я хочу получить пересекающиеся (общие) строки в двух двумерных массивах.Например, если в качестве входных данных передаются следующие массивы:

array([[1, 4],
       [2, 5],
       [3, 6]])

array([[1, 4],
       [3, 6],
       [7, 8]])

, то результат должен быть:

array([[1, 4],
       [3, 6])

Я знаю, как это сделать с помощью циклов.Я смотрю на Pythonic / Numpy способ сделать это.

Answer 1

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

Другой способ - использовать numpy.intersect1d.Вам придется обмануть его, рассматривая строки как одно значение, хотя ... Это делает вещи менее читабельными ...

import numpy as np

A = np.array([[1,4],[2,5],[3,6]])
B = np.array([[1,4],[3,6],[7,8]])

nrows, ncols = A.shape
dtype={'names':['f{}'.format(i) for i in range(ncols)],
       'formats':ncols * [A.dtype]}

C = np.intersect1d(A.view(dtype), B.view(dtype))

# This last bit is optional if you're okay with "C" being a structured array...
C = C.view(A.dtype).reshape(-1, ncols)

Для больших массивов это должно быть значительно быстрее, чем при использованиинаборы.

Answer 2

Вы можете использовать наборы Python:

>>> import numpy as np
>>> A = np.array([[1,4],[2,5],[3,6]])
>>> B = np.array([[1,4],[3,6],[7,8]])
>>> aset = set([tuple(x) for x in A])
>>> bset = set([tuple(x) for x in B])
>>> np.array([x for x in aset & bset])
array([[1, 4],
       [3, 6]])

Как указывает Роб Коуи, это можно сделать более кратко, как

np.array([x for x in set(tuple(x) for x in A) & set(tuple(x) for x in B)])

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

Answer 3

Я не мог понять, почему нет предложенного чистого, тупого способа заставить это работать. Так что я нашел один, который использует передачу NumPy. Основная идея состоит в том, чтобы преобразовать один из массивов в 3d путем замены осей. Построим 2 массива:

a=np.random.randint(10, size=(5, 3))
b=np.zeros_like(a)
b[:4,:]=a[np.random.randint(a.shape[0], size=4), :]

С моим бегом это дало:

a=array([[5, 6, 3],
   [8, 1, 0],
   [2, 1, 4],
   [8, 0, 6],
   [6, 7, 6]])
b=array([[2, 1, 4],
   [2, 1, 4],
   [6, 7, 6],
   [5, 6, 3],
   [0, 0, 0]])

Шаги (массивы могут быть заменены):

#a is nxm and b is kxm
c = np.swapaxes(a[:,:,None],1,2)==b #transform a to nx1xm
# c has nxkxm dimensions due to comparison broadcast
# each nxixj slice holds comparison matrix between a[j,:] and b[i,:]
# Decrease dimension to nxk with product:
c = np.prod(c,axis=2)
#To get around duplicates://
# Calculate cumulative sum in k-th dimension
c= c*np.cumsum(c,axis=0)
# compare with 1, so that to get only one 'True' statement by row
c=c==1
#//
# sum in k-th dimension, so that a nx1 vector is produced
c=np.sum(c,axis=1).astype(bool)
# The intersection between a and b is a[c]
result=a[c]

В функции с 2 строками для сокращения используемой памяти (исправьте меня, если ошибаюсь):

def array_row_intersection(a,b):
   tmp=np.prod(np.swapaxes(a[:,:,None],1,2)==b,axis=2)
   return a[np.sum(np.cumsum(tmp,axis=0)*tmp==1,axis=1).astype(bool)]

который дал результат для моего примера:

result=array([[5, 6, 3],
       [2, 1, 4],
       [6, 7, 6]])

Это быстрее, чем заданные решения, так как в нем используются только простые операции с клочками, при этом он постоянно сокращает размеры и идеально подходит для двух больших матриц. Я думаю, что я мог ошибаться в своих комментариях, так как я получил ответ экспериментально и инстинктивно. Эквивалент пересечения столбцов можно найти, переставив массивы или немного изменив шаги. Также, если нужны дубликаты, то шаги внутри "//" должны быть пропущены. Функция может быть отредактирована так, чтобы она возвращала только логический массив индексов, который мне пригодился, при попытке получить разные индексы массивов с одним и тем же вектором. Контрольный показатель для проголосовавшего и моего ответа (количество элементов в каждом измерении играет роль в выборе того):

Код:

def voted_answer(A,B):
    nrows, ncols = A.shape
    dtype={'names':['f{}'.format(i) for i in range(ncols)],
           'formats':ncols * [A.dtype]}
    C = np.intersect1d(A.view(dtype), B.view(dtype))
    return C.view(A.dtype).reshape(-1, ncols)

a_small=np.random.randint(10, size=(10, 10))
b_small=np.zeros_like(a_small)
b_small=a_small[np.random.randint(a_small.shape[0],size=[a_small.shape[0]]),:]
a_big_row=np.random.randint(10, size=(10, 1000))
b_big_row=a_big_row[np.random.randint(a_big_row.shape[0],size=[a_big_row.shape[0]]),:]
a_big_col=np.random.randint(10, size=(1000, 10))
b_big_col=a_big_col[np.random.randint(a_big_col.shape[0],size=[a_big_col.shape[0]]),:]
a_big_all=np.random.randint(10, size=(100,100))
b_big_all=a_big_all[np.random.randint(a_big_all.shape[0],size=[a_big_all.shape[0]]),:]



print 'Small arrays:'
print '\t Voted answer:',timeit.timeit(lambda:voted_answer(a_small,b_small),number=100)/100
print '\t Proposed answer:',timeit.timeit(lambda:array_row_intersection(a_small,b_small),number=100)/100
print 'Big column arrays:'
print '\t Voted answer:',timeit.timeit(lambda:voted_answer(a_big_col,b_big_col),number=100)/100
print '\t Proposed answer:',timeit.timeit(lambda:array_row_intersection(a_big_col,b_big_col),number=100)/100
print 'Big row arrays:'
print '\t Voted answer:',timeit.timeit(lambda:voted_answer(a_big_row,b_big_row),number=100)/100
print '\t Proposed answer:',timeit.timeit(lambda:array_row_intersection(a_big_row,b_big_row),number=100)/100
print 'Big arrays:'
print '\t Voted answer:',timeit.timeit(lambda:voted_answer(a_big_all,b_big_all),number=100)/100
print '\t Proposed answer:',timeit.timeit(lambda:array_row_intersection(a_big_all,b_big_all),number=100)/100

с результатами:

Small arrays:
     Voted answer: 7.47108459473e-05
     Proposed answer: 2.47001647949e-05
Big column arrays:
     Voted answer: 0.00198730945587
     Proposed answer: 0.0560171294212
Big row arrays:
     Voted answer: 0.00500325918198
     Proposed answer: 0.000308241844177
Big arrays:
     Voted answer: 0.000864889621735
     Proposed answer: 0.00257176160812

Следующий вердикт заключается в том, что если вам нужно сравнить 2 больших 2d массива с 2d точками, используйте голосование с ответом. Если у вас есть большие матрицы во всех измерениях, голосование с ответом является наилучшим во всех отношениях. Таким образом, это зависит от того, что вы выбираете каждый раз.

Answer 4

Еще один способ добиться этого с помощью структурированного массива:

>>> a = np.array([[3, 1, 2], [5, 8, 9], [7, 4, 3]])
>>> b = np.array([[2, 3, 0], [3, 1, 2], [7, 4, 3]])
>>> av = a.view([('', a.dtype)] * a.shape[1]).ravel()
>>> bv = b.view([('', b.dtype)] * b.shape[1]).ravel()
>>> np.intersect1d(av, bv).view(a.dtype).reshape(-1, a.shape[1])
array([[3, 1, 2],
       [7, 4, 3]])

Просто для ясности, структурированный вид выглядит так:

>>> a.view([('', a.dtype)] * a.shape[1])
array([[(3, 1, 2)],
       [(5, 8, 9)],
       [(7, 4, 3)]],
       dtype=[('f0', '<i8'), ('f1', '<i8'), ('f2', '<i8')])

Answer 5

np.array(set(map(tuple, b)).difference(set(map(tuple, a))))

Это также может работать