python - 有效地在 Python 列表中查找索引(与 MATLAB 相比)

Question

我很难找到在 Python 列表中查找索引的有效解决方案。到目前为止，我测试过的所有解决方案都比 MATLAB 中的“查找”功能慢。我才刚刚开始使用 Python(因此，我不是很有经验)。

在 MATLAB 中，我会使用以下内容:

a = linspace(0, 1000, 1000); % monotonically increasing vector
b = 1000 * rand(1, 100); % 100 points I want to find in a
for i = 1 : numel(b)
    indices(i) = find(b(i) <= a, 1); % find the first index where b(i) <= a
end

如果我使用 MATLAB 的 arrayfun()，我可以稍微加快这个过程。在 Python 中，我尝试了几种可能性。我用过

for i in xrange(0, len(b)):
   tmp = numpy.where(b[i] <= a)
   indices.append(tmp[0][0])

这会花费很多时间，尤其是在 a 很大的情况下。如果 b 排序比我可以使用

for i in xrange(0, len(b)):
    if(b[curr_idx] <= a[i]):
        indices.append(i)
        curr_idx += 1
    if(curr_idx >= len(b)):
        return indices
        break

这比 numpy.where() 解决方案快得多，因为我只需搜索一次列表，但这仍然比 MATLAB 解决方案慢。

谁能提出更好/更有效的解决方案？提前致谢。

Answer 1

试试 numpy.searchsorted:

>> a = np.array([0, 1, 2, 3, 4, 5, 6, 7])
>> b = np.array([1, 2, 4, 3, 1, 0, 2, 9])
% sorting b "into" a
>> np.searchsorted(a, b, side='right')-1
array([1, 2, 4, 3, 1, 0, 2, 9])

您可能需要对 b 中超出 a 范围的值进行一些特殊处理，例如上例中的 9。尽管如此，这应该比任何基于循环的方法都要快。

顺便说一句:同样，MATLAB 中的histc 会比循环快很多。

编辑:

如果您想要获取 b 最接近 a 的索引，您应该能够使用相同的代码，只需修改 a:

>> a_mod = 0.5*(a[:-1] + a[1:]) % take the centers between the elements in a
>> np.searchsorted(a_mod, np.array([0.9, 2.1, 4.2, 2.9, 1.1]), side='right')
array([1, 2, 4, 3, 1])

请注意，您可以删除 -1，因为 a_mod 的元素比 a 少一个。