python - 查找成对元素的索引

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的问题:

Are your elements in lists or types (as shown) or in a generator (e.g. reading from a file handle)?

x *都是字符串的元组。因此，它们可以通过索引进行访问。但是，如果答案/解决方案可以用于元组和生成器，那就太好了!

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。

Answer 1

最快的常规搜索算法将具有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

但是，如果您只想搜索一对，则该方法要慢得多，因为您会失去“短路行为”(一旦找到匹配项便会停止)，并且在创建字典时会处理所有元素。

其他方法

除了一般的方法:

O(n)线性搜索

O(log(n))二进制搜索(用于排序的数据)

O(1)查找(用于仅在某些“存储桶”中搜索的可哈希查找或其他搜索问题)

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

结束语

pairwise的食谱实际上非常不错，但是您也可以使用 iteration_utilities.successive 1。最后我检查了它的速度，大约比该食谱快1.5至2倍。即使您不更改方法并接受需要在最坏的情况下处理所有(或几乎所有)元素的方法，它可能也会更快!

该数据可能是生成的。在创建过程中实际“搜索”元素也许是值得的。这样，您根本不需要对数据进行额外的传递。或者，您可以在创建数据集时创建dict(此后可以进行O(1)查找)。有时，如果可以某种方式提取信息，最好查看生成/下载/获取数据集的过程。

现在，在编写完所有这些文本之后，我需要说明显而易见的内容:

您的方法非常好。即使需要在最坏的情况下处理所有元素，它也可以很好地解决当前问题(pairwise -recipe)，并且即使输入很长，它的工作速度也应该非常快。对于包含一百万个'z'的元组，在我的计算机上仅需要200毫秒。因此，您每秒可以处理几百万个元素(即使在像我这样的旧的慢速计算机上)。对于大数据来说，这可能还不够快，但是纯python并不是处理大数据的好语言(通常，您需要编写C扩展名，使用Cython或某些NumPy，Pandas或派生方法)。同样，生成器上的next函数是惰性的(假设您在python2上使用itertools.izip而不是zip)，因此您只处理每个元组，直到找到匹配项为止。

就我个人而言，我只会使用您的原始方法。或者，如果我必须找到几对，那么我将创建前面提到的字典(甚至可以序列化它)并在其中进行查找。

赏金理由明确要求“可信和/或官方消息来源”。幸运的是，已经对“搜索算法”进行了深入研究，因此您可以在有关算法的基础教科书中找到每种提到的方法的解释。例如:

Cormen等。 al-算法简介

Sedgewick和Wayne-算法

维基百科:"Linear search"

维基百科:"Binary search"

维基百科:"Hashtable"(本质上是dict)。

在python Wiki:"TimeComplexity"中，还对python类型的时间复杂性进行了一小部分概述。对于查找，您必须选中“获取项目”或“输入中”。

1披露:我是该第三方图书馆的作者。