考虑我有以下列表:
l = [5,6,7,8,9,10,5,15,20]
m = [10,5]
我想获取列表 l 中元素 m 的索引。我使用了列表推导式实现：
[(i,i+1) for i,j in enumerate(l) if m[0] == l[i] and m[1] == l[i+1]]
输出：[(5,6)]
但如果m中有更多的数字，我觉得这不是正确的方法。那么在Python或NumPy中是否有任何简单的方法？
另一个例子：
l = [5,6,7,8,9,10,5,15,20,50,16,18]
m = [10,5,15,20]
输出应该是：
[(5,6,7,8)]
最简单的方法（使用纯Python）是遍历项目并首先仅检查第一个项目是否匹配。这样可以避免不必要的子列表比较。根据您的 l 的内容，这种方法甚至可能优于NumPy广播解决方案：
def func(haystack, needle): # obviously needs a better name ...
if not needle:
return
# just optimization
lengthneedle = len(needle)
firstneedle = needle[0]
for idx, item in enumerate(haystack):
if item == firstneedle:
if haystack[idx:idx+lengthneedle] == needle:
yield tuple(range(idx, idx+lengthneedle))
>>> list(func(l, m))
[(5, 6, 7, 8)]
如果您对速度感兴趣，我检查了这些方法的性能（从我的设置中借鉴此处）：
import random
import numpy as np
# strided_app is from https://dev59.com/7FkS5IYBdhLWcg3wSk3b#40085052/
def strided_app(a, L, S ): # Window len = L, Stride len/stepsize = S
nrows = ((a.size-L)//S)+1
n = a.strides[0]
return np.lib.stride_tricks.as_strided(a, shape=(nrows,L), strides=(S*n,n))
def pattern_index_broadcasting(all_data, search_data):
n = len(search_data)
all_data = np.asarray(all_data)
all_data_2D = strided_app(np.asarray(all_data), n, S=1)
return np.flatnonzero((all_data_2D == search_data).all(1))
# view1D is from https://dev59.com/tqPia4cB1Zd3GeqP3cEw#45313353/
def view1D(a, b): # a, b are arrays
a = np.ascontiguousarray(a)
void_dt = np.dtype((np.void, a.dtype.itemsize * a.shape[1]))
return a.view(void_dt).ravel(), b.view(void_dt).ravel()
def pattern_index_view1D(all_data, search_data):
a = strided_app(np.asarray(all_data), L=len(search_data), S=1)
a0v, b0v = view1D(np.asarray(a), np.asarray(search_data))
return np.flatnonzero(np.in1d(a0v, b0v))
def find_sublist_indices(haystack, needle):
if not needle:
return
# just optimization
lengthneedle = len(needle)
firstneedle = needle[0]
restneedle = needle[1:]
for idx, item in enumerate(haystack):
if item == firstneedle:
if haystack[idx+1:idx+lengthneedle] == restneedle:
yield tuple(range(idx, idx+lengthneedle))
def Divakar1(l, m):
return np.squeeze(pattern_index_broadcasting(l, m)[:,None] + np.arange(len(m)))
def Divakar2(l, m):
return np.squeeze(pattern_index_view1D(l, m)[:,None] + np.arange(len(m)))
def MSeifert(l, m):
return list(find_sublist_indices(l, m))
# Timing setup
timings = {Divakar1: [], Divakar2: [], MSeifert: []}
sizes = [2**i for i in range(5, 20, 2)]
# Timing
for size in sizes:
l = [random.randint(0, 50) for _ in range(size)]
m = [random.randint(0, 50) for _ in range(10)]
larr = np.asarray(l)
marr = np.asarray(m)
for func in timings:
# first timings:
# res = %timeit -o func(l, m)
# second timings:
if func is MSeifert:
res = %timeit -o func(l, m)
else:
res = %timeit -o func(larr, marr)
timings[func].append(res)
%matplotlib notebook
import matplotlib.pyplot as plt
import numpy as np
fig = plt.figure(1)
ax = plt.subplot(111)
for func in timings:
ax.plot(sizes,
[time.best for time in timings[func]],
label=str(func.__name__))
ax.set_xscale('log')
ax.set_yscale('log')
ax.set_xlabel('size')
ax.set_ylabel('time [seconds]')
ax.grid(which='both')
ax.legend()
plt.tight_layout()
l 和 m 是列表，我的函数在所有尺寸下都比 NumPy 的解决方案表现更好：
list(find_sublist_indices(a, b))，只是为了确保我们做的是同一件事情。 - Divakartolist 比 list 快得多（在大多数情况下是2-5倍）。如果您通常对所有函数进行 numpy 数组基准测试，我稍后会更新答案。 :) - MSeifert您基本上是在寻找另一个列表中的列表的起始索引。
方法 #1： 解决此问题的一种方法是创建滑动窗口，其中包含我们要搜索的列表中的元素，从而给我们一个 2D 数组，然后只需使用 NumPy 广播 对先前获得的 2D 滑动窗口版本的每一行与搜索列表进行广播比较即可。 因此，一种方法是 -
# strided_app is from https://dev59.com/7FkS5IYBdhLWcg3wSk3b#40085052/
def strided_app(a, L, S ): # Window len = L, Stride len/stepsize = S
nrows = ((a.size-L)//S)+1
n = a.strides[0]
return np.lib.stride_tricks.as_strided(a, shape=(nrows,L), strides=(S*n,n))
def pattern_index_broadcasting(all_data, search_data):
n = len(search_data)
all_data = np.asarray(all_data)
all_data_2D = strided_app(np.asarray(all_data), n, S=1)
return np.flatnonzero((all_data_2D == search_data).all(1))
out = np.squeeze(pattern_index_broadcasting(l, m)[:,None] + np.arange(len(m)))
示例运行 -
In [340]: l = [5,6,7,8,9,10,5,15,20,50,16,18]
...: m = [10,5,15,20]
...:
In [341]: np.squeeze(pattern_index_broadcasting(l, m)[:,None] + np.arange(len(m)))
Out[341]: array([5, 6, 7, 8])
In [342]: l = [5,6,7,8,9,10,5,15,20,50,16,18,10,5,15,20]
...: m = [10,5,15,20]
...:
In [343]: np.squeeze(pattern_index_broadcasting(l, m)[:,None] + np.arange(len(m)))
Out[343]:
array([[ 5, 6, 7, 8],
[12, 13, 14, 15]])
方法二: 另一种方法是获取滑动窗口，然后将数据按行标量视图分成要搜索的数据和要搜索的数据，从而给我们提供 1D 数据来处理，如下所示 -
# view1D is from https://dev59.com/tqPia4cB1Zd3GeqP3cEw#45313353/
def view1D(a, b): # a, b are arrays
a = np.ascontiguousarray(a)
void_dt = np.dtype((np.void, a.dtype.itemsize * a.shape[1]))
return a.view(void_dt).ravel(), b.view(void_dt).ravel()
def pattern_index_view1D(all_data, search_data):
a = strided_app(np.asarray(all_data), L=len(search_data), S=1)
a0v, b0v = view1D(np.asarray(a), np.asarray(search_data))
return np.flatnonzero(np.in1d(a0v, b0v))
out = np.squeeze(pattern_index_view1D(l, m)[:,None] + np.arange(len(m)))
为了寻求更简单/紧凑的方法，我们可以查看scikit-image的view_as_windows，以获取带有内置的滑动窗口。我假设数组作为输入以获取更清晰的代码。对于列表作为输入，我们必须使用np.asarray()，如前所示。
方法 # 3：基本上是将pattern_index_broadcasting与view_as_windows导出为一个包含 a 作为较大数据和b 作为要搜索的数组的一行代码-
from skimage.util import view_as_windows
np.flatnonzero((view_as_windows(a,len(b))==b).all(1))[:,None]+np.arange(len(b))
方案 #4 : 对于从b到a的少量匹配，我们可以优化，通过查找b的第一个元素匹配来减少搜索的数据集大小 -
mask = a[:-len(b)+1]==b[0]
mask[mask] = (view_as_windows(a,len(b))[mask]).all(1)
out = np.flatnonzero(mask)[:,None]+np.arange(len(b))
方法#5: 对于小型的b，我们可以简单地为b中的每个元素运行一个循环，并执行按位与-规约操作 -
mask = np.bitwise_and.reduce([a[i:len(a)-len(b)+1+i]==b[i] for i in range(len(b))])
out = np.flatnonzero(mask)[:,None]+np.arange(len(b))
np.argmax 替换为 np.flatnonzero。让我来编辑。 - Divakar只是想说明，当然也可以在 numpy 中实现 @MSeifert 的方法：
def pp(h,n):
nn = len(n)
NN = len(h)
c = (h[:NN-nn+1]==n[0]).nonzero()[0]
if c.size==0: return
for i,l in enumerate(n[1:].tolist(),1):
c = c[h[i:][c]==l]
if c.size==0: return
return np.arange(c[0],c[0]+nn)
def get_data(l1,l2):
d=defaultdict(list)
[d[item].append(index) for index,item in enumerate(l1)]
print(d)
使用 defaultdict 存储其他列表元素的索引。
5。 - Jon Clements