说我有一个列表v = [1, 2, 3, 4, 3, 1, 2]
。我想写一个函数find_pair
,它将检查列表中是否有两个数字并且彼此相邻。所以,find_pair(v, 2, 3)
应该返回True
,但find_pair(v, 1, 4)
应该返回False
。
是否可以在没有循环的情况下实现find_pair
?
v = [1,2,3,4,3,1,2]
any([2,3] == v[i:i+2] for i in xrange(len(v) - 1))
虽然@ PaoloCapriotti的版本可以解决问题,但这个版本更快,因为一旦找到匹配,它就会停止解析v
。
如果编写列表的次数远远少于读取列表,那么也许你可以在写入时构建一个前缀树。 [1]会有一个子节点[2],[2]会有[3]和[3] a [4]。使用更复杂的数据集,树将更有用。在您的情况下,它的深度为2,并且将在搜索序列中的初始元素上编入索引。
您仍然要访问每个节点,但只搜索序列的生命周期一次,如果仅追加。当您追加元素时,您将更新树以包括子序列(如果不存在)。然后读取最多为O(2 * k),其中k是唯一元素的数量。在数字的情况下,20是最大读取以测试序列是否在列表中。
速度优势来自预先计算列表包含的长度为2的子序列以及删除重复项。它也可以很好地扩展到更长的长度。 O(深度* k)最坏的情况。如果采用哈希表,效果会更好。
我知道你已经对这篇文章中的答案之一感到满意了,但是你可以试试以下内容
>>> 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
>>>
天哪,这很快
注意**感谢迈克尔指出。我已经更正了,这是我更新的解决方案。
如果您正在寻找一个返回True或False的函数,具体取决于这两个元素是否连续而不管它们的顺序如何,那么使用:
def find_pair(list, x, y):
if abs(list.index(x)-list.index(y)) == 1:
print(True)
else:
print(False)
但是如果元素的顺序很重要,那么删除if条件中的abs()函数。更新:
一个更强大的可能是(如果y预计遵循x):
def find_pair(list, x, y):
if list[list.index(x)+1] == y:
print(True)
else:
print(False)
结合这里的一些想法,这些似乎都可以做到并且非常快
def InList(v, (x, y)):
return any((x == v[i] and y == v[i + 1]) for i in xrange(len(v) - 1))
def FasterInList(v, (x, y)):
if x in v:
indices = [i for i, match in enumerate(v) if match == x]
for i in indices:
if v[i+1] == y:
return True
return False
较简单的InList版本仅比@ abhijit的解决方案略慢,同时进行少一次测试,但仍然几乎是顶级解决方案的两倍。 FasterInList版本比InList快约25%。
import timeit
abhijit = """
v = [1,2,3,4,3,1,2]
def abhijit(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
abhijit(v,(2,3))
abhijit(v,(4,5))
abhijit(v,(1,2))
abhijit(v,(12,2))
"""
# abhijit(v,(3,2)) this never breaks out of the while loop
top = """
v = [1,2,3,4,3,1,2]
def top(v,(x,y)):
any([x,y] == v[i:i+2] for i in xrange(len(v) - 1))
top(v,(2,3))
top(v,(4,5))
top(v,(1,2))
top(v,(12,2))
top(v,(3,2))
"""
InList = """
v = [1,2,3,4,3,1,2]
def InList(v, (x, y)):
return any((x == v[i] and y == v[i + 1]) for i in xrange(len(v) - 1))
InList(v,(2,3))
InList(v,(4,5))
InList(v,(1,2))
InList(v,(12,2))
InList(v,(3,2))
"""
FasterInList = """
v = [1,2,3,4,3,1,2]
def FasterInList(v, (x, y)):
if x in v:
indices = [i for i, match in enumerate(v) if match == x]
for i in indices:
if v[i + 1] == y:
return True
return False
FasterInList(v,(2,3))
FasterInList(v,(4,5))
FasterInList(v,(1,2))
FasterInList(v,(12,2))
FasterInList(v,(3,2))
"""
top_timer = timeit.Timer(stmt=top)
abhijit_timer = timeit.Timer(stmt=abhijit)
InList_timer = timeit.Timer(stmt=InList)
FasterInList_timer = timeit.Timer(stmt=FasterInList)
print "%.2f usec/pass" % (1000000 * top_timer.timeit(number=100000)/100000) # 8.79 usec/pass
print "%.2f usec/pass" % (1000000 * abhijit_timer.timeit(number=100000)/100000) # 4.42 usec/pass
print "%.2f usec/pass" % (1000000 * InList_timer.timeit(number=100000)/100000) # 4.66 usec/pass
print "%.2f usec/pass" % (1000000 * FasterInList_timer.timeit(number=100000)/100000) # 3.70 usec/pass
[2, 3] in [v[i:i+2] for i in range(len(v) - 1)]
这可能是一个圆形的方法,但你可以使用(上面你的变量v):
' 2, 3' in str(v)
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)
也许更简单:
a = range(100)
exists = (55,56) in zip(a, a[1:])
通常,如果不迭代所有值,则是不可能的。毕竟,一千个元素的列表可能以[.., 2, 3]
结尾。
在特殊情况下,有快捷方式。这些值是否始终排序,您是否始终在寻找特定值?如果是这样,您可以例如使用二进制搜索来查找值,然后将其与下一个值进行比较。如果值无序,则没有快捷方式。如果您要查找任何两个后续值,则没有快捷方式。对于介于两者之间的情况,可能存在捷径。
你需要一个循环。
与使用in运算符支持子序列测试的Python字符串不同,Python列表没有内置子序列测试。
您可以使用Boyer-Moore algorithm进行完全不必要的加速。一般情况有点困难,但如果您只是寻找一对,这很简单。
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)
eumiro的答案赢得了优雅,但如果你需要更快的东西,你可以利用内置的list.index()
方法,这可以节省一些时间来迭代整个列表。
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))
当我运行这个时,我得到:
f1 0.00300002098083
f2 0.0
当匹配不是如此接近列表的开头时,这应该更快。