查找成对元素的索引
Finding index of pairwise elements
给定目标 ('b', 'a') 和输入：
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
目的是找到连续('b', 'a')元素的位置，得到输出：
>>> find_ba(x0)
0
>>> find_ba(x1)
0
>>> find_ba(x2)
None
>>> find_ba(x3)
1
使用 pairwise 配方：
from itertools import tee
def pairwise(iterable):
"s -> (s0,s1), (s1,s2), (s2, s3), ..."
a, b = tee(iterable)
next(b, None)
return zip(a, b)
我可以这样做以获得所需的输出：
def find_ba(x, target=('b', 'a')):
try:
return next(i for i, pair in enumerate(pairwise(x)) if pair == target)
except StopIteration:
return None
但这需要我遍历所有字符对，直到找到第一个实例。 有没有一种方法可以在不循环所有字符的情况下找到成对元素的索引？
在评论中回答@MatthiasFripp 的问题：
Are your elements in lists or types (as shown) or in a generator (e.g. reading from a file handle)?
x* 都是字符串的元组。所以他们可以通过索引访问。但是，如果 answer/solution 可以用于元组和生成器，那就太好了！
Can you say about how many lists you have to search and about how long they are? That would help for suggesting a search strategy.
元组的长度不固定。它们的大小可以大于 2。
问题的答案是不，如果不循环所有字符，就没有任何方法可以找到对。因为如果你不看一个角色，你不知道它是否与你的一对匹配。
您可以通过将其隐含在语言或库例程中来隐藏迭代，但它必须存在。使其隐式化可能会使代码更高效（例如，如果您将循环移出 Python 解释器并移入预编译语言，例如 C）。或者，它可能不会。
一个（低效、愚蠢！）隐藏东西的例子可能是
def find_ba( x, target=('b','a'), separator = '|' ):
t = separator.join(target)
try:
return ( separator.join([ c for c in x]).index(t) ) / 2
except ValueError:
return None
（根据合同号 SW/l10O/Il0O/01L1lO00/22 提供给 Ministry of Silly walks 的代码，并放置在 public 域中）。
使用 itertools 可以让它变得懒惰，但仍然需要迭代：
import itertools
def check(x, target):
for t in itertools.izip(x, itertools.islice(x, 1, len(x))):
if t == target:
return True
return False
check(x0, ('b', 'a'))
True
编辑：在 python3
中使用 zip
也许例如使用正则表达式？您可以在下面找到两个函数。 findPair 将 return 值与您的示例完全相同。 findPairs 将查找所有非重叠事件和 return 它们在列表中的起始位置。
import re
# Function looks for all non-overlapping occurrences of pair (b, a)
# and returns a list containing their starting positions
def findPairs(x, b, a):
x = str().join(x)
y = str().join([str(b), str(a)])
try:
return [x.regs[0][0] for x in list(re.finditer(y, x))]
except AttributeError:
return None
# Function looks for first occurrence of the pair (b, a)
# and returns starting position if there was a match
# or None when the match was not found
def findPair(x, b, a):
x = str().join(x)
y = str().join([str(b), str(a)])
try:
return re.search(y, x).regs[0][0]
except AttributeError:
return None
if __name__ == "__main__":
# first occurrence
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
outx0 = findPair(x0, 'b', 'a') # 0
outx1 = findPair(x1, 'b', 'a') # 0
outx2 = findPair(x2, 'b', 'a') # None
outx3 = findPair(x3, 'b', 'a') # 1
# multiple occurrences:
x4 = ('z', 'b', 'a', 'a', 'z', 'b', 'a', 'a')
outx4 = findPairs(x4, 'b', 'a') # [1, 5]
编辑：
如果您不想/不喜欢正则表达式，并且只对第一次出现感兴趣，您可以简单地使用方法 find() 并将查找对的函数定义为：
def findPairNoRe(x, b, a):
y = str().join([str(b), str(a)])
res = str().join(x).find(y)
if res == -1:
return None
else:
return res
有更短的公式，但无法完全避免循环。但是，您可以通过 multiprocessing 加快速度（见结尾）。首先，这里有一些搜索方法（所有 O(n)），具有速度和简单性的各种组合。
如果值在元组或列表中，则使用相当简单、快速的代码：
def find_ba(tup, target):
last_check = len(tup)-len(target)
for i, c in enumerate(tup):
# note: the test below only uses c 95% of the time,
# which makes it pretty fast
if c == target[0] and i <= last_check and tup[i:i+len(target)] == target:
return i
return None
不是那么简单，而是更快，受@MSeifert 启发，但针对更长的目标进行了优化：
def find_ba(tup, target):
import itertools
search = set(target)
target_len = len(target)
for i in count(start=1, step=target_len):
try:
if tup[i] in search: # O(1) reverse lookup
# search in this neighborhood
c = tup[i]
j = 0
while True:
try:
# find next occurrence of c in the target
j = target[j:].index(c)
except ValueError: # no more occurrences of c in target
break
# align tup and target and check for a match
if j >= i and tup[i-j:i-j+target_len] == target:
return i-j
except IndexError:
break
return None
由于您已经在构造字符元组时遇到麻烦，因此您可以构造字符串，然后让 Python 在本机 C 代码中进行优化：
def find_ba(x, target):
# assuming x and target are both strings
pos = x.find(target)
return pos if pos >= 0 else None
（尽管如此，如果可能的话，您最好在创建元组或字符串时进行搜索。）
如果值在生成器中，那么这将起作用（与您已有的非常相似）。如果底层源很慢（例如，从磁盘读取项目），这将比创建长元组并搜索它们更有效：
import itertools
def find_ba(lst, target):
a, b = itertools.tee(lst)
next(b)
for i, pair in enumerate(zip(a, b)):
if pair == target:
return i
return None
注意：在 Python 2.7 上，使用 itertools.izip 而不是在 Python 2.7.
上压缩
加快速度的主要方法是使用 multiprocessing 库。如果您有大量输入要处理，您可以使用 multiprocessing.Pool.map 以循环方式将每个输入发送给不同的工作人员。如果你只有几个输入并且每个输入都很长，那么你可能想使用 itertools.islice 将它们分成较长的块，然后将每个块发送到 multiprocessing.Pool.map 直到你得到一个命中；然后你可以开始处理下一个输入。我无法从你的问题中判断出哪种方法最有效。
正如 nigel222 所指出的，没有办法（在最坏的情况下）避免遍历整个列表，因为您必须进行详尽的比较以确保您想要的项目不包含在您的可迭代对象中。
不过，如果您要对各种可能的子序列进行大量此类查询，那么将其压入集合可能是值得的，因为集合的查找时间复杂度为 O(1)。
...
my_pairwise = set(pairwise(x))
found_subsequences = [subsequence
for subsequence in collection_of_subsequences
if subsequence in my_pairwise]
这样，通过您的 x 的 O(n) 迭代只发生一次，之后的每次查找都是 O(1)。
虽然不实用，但可以解决你的问题
def look_up(needle, haystack):
i = ''.join(haystack).find(''.join(needle))
return i if i > -1 else None
所以假设我们有这个：
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
ba = ('b', 'a')
我们得到这个：
print(look_up(ba, x0)) # Prints: 0
print(look_up(ba, x1)) # Prints: 0
print(look_up(ba, x2)) # Prints: None
print(look_up(ba, x3)) # Prints: 1
这是多次出现的情况：
def look_up_multiple(needle, haystack):
needle_str = ''.join(needle)
haystack_str = ''.join(haystack)
indexes = []
i = 0
while i < len(haystack_str):
i = haystack_str.find(needle_str, i)
if i > -1:
indexes.append(i)
i += 2
return indexes
让我们运行它：
x = ('b', 'a', 'z', 'z', 'b', 'a')
ba = ('b', 'a')
print(look_up_multiple(ba, x)) # Prints: [0, 4]
尽管它在您的案例中有效，但并不令人印象深刻，请检查一下。
我们只是提取样本中匹配项的索引并检查它是否连续。
def consecutive_index(src,sample):
result = None
il = [src.index(a) for a in sample if a in src]
if len(il) == len(sample) and len(range(il[0],il[-1]))==1:
result = il[0]
return result
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
sample = ('b', 'a')
##TEST your given combinations.
print consecutive_index(x0,sample) #expected 0
print consecutive_index(x1,sample) #expected 0
print consecutive_index(x2,sample) #expected None
print consecutive_index(x3,sample) #expected 1
您可以通过将列表转换为字符串来实现。
def findba(x,target):
x1 = "".join(x)
target1 = "".join(target)
if target1 in x1:
return x1.index(target1)
else:
return None
ab = ('b','a')
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
print findba(x0,ab)
print findba(x1,ab)
print findba(x2,ab)
print findba(x3,ab)
正如已经指出的那样，您无法避免遍历所有字符。您可以使其变得惰性并仅在输入元组上迭代一次，如下所示（假设 Python 3）：
from itertools import islice, tee
def find_ba(x):
pairs = zip(*(islice(g, i, None) for i, g in enumerate(tee(x, 2))))
return next(
(i for i, pair in enumerate(pairs) if pair == ('b', 'a')),
None)
此解决方案使用列表的 index 方法查找 target 的第一个元素。然后检查他列出的下一项是否与 target 的第二项相匹配。如果不是，则查找下一次出现的 'b' 并再次检查以下项目。洗漂洗重复。
这不会遍历所有对，而是查找预期对中的第一项，然后检查下一项。
def find_ba(x, target=('b','a')):
try:
ind = 0
while ind < len(x):
ind += x[ind:].index(target[0])
if x[ind+1] == target[1]:
return ind
ind += 1
except ValueError:
return None
测试：
# 100 random letters
letters = ['f', 'y', 'h', 'u', 't', 'l', 'y', 'u', 'm', 'z', 'a', 'a',
'i', 't', 'g', 'm', 'b', 'l', 'z', 'q', 'g', 'f', 'f', 'b',
'b', 'a', 'c', 'z', 'n', 'j', 'v', 'b', 'k', 'j', 'y', 'm',
'm', 'f', 'z', 'x', 'f', 'q', 'w', 'h', 'p', 'x', 't', 'n',
'm', 'd', 'z', 'q', 'v', 'h', 'b', 'f', 'q', 'd', 'b', 's',
'a', 't', 'j', 'm', 'h', 'r', 'd', 'n', 'e', 'k', 'y', 'z',
'd', 'e', 'x', 'h', 'r', 'z', 'b', 'n', 'q', 'v', 't', 'q',
'f', 'w', 'b', 'w', 'f', 'c', 'f', 'h', 'q', 'o', 'r', 'f',
'w', 'w', 'n', 'v']
find_ba(letters) # 24
使用zip进行比较的方法：
def find_ba1(x):
try:
return [(i,j) for i,j in zip(x[:-1], x[1:])].index(('b', 'a'))
except ValueError:
return None
还有一点速度测试：
%timeit find_ba(letters)
100000 loops, best of 3: 2.31 µs per loop
%timeit find_ba1(letters)
100000 loops, best of 3: 8.4 µs per loop
如果对数据的性质没有任何承诺（即假设它是随机的），搜索不可能比 O(n) 更好。充其量，您可以通过使用您正在尝试做的事情的特定信息优化问题来减少波浪号的操作次数（即减少一个因子），包括：目标的大小，重复字符目标（搜索 'b' 'b' 'a' 我们可以查看每个其他字符并知道它必须是 'b' 才能匹配我们的序列，然后查看周围的字符）或我们可以通过对较小数据集的快速分析获得的任何其他信息（再次假设序列表是未知量）。例如，我研究的一件事是通过迭代目标的长度并确定它是否是我们要搜索的字符之一来搜索目标。当然，这个问题不是搜索列表中的每个索引（我们现在接触 len(list)/len(target) 元素）我们现在对我们接触的每个元素执行更多操作（换句话说，对于 'b', 'a' 我们每两个元素搜索一次，但是我们寻找两个东西）。这在减少操作数量方面没有任何作用，但是，它会显着减少您必须从辅助内存存储加载的元素数量，假设您计划在相当大的序列中寻找目标，这就是为什么您正在避免遍历每个元素。如果提高效率是您的唯一目标，您还可以通过多种方式使用多重并行来提高搜索效率。 （如果你选择这条路线，请记住使用多处理而不是线程，因为 python 的线程模块只支持并发，而不是多并行，因为解释器瓶颈线程）。
作为结论并直接回答您提出的问题，是的，完全有可能找到成对元素的索引，而无需查看序列中的每个元素。然而，这样做需要首先查看手头问题的具体信息，然后将这些信息应用到搜索中。我认为最好的方法是首先通过分析数据进行搜索，然后执行最适合该输入的搜索方法。换句话说，如果有重复，你可以使用它，但如果没有，你可以退回到另一个搜索。
最快的 general 搜索算法将具有 O(n) 平均性能（称为线性搜索），这意味着您别无选择（除了常数因子）处理每个元素。
鉴于您的问题：
Is there a way to finding index of pairwise elements without looping all the characters?
这是可能的（虽然它仍然是 O(n)），只需查看每个第二项：
from itertools import count
def find_ab(tup):
for idx in count(start=1, step=2):
try:
if tup[idx] == 'b':
if tup[idx+1] == 'a':
return idx
elif tup[idx] == 'a':
if tup[idx-1] == 'b':
return idx-1
except IndexError:
break
在最坏的情况下，它仍然会比较所有项目，但它会为每个不是 'b' 或 'a'.
的奇数索引项目跳过一个项目
这有点像作弊所以让我解释一下为什么 常见 替代方案在你的情况下是不可能的：
二分查找
二分查找只需要比较log(n)项，但需要对序列进行排序。您的示例未排序，因此对它们进行排序需要 O(n*log(n)) 操作 - 这不仅会处理每个项目一次，还会处理其中一些项目多次。并不是说我知道对相邻元素进行排序的明智方法。
桶搜索（或哈希表）
您有元组，因此创建哈希表（dict）没有意义，因为要创建该结构，您需要处理每个元素。
但是，如果您计划对这些配对进行多次搜索，您可以创建一次字典 (O(n))，然后在 O(1):
中进行多次搜索
d = {}
for idx, pair in enumerate(pairwise(x0)):
if pair not in d: # keep only the first index for each pair
d[pair] = idx
>>> d.get(('b', 'a'), None)
0
然而，如果您只想搜索 one 对，这种方法会慢得多，因为您丢失了 "short-circuit behaviour"（一旦找到匹配项就停止）并在创建字典时处理所有元素。
其他方法
除了一般方法：
O(n)线性搜索O(log(n))二分查找（排序后的数据）O(1) 查找（对于可哈希查找或其他只需要在 "bucket" 中搜索的搜索问题）
您通常可以利用有关数据的任何结构或知识来减少需要处理的项目数量。问题主要在于（可能）没有用于这些的现有数据结构，并且自制实现通常最终比天真的 "process all elements" 方法慢几个数量级。但是如果你有任何关于你的序列的元信息，那么你就可以利用它。
最后的评论
pairwise 的方法实际上很好，但你也可以使用 iteration_utilities.successive1。最后我检查了它比食谱快大约 1.5 到 2 倍。即使你不改变方法并接受你需要在最坏的情况下处理所有（或几乎所有）元素，它可能会更快！
该数据可能已生成。也许在创建期间为元素实际 "search" 是值得的。这样一来，您根本不需要额外传递数据。或者您可以在创建数据集时创建 dict（这允许之后进行 O(1) 查找）。如果有某种方法可以提取信息，有时最好查看 generated/downloaded/fetched 数据集的过程。
现在，写完所有这些文字后，我需要说明显而易见的事情：
你的方法真好。即使它需要在最坏的情况下处理所有元素，它也会使用完美匹配（pairwise-recipe）来解决手头的问题，而且即使对于长输入，它实际上也应该工作得非常快。对于包含 100 万 'z' 的元组，它在我的计算机上只需要 200ms。因此，您每秒可以处理数百万个元素（即使在像我这样的旧计算机和慢计算机上也是如此）。这对于大数据来说可能不够快，但是 pure-python 不是处理大数据的好语言（通常你需要编写 C 扩展，使用 Cython 或一些 NumPy，Pandas 或衍生方法）。此外，生成器上的 next 函数是惰性的（假设您在 python2 上使用 itertools.izip 而不是 zip），因此您只处理每个元组，直到找到匹配项。
就我个人而言，我会简单地使用您原来的方法。或者，如果我必须找到几对，那么我将只创建我之前提到的字典（甚至可能序列化它）并在其中进行查找。
赏金原因明确要求"credible and/or official sources"。幸运的是 "search algorithms" 得到了很好的研究，因此您可以在有关算法的基础教科书中找到对上述每种方法的解释。例如：
- Cormen 等al - 算法简介
Sedgewick & Wayne - 算法
维基百科："Linear search"
- 维基百科："Binary search"
- 维基百科："Hashtable"（本质上是
dict）。
python wiki："TimeComplexity" 中还有 python 类型时间复杂度的小概览。对于查找，您必须检查 "Get Item " 或 "in".
1 披露：我是那个第 3 方库的作者。
解法：
构建成对的序列数组后，可以使用numpy where定位序列。
#np.roll(x1,-1) shifts the list leftwise one element. np.core.defchararray.add builds a paired sequence.
np.where(np.core.defchararray.add(x1,np.roll(x1,-1)) == 'ba')[0]
测试
for x in [x0,x1,x2,x3]:
print (np.where(np.core.defchararray.add(x,np.roll(x,-1)) == 'ba'))[0]
[0]
[0]
[]
[1]
我尝试对 MSeifert 的方法和我的方法进行基准测试。我的代码源自 MSeifert 的代码，但试图进一步发展，即跳转到下一个目标词，而不是一次走两步。顺便说一句，我的通常更快，不需要任何包。如果有人有任何问题或意见，请告诉我。谢谢。
2017 年 5 月 9 日编辑：
为了回应@Matthias Fripp 的评论，我添加了 10k 和 100k 元素的测试元组。对于 10k 个元素，我的仍然更快，但不是 100k 个元素。因此，我的代码不是最优的。我认为我的方法不是@MSeifert 指出的 "right" 答案，因为最初的问题询问的是不搜索所有元素的方法。
import random # to generate data
# Set up data
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
x4 = tuple([random.choice(x3) for i in xrange(10000)])
x5 = tuple([random.choice(x3) for i in xrange(100000)])
# Set up functions
# My code
def findPairwise(x,target):
currentX = x
cumulatedIdx=0
while(1):
try:
idx = currentX.index(target[0])
try:
if currentX[idx+1] == target[1]:
return(idx+cumulatedIdx)
except:
pass
except:
break
currentX = currentX[idx+2:]
cumulatedIdx += idx+2
# MSeifert's method
from itertools import count
def find_ab(tup,target):
for idx in count(start=1, step=2):
try:
if tup[idx] == target[0]:
if tup[idx+1] == target[1]:
return idx
elif tup[idx] == target[1]:
if tup[idx-1] == target[0]:
return idx-1
except IndexError:
break
结果
In [109]: %timeit findPairwise(x0,target)
The slowest run took 8.66 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.27 µs per loop
In [110]: %timeit find_ab(x0,target)
The slowest run took 5.49 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 2.04 µs per loop
In [111]: %timeit findPairwise(x1,target)
The slowest run took 4.75 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 1.46 µs per loop
In [112]: %timeit find_ab(x1,target)
The slowest run took 5.04 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 1.99 µs per loop
In [113]: %timeit findPairwise(x2,target)
The slowest run took 4.66 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 2.56 µs per loop
In [114]: %timeit find_ab(x2,target)
The slowest run took 5.89 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 4.25 µs per loop
In [115]: %timeit findPairwise(x3,target)
The slowest run took 8.59 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.28 µs per loop
In [116]: %timeit find_ab(x3,target)
The slowest run took 6.66 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.65 µs per loop
In [151]: %timeit findPairwise(x4,target)
The slowest run took 5.46 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.27 µs per loop
In [152]: %timeit find_ab(x4,target)
The slowest run took 6.21 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 1.92 µs per loop
In [153]: %timeit findPairwise(x5,target)
1000 loops, best of 3: 325 µs per loop
In [154]: %timeit find_ab(x5,target)
The slowest run took 4.35 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 3.45 µs per loop
如果您在相同的输入中重复搜索不同的目标，您可以通过创建所有唯一字符串的位置的散列来避免每次循环输入，如下面的代码所示。对于初始设置，这需要通过每个输入进行一次循环，但随后搜索几乎是瞬时的（无循环）。
# store first occurrence of each unique 2-char string (O(n))
x1_first = dict()
target_len = 2
for i in range(len(x1)):
x1_first.setdefault(x1[i:i+target_len], i)
# find first occurrence of a particular string without looping (O(1))
print x1_first.get(('a', 'b'), None)
注意：这与@MSeifert 的回答之一非常相似，但展示了如何处理任意目标长度。如果你有多个目标长度需要担心，那么你需要为每个长度创建单独的字典，这对于存储来说是低效的。在这种情况下，您可能会更好地创建最长可能目标（例如 10 个字符）的排序列表，然后使用二分法搜索它（请参阅 bisect 模块）。对于较短的子字符串，您需要扫描多个匹配项并取出最早的一个。
给定目标 ('b', 'a') 和输入：
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
目的是找到连续('b', 'a')元素的位置，得到输出：
>>> find_ba(x0)
0
>>> find_ba(x1)
0
>>> find_ba(x2)
None
>>> find_ba(x3)
1
使用 pairwise 配方：
from itertools import tee
def pairwise(iterable):
"s -> (s0,s1), (s1,s2), (s2, s3), ..."
a, b = tee(iterable)
next(b, None)
return zip(a, b)
我可以这样做以获得所需的输出：
def find_ba(x, target=('b', 'a')):
try:
return next(i for i, pair in enumerate(pairwise(x)) if pair == target)
except StopIteration:
return None
但这需要我遍历所有字符对，直到找到第一个实例。 有没有一种方法可以在不循环所有字符的情况下找到成对元素的索引？
在评论中回答@MatthiasFripp 的问题：
Are your elements in lists or types (as shown) or in a generator (e.g. reading from a file handle)?
x* 都是字符串的元组。所以他们可以通过索引访问。但是，如果 answer/solution 可以用于元组和生成器，那就太好了！
Can you say about how many lists you have to search and about how long they are? That would help for suggesting a search strategy.
元组的长度不固定。它们的大小可以大于 2。
问题的答案是不，如果不循环所有字符，就没有任何方法可以找到对。因为如果你不看一个角色，你不知道它是否与你的一对匹配。
您可以通过将其隐含在语言或库例程中来隐藏迭代，但它必须存在。使其隐式化可能会使代码更高效（例如，如果您将循环移出 Python 解释器并移入预编译语言，例如 C）。或者，它可能不会。
一个（低效、愚蠢！）隐藏东西的例子可能是
def find_ba( x, target=('b','a'), separator = '|' ):
t = separator.join(target)
try:
return ( separator.join([ c for c in x]).index(t) ) / 2
except ValueError:
return None
（根据合同号 SW/l10O/Il0O/01L1lO00/22 提供给 Ministry of Silly walks 的代码，并放置在 public 域中）。
使用 itertools 可以让它变得懒惰，但仍然需要迭代：
import itertools
def check(x, target):
for t in itertools.izip(x, itertools.islice(x, 1, len(x))):
if t == target:
return True
return False
check(x0, ('b', 'a'))
True
编辑：在 python3
中使用zip
也许例如使用正则表达式？您可以在下面找到两个函数。 findPair 将 return 值与您的示例完全相同。 findPairs 将查找所有非重叠事件和 return 它们在列表中的起始位置。
import re
# Function looks for all non-overlapping occurrences of pair (b, a)
# and returns a list containing their starting positions
def findPairs(x, b, a):
x = str().join(x)
y = str().join([str(b), str(a)])
try:
return [x.regs[0][0] for x in list(re.finditer(y, x))]
except AttributeError:
return None
# Function looks for first occurrence of the pair (b, a)
# and returns starting position if there was a match
# or None when the match was not found
def findPair(x, b, a):
x = str().join(x)
y = str().join([str(b), str(a)])
try:
return re.search(y, x).regs[0][0]
except AttributeError:
return None
if __name__ == "__main__":
# first occurrence
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
outx0 = findPair(x0, 'b', 'a') # 0
outx1 = findPair(x1, 'b', 'a') # 0
outx2 = findPair(x2, 'b', 'a') # None
outx3 = findPair(x3, 'b', 'a') # 1
# multiple occurrences:
x4 = ('z', 'b', 'a', 'a', 'z', 'b', 'a', 'a')
outx4 = findPairs(x4, 'b', 'a') # [1, 5]
编辑：
如果您不想/不喜欢正则表达式，并且只对第一次出现感兴趣，您可以简单地使用方法 find() 并将查找对的函数定义为：
def findPairNoRe(x, b, a):
y = str().join([str(b), str(a)])
res = str().join(x).find(y)
if res == -1:
return None
else:
return res
有更短的公式，但无法完全避免循环。但是，您可以通过 multiprocessing 加快速度（见结尾）。首先，这里有一些搜索方法（所有 O(n)），具有速度和简单性的各种组合。
如果值在元组或列表中，则使用相当简单、快速的代码：
def find_ba(tup, target):
last_check = len(tup)-len(target)
for i, c in enumerate(tup):
# note: the test below only uses c 95% of the time,
# which makes it pretty fast
if c == target[0] and i <= last_check and tup[i:i+len(target)] == target:
return i
return None
不是那么简单，而是更快，受@MSeifert 启发，但针对更长的目标进行了优化：
def find_ba(tup, target):
import itertools
search = set(target)
target_len = len(target)
for i in count(start=1, step=target_len):
try:
if tup[i] in search: # O(1) reverse lookup
# search in this neighborhood
c = tup[i]
j = 0
while True:
try:
# find next occurrence of c in the target
j = target[j:].index(c)
except ValueError: # no more occurrences of c in target
break
# align tup and target and check for a match
if j >= i and tup[i-j:i-j+target_len] == target:
return i-j
except IndexError:
break
return None
由于您已经在构造字符元组时遇到麻烦，因此您可以构造字符串，然后让 Python 在本机 C 代码中进行优化：
def find_ba(x, target):
# assuming x and target are both strings
pos = x.find(target)
return pos if pos >= 0 else None
（尽管如此，如果可能的话，您最好在创建元组或字符串时进行搜索。）
如果值在生成器中，那么这将起作用（与您已有的非常相似）。如果底层源很慢（例如，从磁盘读取项目），这将比创建长元组并搜索它们更有效：
import itertools
def find_ba(lst, target):
a, b = itertools.tee(lst)
next(b)
for i, pair in enumerate(zip(a, b)):
if pair == target:
return i
return None
注意：在 Python 2.7 上，使用 itertools.izip 而不是在 Python 2.7.
上压缩加快速度的主要方法是使用 multiprocessing 库。如果您有大量输入要处理，您可以使用 multiprocessing.Pool.map 以循环方式将每个输入发送给不同的工作人员。如果你只有几个输入并且每个输入都很长，那么你可能想使用 itertools.islice 将它们分成较长的块，然后将每个块发送到 multiprocessing.Pool.map 直到你得到一个命中；然后你可以开始处理下一个输入。我无法从你的问题中判断出哪种方法最有效。
正如 nigel222 所指出的，没有办法（在最坏的情况下）避免遍历整个列表，因为您必须进行详尽的比较以确保您想要的项目不包含在您的可迭代对象中。
不过，如果您要对各种可能的子序列进行大量此类查询，那么将其压入集合可能是值得的，因为集合的查找时间复杂度为 O(1)。
...
my_pairwise = set(pairwise(x))
found_subsequences = [subsequence
for subsequence in collection_of_subsequences
if subsequence in my_pairwise]
这样，通过您的 x 的 O(n) 迭代只发生一次，之后的每次查找都是 O(1)。
虽然不实用，但可以解决你的问题
def look_up(needle, haystack):
i = ''.join(haystack).find(''.join(needle))
return i if i > -1 else None
所以假设我们有这个：
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
ba = ('b', 'a')
我们得到这个：
print(look_up(ba, x0)) # Prints: 0
print(look_up(ba, x1)) # Prints: 0
print(look_up(ba, x2)) # Prints: None
print(look_up(ba, x3)) # Prints: 1
这是多次出现的情况：
def look_up_multiple(needle, haystack):
needle_str = ''.join(needle)
haystack_str = ''.join(haystack)
indexes = []
i = 0
while i < len(haystack_str):
i = haystack_str.find(needle_str, i)
if i > -1:
indexes.append(i)
i += 2
return indexes
让我们运行它：
x = ('b', 'a', 'z', 'z', 'b', 'a')
ba = ('b', 'a')
print(look_up_multiple(ba, x)) # Prints: [0, 4]
尽管它在您的案例中有效，但并不令人印象深刻，请检查一下。
我们只是提取样本中匹配项的索引并检查它是否连续。
def consecutive_index(src,sample):
result = None
il = [src.index(a) for a in sample if a in src]
if len(il) == len(sample) and len(range(il[0],il[-1]))==1:
result = il[0]
return result
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
sample = ('b', 'a')
##TEST your given combinations.
print consecutive_index(x0,sample) #expected 0
print consecutive_index(x1,sample) #expected 0
print consecutive_index(x2,sample) #expected None
print consecutive_index(x3,sample) #expected 1
您可以通过将列表转换为字符串来实现。
def findba(x,target):
x1 = "".join(x)
target1 = "".join(target)
if target1 in x1:
return x1.index(target1)
else:
return None
ab = ('b','a')
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
print findba(x0,ab)
print findba(x1,ab)
print findba(x2,ab)
print findba(x3,ab)
正如已经指出的那样，您无法避免遍历所有字符。您可以使其变得惰性并仅在输入元组上迭代一次，如下所示（假设 Python 3）：
from itertools import islice, tee
def find_ba(x):
pairs = zip(*(islice(g, i, None) for i, g in enumerate(tee(x, 2))))
return next(
(i for i, pair in enumerate(pairs) if pair == ('b', 'a')),
None)
此解决方案使用列表的 index 方法查找 target 的第一个元素。然后检查他列出的下一项是否与 target 的第二项相匹配。如果不是，则查找下一次出现的 'b' 并再次检查以下项目。洗漂洗重复。
这不会遍历所有对，而是查找预期对中的第一项，然后检查下一项。
def find_ba(x, target=('b','a')):
try:
ind = 0
while ind < len(x):
ind += x[ind:].index(target[0])
if x[ind+1] == target[1]:
return ind
ind += 1
except ValueError:
return None
测试：
# 100 random letters
letters = ['f', 'y', 'h', 'u', 't', 'l', 'y', 'u', 'm', 'z', 'a', 'a',
'i', 't', 'g', 'm', 'b', 'l', 'z', 'q', 'g', 'f', 'f', 'b',
'b', 'a', 'c', 'z', 'n', 'j', 'v', 'b', 'k', 'j', 'y', 'm',
'm', 'f', 'z', 'x', 'f', 'q', 'w', 'h', 'p', 'x', 't', 'n',
'm', 'd', 'z', 'q', 'v', 'h', 'b', 'f', 'q', 'd', 'b', 's',
'a', 't', 'j', 'm', 'h', 'r', 'd', 'n', 'e', 'k', 'y', 'z',
'd', 'e', 'x', 'h', 'r', 'z', 'b', 'n', 'q', 'v', 't', 'q',
'f', 'w', 'b', 'w', 'f', 'c', 'f', 'h', 'q', 'o', 'r', 'f',
'w', 'w', 'n', 'v']
find_ba(letters) # 24
使用zip进行比较的方法：
def find_ba1(x):
try:
return [(i,j) for i,j in zip(x[:-1], x[1:])].index(('b', 'a'))
except ValueError:
return None
还有一点速度测试：
%timeit find_ba(letters)
100000 loops, best of 3: 2.31 µs per loop
%timeit find_ba1(letters)
100000 loops, best of 3: 8.4 µs per loop
如果对数据的性质没有任何承诺（即假设它是随机的），搜索不可能比 O(n) 更好。充其量，您可以通过使用您正在尝试做的事情的特定信息优化问题来减少波浪号的操作次数（即减少一个因子），包括：目标的大小，重复字符目标（搜索 'b' 'b' 'a' 我们可以查看每个其他字符并知道它必须是 'b' 才能匹配我们的序列，然后查看周围的字符）或我们可以通过对较小数据集的快速分析获得的任何其他信息（再次假设序列表是未知量）。例如，我研究的一件事是通过迭代目标的长度并确定它是否是我们要搜索的字符之一来搜索目标。当然，这个问题不是搜索列表中的每个索引（我们现在接触 len(list)/len(target) 元素）我们现在对我们接触的每个元素执行更多操作（换句话说，对于 'b', 'a' 我们每两个元素搜索一次，但是我们寻找两个东西）。这在减少操作数量方面没有任何作用，但是，它会显着减少您必须从辅助内存存储加载的元素数量，假设您计划在相当大的序列中寻找目标，这就是为什么您正在避免遍历每个元素。如果提高效率是您的唯一目标，您还可以通过多种方式使用多重并行来提高搜索效率。 （如果你选择这条路线，请记住使用多处理而不是线程，因为 python 的线程模块只支持并发，而不是多并行，因为解释器瓶颈线程）。
作为结论并直接回答您提出的问题，是的，完全有可能找到成对元素的索引，而无需查看序列中的每个元素。然而，这样做需要首先查看手头问题的具体信息，然后将这些信息应用到搜索中。我认为最好的方法是首先通过分析数据进行搜索，然后执行最适合该输入的搜索方法。换句话说，如果有重复，你可以使用它，但如果没有，你可以退回到另一个搜索。
最快的 general 搜索算法将具有 O(n) 平均性能（称为线性搜索），这意味着您别无选择（除了常数因子）处理每个元素。
鉴于您的问题：
Is there a way to finding index of pairwise elements without looping all the characters?
这是可能的（虽然它仍然是 O(n)），只需查看每个第二项：
from itertools import count
def find_ab(tup):
for idx in count(start=1, step=2):
try:
if tup[idx] == 'b':
if tup[idx+1] == 'a':
return idx
elif tup[idx] == 'a':
if tup[idx-1] == 'b':
return idx-1
except IndexError:
break
在最坏的情况下，它仍然会比较所有项目，但它会为每个不是 'b' 或 'a'.
这有点像作弊所以让我解释一下为什么 常见 替代方案在你的情况下是不可能的：
二分查找
二分查找只需要比较log(n)项，但需要对序列进行排序。您的示例未排序，因此对它们进行排序需要 O(n*log(n)) 操作 - 这不仅会处理每个项目一次，还会处理其中一些项目多次。并不是说我知道对相邻元素进行排序的明智方法。
桶搜索（或哈希表）
您有元组，因此创建哈希表（dict）没有意义，因为要创建该结构，您需要处理每个元素。
但是，如果您计划对这些配对进行多次搜索，您可以创建一次字典 (O(n))，然后在 O(1):
d = {}
for idx, pair in enumerate(pairwise(x0)):
if pair not in d: # keep only the first index for each pair
d[pair] = idx
>>> d.get(('b', 'a'), None)
0
然而，如果您只想搜索 one 对，这种方法会慢得多，因为您丢失了 "short-circuit behaviour"（一旦找到匹配项就停止）并在创建字典时处理所有元素。
其他方法
除了一般方法：
O(n)线性搜索O(log(n))二分查找（排序后的数据）O(1)查找（对于可哈希查找或其他只需要在 "bucket" 中搜索的搜索问题）
您通常可以利用有关数据的任何结构或知识来减少需要处理的项目数量。问题主要在于（可能）没有用于这些的现有数据结构，并且自制实现通常最终比天真的 "process all elements" 方法慢几个数量级。但是如果你有任何关于你的序列的元信息，那么你就可以利用它。
最后的评论
pairwise 的方法实际上很好，但你也可以使用 iteration_utilities.successive1。最后我检查了它比食谱快大约 1.5 到 2 倍。即使你不改变方法并接受你需要在最坏的情况下处理所有（或几乎所有）元素，它可能会更快！
该数据可能已生成。也许在创建期间为元素实际 "search" 是值得的。这样一来，您根本不需要额外传递数据。或者您可以在创建数据集时创建 dict（这允许之后进行 O(1) 查找）。如果有某种方法可以提取信息，有时最好查看 generated/downloaded/fetched 数据集的过程。
现在，写完所有这些文字后，我需要说明显而易见的事情：
你的方法真好。即使它需要在最坏的情况下处理所有元素，它也会使用完美匹配（pairwise-recipe）来解决手头的问题，而且即使对于长输入，它实际上也应该工作得非常快。对于包含 100 万 'z' 的元组，它在我的计算机上只需要 200ms。因此，您每秒可以处理数百万个元素（即使在像我这样的旧计算机和慢计算机上也是如此）。这对于大数据来说可能不够快，但是 pure-python 不是处理大数据的好语言（通常你需要编写 C 扩展，使用 Cython 或一些 NumPy，Pandas 或衍生方法）。此外，生成器上的 next 函数是惰性的（假设您在 python2 上使用 itertools.izip 而不是 zip），因此您只处理每个元组，直到找到匹配项。
就我个人而言，我会简单地使用您原来的方法。或者，如果我必须找到几对，那么我将只创建我之前提到的字典（甚至可能序列化它）并在其中进行查找。
赏金原因明确要求"credible and/or official sources"。幸运的是 "search algorithms" 得到了很好的研究，因此您可以在有关算法的基础教科书中找到对上述每种方法的解释。例如：
- Cormen 等al - 算法简介
Sedgewick & Wayne - 算法
维基百科："Linear search"
- 维基百科："Binary search"
- 维基百科："Hashtable"（本质上是
dict）。
python wiki："TimeComplexity" 中还有 python 类型时间复杂度的小概览。对于查找，您必须检查 "Get Item " 或 "in".
1 披露：我是那个第 3 方库的作者。
解法：
构建成对的序列数组后，可以使用numpy where定位序列。
#np.roll(x1,-1) shifts the list leftwise one element. np.core.defchararray.add builds a paired sequence.
np.where(np.core.defchararray.add(x1,np.roll(x1,-1)) == 'ba')[0]
测试
for x in [x0,x1,x2,x3]:
print (np.where(np.core.defchararray.add(x,np.roll(x,-1)) == 'ba'))[0]
[0]
[0]
[]
[1]
我尝试对 MSeifert 的方法和我的方法进行基准测试。我的代码源自 MSeifert 的代码，但试图进一步发展，即跳转到下一个目标词，而不是一次走两步。顺便说一句，我的通常更快，不需要任何包。如果有人有任何问题或意见，请告诉我。谢谢。
2017 年 5 月 9 日编辑：
为了回应@Matthias Fripp 的评论，我添加了 10k 和 100k 元素的测试元组。对于 10k 个元素，我的仍然更快，但不是 100k 个元素。因此，我的代码不是最优的。我认为我的方法不是@MSeifert 指出的 "right" 答案，因为最初的问题询问的是不搜索所有元素的方法。
import random # to generate data
# Set up data
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
x4 = tuple([random.choice(x3) for i in xrange(10000)])
x5 = tuple([random.choice(x3) for i in xrange(100000)])
# Set up functions
# My code
def findPairwise(x,target):
currentX = x
cumulatedIdx=0
while(1):
try:
idx = currentX.index(target[0])
try:
if currentX[idx+1] == target[1]:
return(idx+cumulatedIdx)
except:
pass
except:
break
currentX = currentX[idx+2:]
cumulatedIdx += idx+2
# MSeifert's method
from itertools import count
def find_ab(tup,target):
for idx in count(start=1, step=2):
try:
if tup[idx] == target[0]:
if tup[idx+1] == target[1]:
return idx
elif tup[idx] == target[1]:
if tup[idx-1] == target[0]:
return idx-1
except IndexError:
break
结果
In [109]: %timeit findPairwise(x0,target)
The slowest run took 8.66 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.27 µs per loop
In [110]: %timeit find_ab(x0,target)
The slowest run took 5.49 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 2.04 µs per loop
In [111]: %timeit findPairwise(x1,target)
The slowest run took 4.75 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 1.46 µs per loop
In [112]: %timeit find_ab(x1,target)
The slowest run took 5.04 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 1.99 µs per loop
In [113]: %timeit findPairwise(x2,target)
The slowest run took 4.66 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 2.56 µs per loop
In [114]: %timeit find_ab(x2,target)
The slowest run took 5.89 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 4.25 µs per loop
In [115]: %timeit findPairwise(x3,target)
The slowest run took 8.59 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.28 µs per loop
In [116]: %timeit find_ab(x3,target)
The slowest run took 6.66 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.65 µs per loop
In [151]: %timeit findPairwise(x4,target)
The slowest run took 5.46 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.27 µs per loop
In [152]: %timeit find_ab(x4,target)
The slowest run took 6.21 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 1.92 µs per loop
In [153]: %timeit findPairwise(x5,target)
1000 loops, best of 3: 325 µs per loop
In [154]: %timeit find_ab(x5,target)
The slowest run took 4.35 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 3.45 µs per loop
如果您在相同的输入中重复搜索不同的目标，您可以通过创建所有唯一字符串的位置的散列来避免每次循环输入，如下面的代码所示。对于初始设置，这需要通过每个输入进行一次循环，但随后搜索几乎是瞬时的（无循环）。
# store first occurrence of each unique 2-char string (O(n))
x1_first = dict()
target_len = 2
for i in range(len(x1)):
x1_first.setdefault(x1[i:i+target_len], i)
# find first occurrence of a particular string without looping (O(1))
print x1_first.get(('a', 'b'), None)
注意：这与@MSeifert 的回答之一非常相似，但展示了如何处理任意目标长度。如果你有多个目标长度需要担心，那么你需要为每个长度创建单独的字典，这对于存储来说是低效的。在这种情况下，您可能会更好地创建最长可能目标（例如 10 个字符）的排序列表，然后使用二分法搜索它（请参阅 bisect 模块）。对于较短的子字符串，您需要扫描多个匹配项并取出最早的一个。