Check if two items are in a list, in a particular

Question

Say I have a list v = [1, 2, 3, 4, 3, 1, 2]. I want to write a function, find_pair which will check if two numbers are in the list and adjacent to each other. So, find_pair(v, 2, 3) should return True, but find_pair(v, 1, 4) should return False.

Is it possible to implement find_pair without a loop?

Answer 1

[2, 3] in [v[i:i+2] for i in range(len(v) - 1)]

Answer 2

If writing the list happens far less often than reading from it, perhaps you could build a tree of prefixes upon write. [1] would have a child node [2], [2] would have a [3], and [3] a [4]. With a more complex data set, the tree would be more useful. It would have a depth of 2 in your case and would be indexed on the initial element in your search sequence.

You'd still be visiting each node, but only once for the life of the searched sequence, if append-only. As you append an element, you'd update the tree to include the subsequnce if not present. Then reads are down to a maximum of O(2 * k) where k is the number of unique elements. In the case of digits, that's 20 reads maximum to test if a sequence is in the list.

The speed advantage comes from precomputing the length-2 subsequences the list contains and from removing duplicates. It also scales well to longer lengths. O(depth * k) worst case. Even better if hashtables are employed.

Answer 3

v = [1,2,3,4,3,1,2]
any([2,3] == v[i:i+2] for i in xrange(len(v) - 1))

While @PaoloCapriotti's version does the trick, this one is faster, because it stops parsing the v as soon as a match is found.

Answer 4

In general it is impossible without iterating over all the values. After all, a list of a thousand elements may end in [.., 2, 3].

In special cases, there are shortcuts. Are the values always ordered and are you always looking for a specific value? If so, you can e.g. use a binary search to find the value and then compare it with the next value. If the values are unordered, there is no shortcut. If you are looking for any two subsequent values, there is no shortcut. For cases in between, there may be a shortcut.

Answer 5

You can use the Boyer-Moore algorithm for a totally unnecessary speedup. The general case is a bit difficult, but it's straightforward if you're just looking for a pair.

def find_pair(seq, a, b):
    i = 1
    while i < len(seq):
        if seq[i] == b and seq[i - 1] == a: return i - 1
        i += 2 - (seq[i] == a)

print find_pair([1, 5, 3, 4, 3, 1, 2, 3, 3], 2, 3)

Answer 6

eumiro's answer wins for elegance, but if you need something even faster, you can take advantage of the built-in list.index() method which saves some time over iterating over the whole list.

v = [1,2,3,4,3,1,2]

def f1(items):
    return any([2,3] == v[i:i+2] for i in xrange(len(v) - 1))

def f2(items):
    i = 0
    index = items.index
    try:
        while 1:
            i = index(2, i) + 1
            if items[i] == 3:
                return True
    except IndexError:
        return False

from timeit import repeat    
print "f1", min(repeat("f1(v)", "from __main__ import f1, v", number=1000))
print "f2", min(repeat("f2(v)", "from __main__ import f2, v", number=1000))

When I run this, I get:

f1 0.00300002098083
f2 0.0

This should be even faster when the match isn't so close to the beginning of the list.