6

给定目标('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。

4

15 回答 15

13

最快的通用搜索算法将具有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)查找（用于哈希查找或其他只需要在一些“桶”中搜索的搜索问题）

您通常可以利用有关数据的任何结构或知识来减少需要处理的项目数量。问题主要在于（可能）没有这些数据结构已经存在，并且自制实现通常最终比天真的“处理所有元素”方法慢几个数量级。但是，如果您有任何关于您的序列的元信息，那么您可以利用它。

最后的评论

pairwise 的配方实际上非常好，但你也可以使用1。最后我检查了一下，它比食谱快了大约 1.5 到 2 倍。即使您不改变方法并接受在最坏的情况下需要处理所有（或几乎所有）元素，它也可能更快！iteration_utilities.successive

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

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

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

就个人而言，我会简单地使用你原来的方法。或者，如果我必须找到几对，那么我只需创建我之前提到的字典（甚至可能对其进行序列化）并在其中进行查找。

赏金原因明确需要“可信和/或官方来源”。幸运的是，“搜索算法”得到了很好的研究，因此您可以在有关算法的基本教科书中找到每种上述方法的解释。例如：

在 python wiki 中还有一个关于 python 类型时间复杂度的小概述：“TimeComplexity”。对于查找，您必须检查“获取项目”或“输入”。

1披露：我是该第 3 方库的作者。

于 2017-05-07T23:10:16.327 回答
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
于 2017-05-05T09:43:05.720 回答
1

也许例如使用正则表达式？您可以在下面找到两个功能。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
于 2017-05-03T22:25:14.163 回答
1

有更短的公式，但没有办法完全避免循环。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 上，在 Python 2.7 上使用 itertools.izip 而不是 zip。

加快速度的主要方法是使用该multiprocessing库。如果您有大量输入要处理，您可以使用multiprocessing.Pool.map循环方式将每个输入发送给不同的工作人员。如果您只有几个输入并且每个输入都很长，那么您可能希望使用 itertools.islice 将它们分成较长的块，然后将每个块发送multiprocessing.Pool.map到您得到命中；然后你可以开始处理下一个输入。我无法从您的问题中判断出哪种方法最有效。

于 2017-05-03T22:51:54.890 回答
0

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

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)
于 2017-05-05T10:03:50.290 回答
0

正如已经指出的那样，您无法避免循环遍历所有字符。您可以使它变得惰性，并且只在输入元组上迭代一次，如下所示（假设 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)
于 2017-05-05T11:06:10.737 回答
0

使用 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

编辑：zip在 python3 中使用

于 2017-04-26T09:44:05.733 回答
0

问题的答案是不，没有任何方法可以在不循环所有字符的情况下找到对。因为如果你不看一个角色，你不知道它是否与你的一对匹配。

您可以通过将迭代隐含在语言或库例程中来隐藏迭代，但它必须存在。使其隐含可能会使代码更高效（例如，如果您将循环移出 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 并置于公共领域）。

于 2017-04-26T09:37:12.450 回答
0

target此解决方案使用列表的方法查找第一个元素index。然后它检查列表中的下一项是否与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
于 2017-05-05T18:26:26.967 回答
0

解决方案：

在构建成对的序列数组后，您可以使用 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]
于 2017-05-08T04:31:04.023 回答
0

我试图对 MSeifert 的方法和我的方法进行基准测试。我的代码源自 MSeifert 的代码，但试图进一步发展，即跳到下一个目标词，而不是一次走两步。顺便说一句，我的通常更快，并且不需要任何包。如果有人有任何问题或意见，请告诉我。谢谢你。

2017 年 5 月 9日编辑：
为了回应 @Matthias Fripp 的评论，我添加了 10k 和 100k 元素的测试元组。对于 10k 元素，我的仍然更快，但不是 100k 元素。因此，我的代码不是最优的。我认为我的方法也不是@MSeifert 指出的“正确”答案，因为最初的问题询问了不搜索所有元素的方法。

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
于 2017-05-09T01:20:55.120 回答
0

这不实用，但可以解决您的问题

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]
于 2017-05-05T05:53:29.417 回答
0

正如 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)。

于 2017-05-04T23:35:04.387 回答
0

如果您在相同的输入中重复搜索不同的目标，您可以通过创建所有唯一字符串的位置的哈希来避免每次循环输入，如下面的代码。这需要一个循环遍历每个输入以进行初始设置，但是搜索几乎是瞬时的（没有循环）。

# 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 模块）。对于较短的子字符串，您需要扫描多个匹配项并取出最早的匹配项。

于 2017-05-09T09:13:01.843 回答
0

如果对数据的性质没有任何承诺（即假设它是随机的），搜索不会比 O(n) 更好。充其量，您可以通过使用您正在尝试做的特定信息优化问题，包括：目标的大小，重复字符目标（搜索 'b' 'b' 'a' 我们可以查看所有其他字符并知道它必须是 'b' 以匹配我们的序列，然后查看周围的字符）或我们可以通过 a 获得的任何其他信息对较小的数据集进行快速分析（再次假设序列表是未知量）。例如，我调查过的一件事是，通过迭代目标的长度并确定它是否是我们正在搜索的字符之一来搜索目标。当然，这样做的问题是不是搜索列表中的每个索引（我们现在触摸 len(list)/len(target) 元素），我们现在对我们触摸的每个元素执行更多操作（换句话说，对于 'b ', 'a' 我们搜索每两个元素，但我们寻找两个东西）。这在减少操作数量方面没有任何作用，但是，假设您计划以相当大的序列查找目标并且这就是为什么您避免循环遍历每个元素。如果提高效率是您的唯一目标，您还可以通过多种方式使用多并行性来提高搜索效率。（如果您选择这条路线，请记住使用多处理而不是线程，因为 python 的线程模块仅支持并发，而不是由于解释器瓶颈线程而导致的多并行）。

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

于 2017-05-05T21:38:38.490 回答