优雅查找列表中的子列表 [英] elegant find sub-list in list

问题描述

给定一个包含被噪声包围的已知模式的列表，是否有一种优雅的方法来获取所有与模式相同的项目。见下面的粗制代码。

  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 = [] 
 
 
在list_with_noise中的i：
在known_pattern中的j：
如果i == j：
 res.append（i ）
继续
 
打印res 
  

我们会得到code> 2，1，2，3，4，2，1，2，3，4，1，2，3，4，4，3，3

奖励：如果完整模式不存在，请避免附加（即，允许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] 
  pre> 
 
 
列表包含命名元组。
解决方案例
我知道这个问题已经5个月了，已经被接受了，但是google上的一个非常类似的问题让我来了这个问题，所有的答案似乎都有一些很重要的问题，很无聊，想要在一个SO答案中试试我的手，所以我只是在我发现的东西上摇摆。
 
 
 
问题的第一部分，据我所知，这很简单：只要返回原始列表，所有元素都不会被过滤掉。接下来的想法，我以为使用filter（）函数的第一个代码：
  def subfinder（mylist，pattern）：
返回列表（filter（lambda x：x in pattern，mylist））
  
我会说这个解决方案绝对比原来的解决方案更简洁，但是它不会更快，或至少不太明显，如果没有很好的使用原因，我尽量避免使用lambda表达式。事实上，我可以想出的最好的解决方案是简单的列表理解：
  def subfinder（mylist，pattern）：
 pattern = set（pattern）
 return [x for m in mylist if x in pattern] 
  
这个解决方案比原来的更加优雅和明显快：理解速度比原来的要快大约120％，同时将模式设置成一个第一个颠覆，在我的测试中快达320％。 / p> 
 
 
现在的奖金：我会直接跳入它，我的解决方案如下：
  def subfinder（mylist，pattern）：
 matches = [] 
 for i in range（len（mylist））：
如果mylist [i] ==模式[0]和mylist [i：i + len（pattern）] == pattern：
 matches.append（pattern）
 return matches 
  
这是史蒂芬·朗巴尔斯基（Steven Rumbalski）的低效率班轮的一个变体，那就是添加了mylist ] == pattern [0]检查和感谢python的短路评估，明显快于原始语句和itertools版本（以及我可以告诉的所有其他提供的解决方案）和 
Given a list containing a known pattern surrounded by noise, is there an elegant way to get all items that equal the pattern. See below for my crude code.
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
we would get 2, 1, 2, 3, 4, 2, 1, 2, 3, 4, 1, 2, 3, 4, 4, 3


bonus: avoid appending i if the full pattern is not present (ie., allow 1,2,3,4 but not 1,2,3)

examples: 
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]
The lists contain named tuples.
解决方案
I know this question is 5 months old and already "accepted", but googling a very similar problem brought me to this question and all the answers seem to have a couple of rather significant problems, plus I'm bored and want to try my hand at a SO answer, so I'm just going to rattle off what I've found.

The first part of the question, as I understand it, is pretty trivial: just return the original list with all the elements not in the "pattern" filtered out. Following that thinking, the first code I thought of used the filter() function:
def subfinder(mylist, pattern):
    return list(filter(lambda x: x in pattern, mylist))
I would say that this solution is definitely more succinct than the original solution, but it's not any faster, or at least not appreciably, and I try to avoid lambda expressions if there's not a very good reason for using them. In fact, the best solution I could come up with involved a simple list comprehension:
def subfinder(mylist, pattern):
    pattern = set(pattern)
    return [x for x in mylist if x in pattern]
This solution is both more elegant and significantly faster than the original: the comprehension is about 120% faster than the original, while casting the pattern into a set first bumps that up to a whopping 320% faster in my tests.

Now for the bonus: I'll just jump right into it, my solution is as follows:
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
This is a variation of Steven Rumbalski's "inefficient one liner", that, with the addition of the "mylist[i] == pattern[0]" check and thanks to python's short-circuit evaluation, is significantly faster than both the original statement and the itertools version (and every other offered solution as far as I can tell) and it even supports overlapping patterns. So there you go.

                        
这篇关于优雅查找列表中的子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！