在屏蔽数组中形成项目索引，计算原始排序数组中相同项目的索引

Question

我使用下面的方法屏蔽了排序的一维 numpy 数组（遵循此处提出的解决方案）：def get_from_sorted(sorted,idx):     mask = np.zeros(sorted.shape, bool)     mask[idx] = True     return sorted[mask]python 方法在对索引进行屏蔽后返回数组idx。例如，如果 Sorted=np.array([0.1,0.2,0.3.0.4,0.5])和 idx= np.array([4,0,1]），则该方法get_from_sorted应该返回np.array([0.1,0.2,0.5])（注意原始数组中的顺序被保留。）问题：我需要获取屏蔽后数组中项目的索引与原始列表中项目的索引之间的映射。在上面的例子中，这样的映射是0 -> 01 -> 12 -> 5因为 0.1、0.2 和 0.5 分别位于 中的第 0 位、第 1 位和第 5 位sorted。如何有效地对该映射进行编程？对效率的要求：效率是我解决问题的关键。这里，“idx”和“sorted”都是一个包含 100 万个元素的一维数组，idx 是一个包含约 50 万个元素的一维数组（取自图像处理应用程序）。因此，针对原始数组逐一或以矢量化方式检查屏蔽数组的元素（例如使用 np.where）在我的情况下表现不佳。理想情况下，屏蔽数组和原始排序数组中的索引之间应该存在相对简单的数学关系。任何想法？

Answer 1

有一个问题我不清楚。它可以有多种解释。

mask -> idx（按升序排列）：

让我尝试一下这个相当大的数据集（10M 的值，其中 10% 是True）：

x = np.random.choice(a=[False, True], size=(10000000,), p=[0.9, 0.1])

在这种情况下，使用np.where是非常有效的：

%timeit np.where(x)[0]

%timeit x.nonzero()[0]

%timeit np.arange(len(x))[x]

24.8 ms ± 551 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

24.5 ms ± 229 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

52.4 ms ± 895 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

排序的随机项 -> idx （按升序）：

如果您丢失了对需要从中获取的项目位置的任何引用sorted，您仍然可以查找idx是否没有重复的项目。这是O(n logn)：

x = np.random.choice(a=[False, True], size=(10000000,), p=[0.9, 0.1])

arr = np.linspace(0,1,len(x))

sub_arr = arr[x] %input data: skipping 90% of items

%timeit np.searchsorted(arr, sub_arr) %output data

112 ms ± 2.2 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 

idx（任意顺序）-> idx（升序）

这很简单：

x = np.arange(10000000)

np.random.shuffle(x)

idx = x[:1000000] #input data: first 1M of random idx

%timeit np.sort(idx) #output data

65.3 ms ± 316 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Answer 2

如果您需要知道屏蔽条目的来源，可以使用np.where、np.nonzero或 之一np.flatnonzero。但是，如果您只需要获取索引子集的起源，则可以使用我最近作为库的一部分编写的函数 haggis: ¹。haggis.npy_util.unmasked_index

给定mask一些掩码元素的索引，您可以使用以下命令检索原始位置的多维索引

unmasked_index(idx, mask)

如果您需要它，还有一个反函数haggis.npy_util.masked_index，可以将多维输入数组中的位置转换为其在掩码数组中的索引。

Answer 3

我假设（根据您的示例）原始列表是排序列表。在这种情况下，除非我误解了，否则你只需这样做：

idx.sort()

然后映射是i-> idx[i]

当然，如果原始顺序idx很重要，请先复制一份。