Python/NumPy 第一次出现子数组

Question

在 Python 或 NumPy 中，找出第一次出现的子数组的最佳方法是什么？

例如，我有

a = [1, 2, 3, 4, 5, 6]
b = [2, 3, 4]

找出 b 在 a 中的位置的最快方法(运行时)是什么？我知道对于字符串来说这非常容易，但是对于列表或 numpy ndarray 呢？

非常感谢!

[已编辑] 我更喜欢 numpy 解决方案，因为根据我的经验，numpy 向量化比 Python 列表理解要快得多。同时，大数组很大，所以我不想将其转换为字符串；那将是(太)长。

Answer 1

我假设您正在寻找特定于 numpy 的解决方案，而不是简单的列表理解或 for 循环。一种直接的方法是使用 rolling window搜索适当大小的窗口的技术。

这种方法很简单，可以正常工作，并且比任何纯 Python 解决方案都快得多。对于许多用例来说应该足够了。然而，由于多种原因，这并不是最有效的方法。对于更复杂但在预期情况下渐近最优的方法，请参阅基于 numba 的 rolling hash norok2's answer 中的实现.

这是 rolling_window 函数:

>>> def rolling_window(a, size):
...     shape = a.shape[:-1] + (a.shape[-1] - size + 1, size)
...     strides = a.strides + (a. strides[-1],)
...     return numpy.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)
... 

然后你可以做类似的事情

>>> a = numpy.arange(10)
>>> numpy.random.shuffle(a)
>>> a
array([7, 3, 6, 8, 4, 0, 9, 2, 1, 5])
>>> rolling_window(a, 3) == [8, 4, 0]
array([[False, False, False],
       [False, False, False],
       [False, False, False],
       [ True,  True,  True],
       [False, False, False],
       [False, False, False],
       [False, False, False],
       [False, False, False]], dtype=bool)

要使其真正有用，您必须使用 all 沿轴 1 减少它:

>>> numpy.all(rolling_window(a, 3) == [8, 4, 0], axis=1)
array([False, False, False,  True, False, False, False, False], dtype=bool)

然后你可以使用它，但是你会使用一个 bool 数组。获取索引的简单方法:

>>> bool_indices = numpy.all(rolling_window(a, 3) == [8, 4, 0], axis=1)
>>> numpy.mgrid[0:len(bool_indices)][bool_indices]
array([3])

对于列表，您可以调整其中之一 rolling window迭代器使用类似的方法。

对于非常大的数组和子数组，你可以这样节省内存:

>>> windows = rolling_window(a, 3)
>>> sub = [8, 4, 0]
>>> hits = numpy.ones((len(a) - len(sub) + 1,), dtype=bool)
>>> for i, x in enumerate(sub):
...     hits &= numpy.in1d(windows[:,i], [x])
... 
>>> hits
array([False, False, False,  True, False, False, False, False], dtype=bool)
>>> hits.nonzero()
(array([3]),)

另一方面，这可能会慢一些。