Как получить обратное отображение в numpy в O (1)?

Question

У меня есть пустой массив, элементы которого уникальны, например:

b = np.array([5, 4, 6, 8, 1, 2])

(Edit2: b может иметь большие числа и числа с плавающей запятой. Приведенный выше пример приведен для простоты)

Я получаю числа, которые являются элементами в b.

Я хочу найти их индекс в b, что означает Я хочу обратное отображение от значения к индексу в b.

Я мог бы сделать

for number in input:
    ind = np.where(number==b)

, который будет перебирать весь массив при каждом вызове where.

Я также мог бы создать словарь,

d = {}
for i, element in enumerate(list(b)):
    d[element] = i

Я мог бы создать этот словарь во время "предварительной обработки", но все равно я остался бы со странно выглядящим словарем, в основном с пустым кодом, который кажется (мне) не таким, каким подразумевается использование numpy.

Как я могу сделать это обратное отображение в numpy?

использование (O (1) время и память требуется):

print("index of 8 is: ", foo(b, 8))

---

• Edit1: не дубликат this

Использование in1d, как объяснено здесь не решает мою проблему. Используя их пример:

b = np.array([1, 2, 3, 10, 4])

Я хочу иметь возможность, например, найти индекс 10 в b, во время выполнения, в O (1).

Выполнение хода предварительной обработки

mapping = np.in1d(b, b).nonzero()[0]

>> [0, 1, 2, 3, 4]

(что можно сделать с помощью np.arange(len(b)))

на самом деле не помогает, потому что, когда 10 входит в качестве ввода, с помощью этого метода невозможно определить его индекс за O (1) времени.

Answer 1

Решение

Если вам нужно постоянное время (т. Е. O(1)), вам нужно предварительно вычислить таблицу поиска. Если вы хотите, чтобы ваша таблица поиска использовала другой массив Numpy, это, по сути, должен быть разреженный массив, в котором большинство значений «пусто». Вот работоспособный подход, при котором пустые значения помечаются как -1:

b = np.array([5, 4, 6, 8, 1, 2])

_b_ix = np.array([-1]*(b.max() + 1))
_b_ix[b] = np.arange(b.size)
# _b_ix: array([-1,  4,  5, -1,  1,  0,  2, -1,  3])

def foo(*val):
    return _b_ix[list(val)]

Тест:

print("index of 8 is: %s" % foo(8))
print("index of 0,5,1,8 is: %s" % foo(0,5,1,8))

Выход:

index of 8 is: [3]
index of 0,5,1,8 is: [-1  0  4  3]

Протест

В рабочем коде вам определенно следует использовать словарь для решения этой проблемы, как указывали другие авторы. Зачем? Ну, во-первых, скажем, что ваш массив b содержит float значений или любое не int значение. Тогда справочная таблица на основе Numpy не будет работать вообще.

Таким образом, вы должны использовать приведенный выше ответ, только если у вас есть глубоко укоренившееся философское несогласие с использованием словаря (например, dict набежал на вашу домашнюю кошку). Вот хороший способ для генерации запроса обратного просмотра:

ix = {k:v for v,k in enumerate(b.flat)}

Answer 2

Вы можете использовать dict, zip и numpy.arrange для создания обратного поиска:

import numpy 

b = np.array([5, 4, 6, 8, 1, 2])
d = dict(zip(b, np.arange(0,len(b))))
print(d)

дает:

{5: 0, 4: 1, 6: 2, 8: 3, 1: 4, 2: 5}

Answer 3

Это проще, чем вы думаете, используя расширенную индексацию numpy.

Что мы делаем, так это создаем наш целевой массив и просто назначаем в качестве индекса usign b. Мы назначим нужные индексы с помощью arange.

>>> t = np.zeros((np.max(b) + 1,))
>>> t[b] = np.arange(0, b.size)
>>> t
array([0., 4., 5., 0., 1., 0., 2., 0., 3.])

Вы можете использовать nan s или -1 вместо нулей для построения цели, чтобы помочь обнаружить недопустимые поиски.

Использование памяти : это оптимально работает как в пространстве, так и во времени, поскольку полностью обрабатывается Numpy.

Если вы можете терпеть столкновения, вы можете реализовать хеш-таблицу бедного человека. Предположим, у нас есть валюты, например:

h = np.int32(b * 100.0) % 101  # Typically some prime number
t = np.zeros((101,))
t[h] = np.arange(0, h.size)

# Retrieving a value v; keep in mind v can be an ndarray itself.
t[np.int32(v * 100.0) % 101]

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

Это примерно предел того, что полезно делать с numpy.

Answer 4

Если вы хотите выполнить несколько поисков, вы можете сделать это в O(1) после начального O(n) обхода, чтобы создать словарь поиска.

b = np.array([5, 4, 6, 8, 1, 2])
lookup_dict = {e:i for i,e in enumerate(b)}
def foo(element):
    return lookup_dict[element]

И это работает для вашего теста:

>>> print('index of 8 is:', foo(8))
index of 8 is:  3

---

Обратите внимание, что если существует вероятность того, что b мог измениться после последнего вызова foo(), мы должны заново создать словарь.