Find if one list is a subsequence of another

Question

So the problem of verifying if a list is a subsequence of another came up in a discussion, and I wrote code that seems to work (I haven't rigorously tested it).

IsSubequence.py

def is_subsequence(lst1, lst2):
    """
        *   Finds if a list is a subsequence of another.

        *   Params:
            *   `lst1` (`list`): The candidate subsequence.
            *   `lst2` (`list`): The parent list.
        *   Return:
            *   (`bool`): A boolean variable indicating whether `lst1` is a subsequence of `lst2`.
    """
    l1, l2 = len(lst1), len(lst2)
    if l1 > l2:  #`l1` must be <= `l2` for `lst1` to be a subsequence of `lst2`.
        return False
    i = j = 0
    d1, d2 = l1, l2
    while i < l1 and j < l2:
        while lst1[i] != lst2[j]:
            j += 1
            d2 -= 1
            if d1 > d2:  #At this point, `lst1` cannot a subsequence of `lst2`.
                return False
        i, j, d1, d2 = i+1, j+1, d1-1, d2-1
        if d1 > d2:
            return False
    return True

I'm primarily concerned about performance.

Answer 1

Review

• Testing

  (I haven't rigorously tested it).

  Well you should write some test to ensure validity of the function. So even after changes you can be sure it will still work. doctest is a pretty nice module to use, and is a nice extension of your docstring

• Naming

  Variables should have descriptive names!

  lst1, lst2 if it wasn't for that docstring I would not have known what is the subseq and the parent, so instead I propose to rename them to needle and haystack here the intent is more clear

  Same goes for d1, d2... I can see that they are the remaining length of the list, but it is hard to tell from the variable name.

• for is considered more Pythonic vs while

  For loops are Pythons greatest feature IMHO, they are easy to read and short to write

  You should start writing for loops instead of a while, "Loop like a native" might be an interesting talk to view

• Too many assignments in a line

  Might be preference, but I find this line hard to read:

  i, j, d1, d2 = i+1, j+1, d1-1, d2-1

  There are too many values with not enough descriptive names on this line

Alternative

We can instead loop over the haystack and use slicing to compare the sliced haystack with the needle, lastly top it off with the any keyword and write some tests with the doctest module

import doctest

def is_subsequence(needle, haystack):
    """
    Finds if a list is a subsequence of another.

    * args
        needle: the candidate subsequence
        haystack: the parent list

    * returns
        boolean

    >>> is_subsequence([1, 2, 3, 4], [1, 2, 3, 4, 5, 6])
    True
    >>> is_subsequence([1, 2, 3, 4], [1, 2, 3, 5, 6])
    False
    >>> is_subsequence([6], [1, 2, 3, 5, 6])
    True
    >>> is_subsequence([5, 6], [1, 2, 3, 5, 6])
    True
    >>> is_subsequence([[5, 6], 7], [1, 2, 3, [5, 6], 7])
    True
    >>> is_subsequence([1, 2, 3, 4, 5, 6, 7, 8], [1, 2, 3, [5, 6], 7])
    False
    """
    return any(
        haystack[i:i+len(needle)] == needle
        for i in range(len(haystack) - len(needle) + 1)
    )

if __name__ == '__main__':
    doctest.testmod()