elegant find sub-list in list

by

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.

More Related Contents:

  1. Transpose/Unzip Function (inverse of zip)?
  2. Python List vs. Array – when to use?
  3. Getting the index of the returned max or min item using max()/min() on a list
  4. Why can tuples contain mutable items?
  5. How can I iterate through two lists in parallel?
  6. Find and replace string values in list
  7. Pairs from single list
  8. Splitting a list based on a delimiter word
  9. How to find most common elements of a list? [duplicate]
  10. How do you pick “x” number of unique numbers from a list in Python?
  11. Find first sequence item that matches a criterion [duplicate]
  12. Unable to reverse lists in Python, getting “Nonetype” as list
  13. join two lists of dictionaries on a single key
  14. Assigning values to variables in a list using a loop
  15. Python – How to sort a list of lists by the fourth element in each list? [duplicate]
  16. How to get all combination of n binary value? [duplicate]
  17. Convert a columns of string to list in pandas
  18. Indexing a list with an unique index
  19. Why doesn’t assigning to the loop variable modify the original list? How can I assign back to the list in a loop? [duplicate]
  20. Flattening a list recursively [duplicate]
  21. Python: is using “..%(var)s..” % locals() a good practice?
  22. Python: Remove Duplicate Items from Nested list
  23. How to sort multidimensional array by column?
  24. How to sort a 2D list? [closed]
  25. sum each value in a list of tuples
  26. Getting indices of True values in a boolean list
  27. Python: How to sort a list of dictionaries by several values?
  28. Reading specific columns from a text file in python
  29. How does str(list) work?
  30. Removing an item from a list of lists based on each of the lists first element

Leave a Comment