优雅查找列表中的子列表

Question

给定一个包含噪声包围的已知模式的列表,是否有一种优雅的方式来获得与模式相同的所有项目.请参阅下面的原始代码.

list_with_noise = [7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5]
known_pattern = [1,2,3,4]
res = []


for i in list_with_noise:
    for j in known_pattern:
        if i == j:
            res.append(i)
            continue

print res

我们会得到的 2, 1, 2, 3, 4, 2, 1, 2, 3, 4, 1, 2, 3, 4, 4, 3

奖励:如果不存在完整模式,则避免附加i(即,允许1,2,3,4但不允许1,2,3)

例子:

find_sublists_in_list([7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5],[1,2,3,4])

[1,2,3,4],[1,2,3,4],[1,2,3,4]


find_sublists_in_list([7,2,1,2,3,2,1,2,3,6,9,9,1,2,3,4,7,4,3,1,2,6],[1,2,3,4])

[1,2,3],[1,2,3],[1,2,3]

列表包含命名元组.

Answer 1

我知道这个问题是5个月大并且已经"被接受"了,但谷歌搜索一个非常相似的问题带我到这个问题,所有的答案似乎有几个相当重要的问题,加上我很无聊,想试试我的手在一个SO答案,所以我只是打扰我发现的东西.

正如我所理解的那样,问题的第一部分非常简单:只需返回原始列表,其中所有元素都不会被"模式"过滤掉.按照这个想法,我想到的第一个代码使用了filter()函数:

def subfinder(mylist, pattern):
    return list(filter(lambda x: x in pattern, mylist))

我会说这个解决方案肯定比原始解决方案更简洁,但它没有任何更快,或者至少没有明显,我尝试避免lambda表达式,如果没有一个很好的理由使用它们.事实上,我能提出的最佳解决方案涉及一个简单的列表理解:

def subfinder(mylist, pattern):
    pattern = set(pattern)
    return [x for x in mylist if x in pattern]

这种解决方案比原版更优雅,速度更快:理解速度比原版快约120%,同时将模式投射到一组第一个颠簸中,在我的测试中高达320%.

现在获得奖金:我会直接进入它,我的解决方案如下:

def subfinder(mylist, pattern):
    matches = []
    for i in range(len(mylist)):
        if mylist[i] == pattern[0] and mylist[i:i+len(pattern)] == pattern:
            matches.append(pattern)
    return matches

这是Steven Rumbalski的"低效单线程"的变体,通过添加"mylist [i] == pattern [0]"检查并且由于python的短路评估,它明显快于原始声明和itertools版本(以及我所能提供的所有其他解决方案),它甚至支持重叠模式.你去吧

Answer 2

这将获得您问题的“奖金”部分：

pattern = [1, 2, 3, 4]
search_list = [7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5]
cursor = 0
found = []
for i in search_list:
    if i == pattern[cursor]:
        cursor += 1
        if cursor == len(pattern):
            found.append(pattern)
            cursor = 0
    else:
        cursor = 0

对于非奖金：

pattern = [1, 2, 3, 4]
search_list = [7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5]
cursor = 0
found = []
for i in search_list:
    if i != pattern[cursor]:
        if cursor > 0:
            found.append(pattern[:cursor])
        cursor = 0
    else:
        cursor += 1

最后，这个处理重叠：

def find_matches(pattern_list, search_list):
    cursor_list = []
    found = []
    for element in search_list:
        cursors_to_kill = []
        for cursor_index in range(len(cursor_list)):
            if element == pattern_list[cursor_list[cursor_index]]:
                cursor_list[cursor_index] += 1
                if cursor_list[cursor_index] == len(pattern_list):
                    found.append(pattern_list)
                    cursors_to_kill.append(cursor_index)
            else:
                cursors_to_kill.append(cursor_index)
        cursors_to_kill.reverse()
        for cursor_index in cursors_to_kill:
            cursor_list.pop(cursor_index)
        if element == pattern_list[0]:
            cursor_list.append(1)
    return found