Как найти индексы переупорядоченного массива numpy?

Question

Скажем, у меня есть отсортированный Numpy массив:

arr = np.array([0.0, 0.0], 
       [0.5, 0.0], 
       [1.0, 0.0], 
       [0.0, 0.5], 
       [0.5, 0.5], 
       [1.0, 0.5], 
       [0.0, 1.0], 
       [0.5, 1.0], 
       [1.0, 1.0]) 

и предположим, что я сделать нетривиальное операцию на ней таким образом, что у меня есть новый массив, который является таким же, как и старый, но в другом порядке:

arr2 = np.array([0.5, 0.0], 
       [0.0, 0.0], 
       [0.0, 0.5], 
       [1.0, 0.0], 
       [0.5, 0.5], 
       [1.0, 0.5], 
       [0.0, 1.0], 
       [1.0, 1.0], 
       [0.5, 1.0]) 

Вопрос: как получить индексы, где каждый элемент arr2 размещен в arr. Другими словами, мне нужен метод, который принимает оба массива и возвращает массив той же длины, что и arr2, но с индексом элемента arr. Например, первым элементом возвращаемого массива будет индекс первого элемента arr2 в arr.

where_things_are(arr2, arr) 
return : array([1, 0, 3, 2, 4, 5, 6, 8, 7]) 

Есть ли такая функция, которая уже существует в numpy?

EDIT:

Я пробовал:

np.array([np.where((arr == x).all(axis=1)) for x in arr2]) 

который возвращает то, что я хочу, но все еще держит мой вопрос: есть ли более эффективный способ сделать это с помощью Numpy методы?

EDIT2:

Он также должен работать, если длина arr2 не такой же, как длина исходного массива (например, если я удалил некоторые элементы из него). Таким образом, он не находит и не инвертирует перестановку, а скорее находит, где находятся элементы.

Answer 1

Ключом является инвертирование перестановок. Код ниже работает, даже если исходный массив не отсортирован. Если он отсортирован, то можно использовать find_map_sorted, который, очевидно, быстрее.

UPDATE: адаптируя к постоянно меняющимся требованиям OP, я добавил ветку, которая обрабатывает потерянные элементы.

import numpy as np 

def invperm(p): 
    q = np.empty_like(p) 
    q[p] = np.arange(len(p)) 
    return q 

def find_map(arr1, arr2): 
    o1 = np.argsort(arr1) 
    o2 = np.argsort(arr2) 
    return o2[invperm(o1)] 

def find_map_2d(arr1, arr2): 
    o1 = np.lexsort(arr1.T) 
    o2 = np.lexsort(arr2.T) 
    return o2[invperm(o1)] 

def find_map_sorted(arr1, arrs=None): 
    if arrs is None: 
     o1 = np.lexsort(arr1.T) 
     return invperm(o1) 
    # make unique-able 
    rdtype = np.rec.fromrecords(arrs[:1, ::-1]).dtype 
    recstack = np.r_[arrs[:,::-1], arr1[:,::-1]].view(rdtype).view(np.recarray) 
    uniq, inverse = np.unique(recstack, return_inverse=True) 
    return inverse[len(arrs):] 

x1 = np.random.permutation(100000) 
x2 = np.random.permutation(100000) 
print(np.all(x2[find_map(x1, x2)] == x1)) 

rows = np.random.random((100000, 8)) 
r1 = rows[x1, :] 
r2 = rows[x2, :] 
print(np.all(r2[find_map_2d(r1, r2)] == r1)) 

rs = r1[np.lexsort(r1.T), :] 
print(np.all(rs[find_map_sorted(r2), :] == r2)) 

# lose ten elements 
print(np.all(rs[find_map_sorted(r2[:-10], rs), :] == r2[:-10])) 

Answer 2

Если вы гарантировать уникальность:

[ np.where(np.logical_and((arr2==x)[:,1], (arr2==x)[:,0])==True)[0][0] for x in arr] 

Обратите внимание, что, я преобразовал свой массив в 2D: например

arr2 = np.array([[0.5, 0.0], 
[0.0, 0.0], 
[0.0, 0.5], 
[1.0, 0.0], 
[0.5, 0.5], 
[1.0, 0.5], 
[0.0, 1.0], 
[1.0, 1.0], 
[0.5, 1.0]]) 

Answer 3

Вот способ использования NumPy Broadcasting:

In [10]: ind = np.where(arr[:, None] == arr2[None, :])[1] 

In [11]: ind[np.where(np.diff(ind)==0)] 
Out[11]: array([1, 0, 3, 2, 4, 5, 6, 8, 7]) 

Идея заключается в том, увеличивая размер массивов, так что их сравнение производит 3d массив, так как исходный суб-массив имеет длину 2, если бы у нас было два последовательных равных элемента на второй оси результата сравнения, они были бы там, где оба элемента равны. Для лучшей демонстрации здесь является результатом сравнения без выбора второй оси:

In [96]: np.where(arr[:, None] == arr2[None, :]) 
Out[96]: 
(array([0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 
     3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 
     7, 7, 8, 8, 8, 8, 8, 8]), 
array([0, 1, 1, 2, 3, 6, 0, 0, 1, 3, 4, 8, 0, 1, 3, 3, 5, 7, 1, 2, 2, 4, 5, 
     6, 0, 2, 4, 4, 5, 8, 2, 3, 4, 5, 5, 7, 1, 2, 6, 6, 7, 8, 0, 4, 6, 7, 
     8, 8, 3, 5, 6, 7, 7, 8]), 
array([1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 
     0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 
     0, 1, 0, 0, 1, 0, 1, 1])) 

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

Answer 4

Пакет numpy_indexed (отказ от ответственности: я его автор) содержит эффективную функциональность для такого типа проблем; npi.indices является ndarray-эквивалентом list.index.

import numpy_indexed as npi 
idx = npi.indices(arr, arr2) 

Это возвращает список таких индексов, что arr [idx] == arr2. Если arr2 содержит элементы, отсутствующие в arr, повышается значение ValueError; но вы можете контролировать это с помощью «недостающего» kwarg.

Чтобы ответить на ваш вопрос, включена ли эта функция в numpy; да, в том смысле, что numpy - это полная экосистема. Но на самом деле, если вы считаете количество строк кода, необходимых для его эффективного, правильного и общего характера.