1

我有一个包含很多bool值的列表，我想得到这个模式：True, True, False, True, True. 为此，我认为我需要在处理我的前一个元素时循环获取下一个元素。我该怎么做？

额外的问题：有没有办法增加列表中元素的位置而不是i += 1事物？

4

4 回答 4

2

我会尝试一下：

subset = [True, True, False, True, True]
main = [False, True, False, True, True, True, False, True, True, False, True, False, True]

for i, j in  enumerate(xrange(len(subset), len(main) + 1)):
    if main[i:j] == subset:
        print subset, 'is at', i
        break
else:
    print 'not found'

注意：这有点粗暴，但一次性还可以……否则，看看尝试……

于 2012-11-01T23:12:36.133 回答
1 
l = len(some_list) - 3
for i, thing in enumerate(some_list):
    if i == l: break
    if thing and some_list[i+1] and not some_list[i+2] and some_list[i+3]:
        bingo(i)

另一个未经测试的尝试：

needle = [True, True, False, True, True]
needle_len = len(needle)
for i in range(len(stack)-needle_len+1):
    if needle == stack[i:i+needle_len]:
        bingo(i)
于 2012-11-01T22:50:49.317 回答
1

如果我正确理解了这个问题，那么您尝试做的事情与 完全相同str.find，但是在列表中查找子列表而不是字符串中的子字符串。

如果是这样：

def findSubList(l, sub):
  return (''.join('T' if x else 'F' for x in l)
          .find(''.join('T' if x else 'F' for x in sub)))

这可能看起来很 hacky，但它是有道理的：你想在一个列表中找到一个子列表，两者都可以简单地转换为字符串，并且已经有一个内置函数可以在字符串中找到一个子字符串，所以为什么不使用吗？

结果可能太慢了，但实际上，编写它的速度非常快，值得对其进行测试，看看它是否对您的目的来说太慢了。（即使它太慢了，也可能是转换为字符串的部分很慢，首先使用字符串而不是布尔列表可能是合理的，或者在开始进行 200 次搜索之前转换一次， 管他呢。）

如果这不可避免地太慢了，我接下来要做的是查看实现str.find并将其转换为通用序列查找。你已经有了 Python 的源代码，所以这应该不会太难。但是，它可能str.find在 C 中，移植起来可能会很痛苦。在这种情况下，您可能仍想在线搜索纯 Python str.find……但假设您没有找到。

下一步是查看 PyPI 上是否有序列查找模块。

如果没有，有一些众所周知的算法要么易于实现，要么在 ActiveState 甚至 Wikipedia 等地方免费实现。有关列表和一些比较，请参阅Wikipedia 上的字符串搜索算法。（性能特征取决于您没有提供给我们的因素——您需要进行多少次搜索；主要、子集或两者都不同；等等，这意味着没有更多信息，没有人能猜出哪个是最好的。）

甚至标准的字符串搜索算法也可能不够快，并且利用您搜索单个位而不是 8 位字符的事实可以获得主要的效率提升。（如果模式是固定的，您甚至应该能够将搜索描述为有限状态机，并将其转换为硬编码、可证明的最佳实现……）

因此，您可能必须自己设计一些东西。但你不太可能这样做，如果可能的话，我会避免这样做。每当你遇到一个明显常见的问题时，值得假设它是一个已解决的问题并寻找解决方案，而不是试图从第一原则解决它。

于 2012-11-01T23:22:33.570 回答
0

相当有效，使用滑动窗口方法，应该以线性时间运行。 

def find_x_in_y(subset, main):
    """ Returns a list of the indexes of the first value of matches. """
    results = []
    for i in xrange(len(main)):
        if main[i:i+5] == subset:
              results.append(i)
    return results

# values borrowed from @JonClements
subset = [True, True, False, True, True]
main = [False, True, False, True, True, True, False, True, True, False, True, False, True]

>>> find_x_in_y(subset, main)
... [4]

@abarnert 很好，这是一种实际上非常有效的方法。

效率极高，将整个布尔列表转换为位数组并运行本机搜索方法。 

from bitarray import bitarray

def find_x_in_y(subset, main):
    subarray = bitarray(subset)
    mainarray = bitarray(main)
    return [int(i) for i in mainarray.itersearch(subarray)]

timeit结果：

Length of main:                     10      100     1000    10000   100000   1000000

returning _all_ matches:
# number of matches                  1       10      100     1000    10000    100000
# sliding window approach     (0.00059, 0.00502, 0.04194, 0.26211, 2.55554, 26.21962)
# bitarray approach           (0.00028, 0.00072, 0.00484, 0.02926, 0.2822,   2.93676)

returning first match:
# sliding window approach     (0.00034, 0.00034, 0.00034, 0.00021, 0.00026,  0.00059)
# bitarray approach           (0.00017, 0.00017, 0.00016, 0.00011, 0.00014,  0.00049)
# joined string approach      (0.00134, 0.00721, 0.06244, 0.39224, 4.21628, 39.63207)
于 2012-11-01T23:23:57.943 回答