如何在O（1）中获取numpy中的反向映射？

Question

我有一个numpy数组，其元素是唯一的，例如：

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的副本

像解释here一样使用in1d并不能解决我的问题。使用他们的例子：

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

我希望能够在运行时在O（1）中找到b中的10索引。

进行预处理移动

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

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

（可以使用np.arange(len(b))完成）

并没有真正帮助，因为当10作为输入时，使用此方法无法在O（1）时间内告诉其索引。

Answer 1

Solution

如果你想要恒定的时间（即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]

Caveat

在生产代码中，你应该使用字典来解决这个问题，正如其他的回答者所指出的那样。为什么？好吧，首先，说你的数组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的高级索引，它比你想象的要简单。

我们做的是制作我们的目标数组，并使用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.])

您可以使用nans或-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()有可能发生变化，我们必须重新创建字典。