Python/NumPy 第一次出现子数组

Question

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

例如，我有

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

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

非常感谢！

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

原文由 CuriousMind 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

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

这是 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_indices = numpy.all(rolling_window(a, 3) == [8, 4, 0], axis=1)
>>> numpy.mgrid[0:len(bool_indices)][bool_indices]
array([3])

对于列表，您可以调整这些 滚动窗口 迭代器之一以使用类似的方法。

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

 >>> 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]),)

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

原文由 senderle 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

以下代码应该有效：

 [x for x in xrange(len(a)) if a[x:x+len(b)] == b]

返回模式开始的索引。

原文由 danem 发布，翻译遵循 CC BY-SA 4.0 许可协议