检查两个项目是否按特定顺序在列表中？

Question

我有一个列表 v = [1, 2, 3, 4, 3, 1, 2]。我想写一个函数find_pair，检查两个数字是否在列表中并且相邻。因此，find_pair(v, 2, 3)应该返回True，但find_pair(v, 1, 4)应该返回False。

是否可能不使用循环来实现find_pair函数？

- John Smith

Answer 1

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

虽然@PaoloCapriotti的版本也可以达到效果，但这个版本更快，因为它在找到匹配项后立即停止解析v。

- eumiro

---

splice 每次都会创建一个新的子列表，难道不用两个 if 语句更好吗？如果我错了，请纠正我。 - st0le

我认为 v[i:i+2] 只是查看列表元素。 - eumiro

@eumiro 你的看法不正确 :-) 列表切片会创建新的列表。例如，这就是创建列表副本的惯用语背后的机制：c = s[:]。 - Raymond Hettinger

Answer 2

这可能是一个绕弯子的方法，但您可以使用（使用您上面的变量v）：

' 2, 3' in str(v)

- Jayae

---

你确定"12, 3"这个模式不存在吗？ - DSM

@uosɐſ: 你编辑了答案并增加了一个额外的空格，试图避免我指出的问题，但仍然无法解决。你的版本在序列开头不会匹配2,3（因为2前面的字符将是[, 而不是空格）。请检查一下。 - DSM

我后悔编辑它。1）它不是我的，我只是太心急了；2）它捣乱了你的评论；3）这不是一个有效的解决方案。但是针对您在此处的评论，将列表转换为字符串的方式很重要。如果有前导空格和没有括号，那么它将起作用。 - Jason Kleban

'2, 3' in str([-1] + v)？;-) 当然，此时解决方案已经过于繁琐，不值得这样做 :) - thedayturns

在 '|'+'|'.join(v) + '|' 中加入 '|2|3|' 怎么样？ - rodfersou

Answer 3

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

def find(x, y, v):
    return (x, y) in zip(v, v[1:])

print find(2, 3, v)
print find(1, 4, v)

- Ada Weizmann

Answer 4

也许更简单的是：

a = range(100)
exists = (55,56) in zip(a, a[1:])

- carl

Answer 5

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

- Paolo Capriotti

Answer 6

一般而言，如果要查找某个特定的值，则必须遍历所有值。毕竟，一个包含一千个元素的列表可能以 [.., 2, 3] 结尾。

在某些特殊情况下，有些快捷方式可用。如果这些值始终按顺序排列并且您总是在查找特定值，则可以使用二分查找来查找该值，然后将其与下一个值进行比较。如果这些值无序，则没有快捷方式可用。如果您正在寻找任意两个连续值，则没有快捷方式可用。对于介于这两种情况之间的情况，可能存在一些快捷方式。

- Confusion

Answer 7

你需要一个循环。

与支持使用in运算符进行子序列测试的Python字符串不同，Python列表没有内置的子序列测试。

- Raymond Hettinger

Answer 8

如果你想要完全不必要的加速，可以使用Boyer-Moore算法。一般情况比较困难，但如果你只是在寻找一对，那么很简单。

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)

- user97370

---

在大多数情况下，Python内置的list.index()速度应该能够超过通过纯Python实现Boyer-Moore算法所获得的任何优势。 - Michael Hoffman

真的，这个答案有点玩笑 :) - user97370

Answer 9

如果写列表的频率比读取少得多，那么你可以在写入时构建一个前缀树。[1] 将有一个子节点 [2]，[2] 将有一个 [3]，[3] 将有一个 [4]。对于更复杂的数据集，树将更加有用。在您的情况下，它将具有深度 2，并且将以搜索序列中的初始元素为索引。

如果仅进行追加，则生命周期内只访问每个节点一次。随着添加元素，您将更新树以包括子序列（如果不存在）。然后，读取将最多需要 O(2 * k) 次，其中 k 是唯一元素的数量。在数字的情况下，最多需要 20 次读取来测试列表中是否存在序列。

速度优势来自预计算列表所包含的长度为 2 的子序列并删除重复项。它还可以很好地扩展到更长的长度。最坏情况下，时间复杂度为 O(depth * k)。如果使用哈希表，效果会更好。

- Jason Kleban

Answer 10

您可以尝试以下内容

>>> v = [1,2,3,4,3,1,2]
def InList(v,(i,j)):
    start=1
    try:
         while True:
            if v[v.index(i,start)+1]==j and v[v.index(j,start)-1]==i:
                return True
            start=v.index(i)+1
    except IndexError:
        return False
    except ValueError:
        return False
    
>>> InList(v,(2,3))
True
>>> InList(v,(4,5))
False
>>> InList(v,(1,2))
True
>>> InList(v,(12,2))
False
>>> InList(v,(3,1))
True

好吧，我的好奇心驱使我想测试一下这个实现与最快发布的实现相比表现如何

>>> stmt1="""
v = [1,2,3,4,3,1,2]
def InList(v,(i,j)):
    start=1
    try:
         while True:
            if v[v.index(i,start)+1]==j and v[v.index(j,start)-1]==i:
                return True
            start=v.index(i)+1
    except IndexError:
        return False
    except ValueError:
        return False
InList(v,(2,3))
InList(v,(4,5))
InList(v,(1,2))
InList(v,(12,2))
"""
>>> stmt2="""
v = [1,2,3,4,3,1,2]
def InList(v,(x,y)):
    any([x,y] == v[i:i+2] for i in xrange(len(v) - 1))
InList(v,(2,3))
InList(v,(4,5))
InList(v,(1,2))
InList(v,(12,2))
"""
>>> t1=timeit.Timer(stmt=stmt1)
>>> t2=timeit.Timer(stmt=stmt2)
>>> print "%.2f usec/pass" % (1000000 * t1.timeit(number=100000)/100000)
13.67 usec/pass
>>> print "%.2f usec/pass" % (1000000 * t2.timeit(number=100000)/100000)
20.67 usec/pass
>>> 

哇，这速度真快。

- Abhijit