寻找成对元素的索引

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.

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))操作 - 这不仅会处理每个项目一次,而是会多次处理其中一些项目.并不是说我知道一种合理的方法来对相邻元素进行排序.

桶搜索(或哈希表)

你有元组所以创建一个哈希表(a 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) 查找(用于可清除的查找或其他搜索问题,只需要在某些"桶"中搜索)

您通常可以利用有关数据的任何结构或知识来减少需要处理的项目数量.问题主要在于(可能)没有已经存在的数据结构,而且自制的实现通常比天真的"处理所有元素"方法慢几个数量级.但是,如果您有关于序列的任何元信息,那么您可以利用它.

最后的评论

成对的配方实际上相当不错,但你也可以使用¹.最后我检查它比食谱大约快1.5到2倍.即使您不改变方法并接受在最坏的情况下需要处理所有(或几乎所有)元素,它可能会更快!iteration_utilities.successive

该数据可能已生成.也许在创作过程中实际"搜索"元素是值得的.这样你根本不需要对数据进行额外的传递.或者您可以dict在创建数据集的同时创建(允许O(1)随后进行查找).如果有某种方式可以提取信息,有时候查看生成/下载/获取数据集的过程是个好主意.

现在,在写完所有这些文字后,我需要说清楚:

你的方法非常好.即使它需要在最坏的情况下处理所有元素,它pairwise也会针对手头的问题使用完美的拟合(-recipe),即使对于长输入也应该非常快.对于包含100万的元组'z',我的计算机上只需要200ms.因此,您可以每秒处理数百万个元素(即使是像我这样的老式和慢速计算机).对于大数据而言,这可能不够快,但是纯python并不是处理大数据的好语言(通常你需要编写C扩展,使用Cython或一些NumPy,Pandas或衍生方法).此外,next生成器上的函数是惰性的(假设您itertools.izip在python2上使用而不是zip),因此您只需处理每个元组,直到找到匹配项.

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

赏金的理由明确地要求"可信和/或官方来源".对Fortunatly"搜索算法"进行了深入研究,因此您可以在算法的基础教科书中找到每种提到的方法的解释.例如:

• Cormen等.al - 算法简介

• Sedgewick&Wayne - 算法

• 维基百科:"线性搜索"

• 维基百科:"二元搜索"
• 维基百科:"Hashtable"(基本上是一个dict).

还有一个关于python wiki中python类型的时间复杂性的小概述:"TimeComplexity".对于查找,您必须选中"获取项目"或"在"中.

¹披露:我是第三方图书馆的作者.