Найти общие элементы в подмассивах массивов - PullRequest
Новая
       8

Найти общие элементы в подмассивах массивов

0 голосов
/ 19 ноября 2018

У меня есть два массива с цифрами: arr1 = (~ 140000, 3) и arr2 = (~ 450000, 10). Первые 3 элемента каждой строки для обоих массивов являются координатами (z, y, x). Я хочу найти строки arr2, которые имеют одинаковые координаты arr1 (который можно считать подгруппой arr2).

например: 

arr1 = [[1,2,3],[1,2,5],[1,7,8],[5,6,7]]

arr2 = [[1,2,3,7,66,4,3,44,8,9],[1,3,9,6,7,8,3,4,5,2],[1,5,8,68,7,8,13,4,53,2],[5,6,7,6,67,8,63,4,5,20], ...]

Я хочу найти общие координаты (те же первые 3 элемента): 

list_arr = [[1,2,3,7,66,4,3,44,8,9], [5,6,7,6,67,8,63,4,5,20], ...]

В данный момент я делаю этот двойной цикл, который очень медленный: 

list_arr=[]
for i in arr1:
    for j in arr2:
        if i[0]==j[0] and i[1]==j[1] and i[2]==j[2]:
            list_arr.append (j)

Я также пытался создать (после 1-го цикла) подмассив arr2, отфильтровав его по значению i [0] (arr2_filt = [el для el в arr2, если el [0] == i [0]) , Эта скорость немного работает, но она все еще остается очень медленной.

Можете ли вы помочь мне с этим?

Ответы [ 3 ]

0 голосов
/ 19 ноября 2018

Подход # 1

Вот векторизованный с views - 

# https://stackoverflow.com/a/45313353/ @Divakar
def view1D(a, b): # a, b are arrays
    a = np.ascontiguousarray(a)
    b = np.ascontiguousarray(b)
    void_dt = np.dtype((np.void, a.dtype.itemsize * a.shape[1]))
    return a.view(void_dt).ravel(),  b.view(void_dt).ravel()

a,b = view1D(arr1,arr2[:,:3])
out = arr2[np.in1d(b,a)]

Подход # 2

Другой с dimensionality-reduction для целых - 

d = np.maximum(arr2[:,:3].max(0),arr1.max(0))
s = np.r_[1,d[:-1].cumprod()]
a,b = arr1.dot(s),arr2[:,:3].dot(s)
out = arr2[np.in1d(b,a)]

Улучшение # 1

Мы могли бы использовать np.searchsorted для замены np.in1d для обоих подходов, перечисленных ранее - 

unq_a = np.unique(a)
idx = np.searchsorted(unq_a,b)
idx[idx==len(a)] = 0
out = arr2[unq_a[idx] == b]

Улучшение # 2

Для последнего улучшения использования np.searchsorted, которое также использует np.unique, мы могли бы использовать argsort вместо - 

sidx = a.argsort()
idx = np.searchsorted(a,b,sorter=sidx)
idx[idx==len(a)] = 0
out = arr2[a[sidx[idx]]==b]
0 голосов
/ 19 ноября 2018

Для целых чисел Дивакар уже дал отличный ответ.Если вы хотите сравнить числа с плавающей запятой, вы должны рассмотреть, например, следующее: 

1.+1e-15==1.
False
1.+1e-16==1.
True

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

import numpy as np
from scipy import spatial
def get_indices_of_nearest_neighbours(arr1,arr2):
  tree=spatial.cKDTree(arr2[:,0:3])
  #You can check here if the distance is small enough and otherwise raise an error
  dist,ind=tree.query(arr1, k=1)
  return ind
0 голосов
/ 19 ноября 2018

Вы можете сделать это с помощью set

arr = np.array([[1,2,3],[4,5,6],[7,8,9]])
arr2 = np.array([[7,8,9,11,14,34],[23,12,11,10,12,13],[1,2,3,4,5,6]])

# create array from arr2 with only first 3 columns
temp = [i[:3] for i in arr2]

aset = set([tuple(x) for x in arr])
bset = set([tuple(x) for x in temp])
np.array([x for x in aset & bset])

Выход 

array([[7, 8, 9],
       [1, 2, 3]])

Редактировать

Использовать list comprehension

l = [list(i) for i in arr2 if i[:3] in arr]

print(l)

Вывод: 

[[7, 8, 9, 11, 14, 34], [1, 2, 3, 4, 5, 6]]
...