寻找成对元素的索引

Question

考虑目标('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在评论中的问题：x*都是字符串元组列表。因此它们可以通过索引访问。但如果答案/解决方案适用于元组和生成器，那就太好了！你能说出你要搜索多少个列表以及它们有多长吗？这将有助于建议搜索策略。元组的长度并不固定。它们可以是大小> 2的元组。

- alvas

---

如果ab在"".join(x0)中？ - Liam

你的意思是，“不用遍历所有元素”？那么你肯定至少需要查看每个元素一次才能确定该元组不在列表中。（你可能会争辩说只需要查看每2个元素，但那样你就必须将其与元组中的两个元素都进行比较，对吗？） - tobias_k

@alvas 我认为即使你使用字典以常数时间访问一对元素也是不可能的。你仍然需要遍历一次来构建。 - Ozgur Vatansever

你不需要try-except子句，return next((i for i, pair in enumerate(pairwise(x)) if pair == target), None)。 - Chris_Rands

@alvas 你能在问题中概念性地解释一下，如果没有显式或隐式循环，你希望这个问题如何可能实现吗？ - Chris_Rands

Answer 1

最快的通用搜索算法将具有O(n)的平均性能（称为线性搜索），这意味着您没有选择（除了可能是一个常数因子）而必须处理每个元素。

鉴于您的问题：

是否有一种方法可以在不循环所有字符的情况下找到成对元素的索引？

那是可能的（尽管仍然是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

然而，如果你只想搜索一个对，那么这种方法会慢得多，因为你失去了“短路行为”（一旦找到匹配项就停止），并且在创建字典时处理所有元素。

其他方法：

- O(n)线性搜索 - O(log(n))二分搜索（用于排序数据） - O(1)查找（用于可哈希查找或其他只需要在某些“桶”中搜索的搜索问题）

你通常可以利用任何关于数据的结构或知识来减少需要处理的项目数量。问题主要是没有现成的数据结构可用，自制实现往往比朴素的“处理所有元素”的方法慢几个数量级。但如果你有关于序列的任何元信息，那么你可以利用它。

最后的备注。

配对的方法其实非常好，但你也可以使用iteration_utilities.successive¹。据我所知，它的速度大约是该方法的1.5到2倍。即使你不改变方法并接受在最坏情况下需要处理所有（或几乎所有）元素，它也可能更快！

那些数据很可能是生成的。也许在创建过程中实际“搜索”元素是值得的。这样，你根本不需要额外地遍历数据。或者在创建数据集时创建dict（这允许之后进行O(1)查找）。有时候看看生成/下载/提取数据集的过程是否有办法提取信息是一个好主意。

现在，在写完所有这些文字之后，我需要说明一下显而易见的事情：

你的方法非常好。即使在最坏情况下需要处理所有元素，它也使用了一个完美适合问题的成对配方，并且即使在输入很长的情况下，它应该也能够非常快速地工作。例如，对于包含 1 百万个 'z' 的元组，在我的电脑上只需要 200 毫秒。因此，您可以每秒处理数百万个元素（即使在像我这样的旧而慢的计算机上）。这对于大数据可能还不够快，但是纯 Python 不是处理大数据的好语言（通常您需要编写 C 扩展、使用 Cython 或某些 NumPy、Pandas 或衍生方法）。此外，生成器上的 next 函数是惰性的（假设您在 Python2 上使用 itertools.izip 而不是 zip），因此您只处理每个元组，直到找到匹配项。

就个人而言，我会直接使用您最初的方法。或者，如果我必须找到多个配对，那么我会创建我之前提到的字典（甚至可能序列化它），并在其中进行查找。

---

The bounty reason explicitly requires "credible and/or official sources". Fortunately, "search algorithms" have been well studied, so you can find explanations for each of the mentioned approaches in basic textbooks on algorithms. For example:

• Cormen, et. al - Introduction to Algorithms

• Sedgewick & Wayne - Algorithms

• Wikipedia: "Linear search"

• Wikipedia: "Binary search"
• Wikipedia: "Hashtable" (that's essentially a dict).

There's also a small overview of time complexities of Python types in the Python wiki: "TimeComplexity". For lookups, you have to check "Get Item" or "in".

---

¹声明：我是那个第三方库的作者。

- MSeifert

Answer 2

虽然在您的情况下它的效果不是很惊人，请查看。

我们只是从样本中提取匹配项的索引，然后检查它是否连续。

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

- DexJ

---

我没有点踩，但是 tuple.index 方法只会返回第一个匹配项，所以如果第一个匹配项不匹配，你将找不到匹配项：consecutive_index(('a', 'b', 'z', 'b', 'a'), ('b', 'a')) 返回 None（但在索引 4 处有匹配项）。问题中没有提到元组中的任何“结构”，所以我不确定您的方法是否正确。此外，如果 a 不在 src 中，则 if a in src 将处理 src 的所有元素，因此它并没有完全解决问题的“不循环遍历所有字符”的部分。 - MSeifert

Answer 3

也许可以使用正则表达式来实现？下面是两个函数。findPair将返回与您的示例完全相同的值。findPairs将查找所有非重叠的出现，并在列表中返回它们的起始位置。

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

- machnic

---

str.join(), str.find() 和正则表达式仍然会迭代。将其转换为字符串之前进行大量的工作，而OP已经以合理高效的方式解决了这个问题。 - Martijn Pieters

Answer 4

有更短的公式可以实现，但无法完全避免循环。然而，您可以通过 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而不是zip。

加速的主要方法是使用multiprocessing库。如果您有大量输入需要处理，则可以使用multiprocessing.Pool.map将每个输入按循环方式发送到不同的工作进程中。如果您只有少量输入，并且每个输入都非常长，则可能需要使用itertools.islice将它们分成较长的块，然后将每个块发送到multiprocessing.Pool.map，直到找到匹配项为止；然后您可以开始处理下一个输入。从您的问题中无法确定哪种方法最有效。

- Matthias Fripp

Answer 5

假设数据是随机的情况下，搜索时间复杂度不能优于O(n)。最好的情况就是利用具体信息来优化问题，比如目标的大小、目标中重复字符（例如搜索'b' 'b' 'a'时，我们可以查看其他字符并确定它们一定是'b'以匹配我们的序列，然后查看周围字符），或者通过对较小数据集进行快速分析获得的任何其他信息（同样假设序列列表是未知的）。例如，我曾经尝试过通过迭代目标长度来查找目标，并确定它是否是我们正在搜索的字符之一。当然，这种方法的问题在于，我们不再搜索列表中的每个索引（现在我们仅接触len(list)/len(target)个元素），而是在接触到每个元素时执行更多的操作（换句话说，对于'b'，'a'，我们搜索每两个元素，但我们要寻找两个东西）。这在减少操作次数方面没有任何作用，但如果你打算在相当大的序列中寻找目标并且这就是你为什么避免循环遍历每个元素的原因，它将显著减少你需要从二级存储器读取的元素数量。如果增加效率是你唯一的目标，还可以使用多重并行处理来增加搜索效率。 （请记住使用多进程而不是线程，因为Python的线程模块仅支持并发而不支持多重并行处理，由于解释器限制了线程的数量）。

作为结论并直接回答您提出的问题，是完全可能在不查看序列中的每个元素的情况下找到成对元素的索引。然而，这样做需要首先查看与手头问题相关的特定信息，然后将此信息应用于搜索。我认为最好的方法是通过首先分析数据，然后执行最适合该输入的搜索方法来进行搜索。换句话说，如果有重复项，则可以使用它，但如果没有，则可以退回到另一种搜索方法。

- zlmonroe

Answer 6

正如nigel222所指出的那样，在最坏的情况下，你无法避免遍历整个列表，因为你必须进行详尽的比较，以确保你想要的项不包含在你的可迭代对象中。

如果你将在各种可能的子序列上进行大量这些查询，那么将其压缩成一个集合可能是值得的，因为集合具有O(1)的查找。

...
my_pairwise = set(pairwise(x))
found_subsequences = [subsequence
                      for subsequence in collection_of_subsequences
                      if subsequence in my_pairwise]

通过这种方式，只需一次 O(n) 的迭代通过您的 x，之后每次查找的复杂度都是 O(1)。

- Patrick Rhomberg

Answer 7

这不是很实际，但它可以解决你的问题。

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]

- Tim S.

Answer 8

你可以通过将列表转换为字符串来实现。

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)

- Somil

Answer 9

正如已经指出的那样，您无法避免循环遍历所有字符。您可以使其变得懒惰，并仅迭代一次输入元组，如下所示（假设使用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)

- Alicia Garcia-Raboso

---

切片 x[1：] 不是惰性的，它需要 x 是一个列表或元组。如果 x 是一个值过多以至于无法一次性全部放入内存的迭代器，则无法使用该方法。提问者使用的“pairwise”配方更好。 - Blckknght

Answer 10

这个解决方案使用列表的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

- Brad Campbell