Author seblin
Recipients abarry, josh.r, rhettinger, seblin, socketpair
Date 2015-12-18.11:35:56
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1450438556.61.0.48885053157.issue25898@psf.upfronthosting.co.za>
In-reply-to
Content
@Josh
What is the point of using iterators here? If the user wants an iterator to be checked then he can throw that iterator right away because it was exhausted by the function. I think that in most cases the user wants to do some postprocessing on a hairstack after being checked. This is why I restricted the arguments to be sequences.

Keeping that restriction in mind a pure Python implementation could look like this:

def has_subsequence(seq, subseq):
    if not subseq:
        return True
    if len(subseq) > len(seq):
        return False
    start = 0
    while True:
        try:
            start = seq.index(subseq[0], start)
        except ValueError:
            # seq.index() did not match
            return False
        stop = start + len(subseq)
        if seq[stop - 1] == subseq[-1] and seq[start:stop] == subseq:
            return True
        start += 1

Unfortunately, this version potentially creates lots of subseqences for checking equality with the `subseq` argument. I tried to minimise the occurrence of those cases by pre-checking the first and the last element of a candidate. Anyway, this seems to be faster for small needles compared to your `deque`-based suggestion.
History
Date User Action Args
2015-12-18 11:35:56seblinsetrecipients: + seblin, rhettinger, socketpair, josh.r, abarry
2015-12-18 11:35:56seblinsetmessageid: <1450438556.61.0.48885053157.issue25898@psf.upfronthosting.co.za>
2015-12-18 11:35:56seblinlinkissue25898 messages
2015-12-18 11:35:56seblincreate