如何改进Python中列表上的模式匹配

Question

我有一个很大的名单，其中可能有数千到数百万的条目。我设置了一个有限大小的窗口在列表上滑动。我需要在窗口中计数匹配的元素，并通过一次向前滑动窗口1位置来重复这个过程。下面是一个简单的列表示例

L = [1 2 1 3 4 5 1 2 1 2 2 2 3 ]

假设窗口的长度为3，它将捕获

elements

• move

• 1 2 1，其中包含一对匹配元素(1 &1)

• 按1位置=> 2 1 3向前移动窗口，无匹配元素

• 将窗口向前移动1位置=> 1 3 4 4，没有匹配元素

• 将窗口向前移动1位置=> 3 4 5，不匹配元素

H 110按位置=> 4 5 1向前移动窗口，不匹配的

• 按1位置=> 5 1 2向前移动，不按1位置=> 1 21向前移动窗口，1匹配元素(1 &1)

• 按1位置=> 2 1 2移动窗口，1匹配单元(2 &2)

• 按1位置=> 1 2 2移动窗口，1匹配元素(2和2)

• 按1位置=> 2 2 2移动窗口，3匹配单元(2 2 -，2- 2，-2 2)

• 将窗口向前移动1位置=> 2 2 3，1匹配元素(2和2)

G 224

总计1+1+1+1+3+1=8对匹配对。我找到了使用itertools查找窗口中所有元素的组合的想法，并开发了一个代码来查找所有匹配的对。

import itertools
L = [1,2,1,3,4,5,1,2,1,2,2,2,3]
winlen = 3
totalMatch = 0
for n in range(len(L)-winlen+1):
    window = [L[n+i] for i in range(winlen)]
    A = list(itertools.combinations(window, 2))
    match = [a==b for a, b in A]
    totalMatch += sum(match)

它适用于短列表，但是对于列表和窗口越来越大，这段代码太慢了。我已经使用C++多年了，并且决定改用python，如果有任何提高代码效率的提示，我会很感激的。

Answer 1

更有效地跟踪窗口中的数据？这里是O(x=1，2)，而不是你的O({##*}}*winlen^2)。它在ctr中保存窗口的元素计数，在match中保存窗口的匹配。例如，当一个新值进入窗口，并且窗口中已经有该值的两个实例时，您将得到两个新的匹配。类似地，对于从窗口掉出的值，它需要与其匹配的数量与窗口中的其他实例相同。

from collections import Counter

L = [1,2,1,3,4,5,1,2,1,2,2,2,3]
winlen = 3

totalMatch = match = 0
ctr = Counter()
for i, x in enumerate(L):
    
    # Remove old element falling out of window
    if i >= winlen:
        ctr[L[i-winlen]] -= 1
        match -= ctr[L[i-winlen]]

    # Add new element to window
    match += ctr[x]
    ctr[x] += 1

    # Update the total (for complete windows)
    if i >= winlen - 1:
        totalMatch += match

print(totalMatch)

L和winlen的基准结果乘以20：

 38.75 ms  original
  0.18 ms  Manuel

 38.73 ms  original
  0.19 ms  Manuel

 38.87 ms  original
  0.18 ms  Manuel

基准代码(还包括长度从0到9的数字1到3的所有列表的测试代码)：

from timeit import repeat
import itertools
from itertools import product
from collections import Counter

def original(L, winlen):
    totalMatch = 0
    for n in range(len(L)-winlen+1):
        window = [L[n+i] for i in range(winlen)]
        A = list(itertools.combinations(window, 2))
        match = [a==b for a, b in A]
        totalMatch += sum(match)
    return totalMatch

def Manuel(L, winlen):
    totalMatch = match = 0
    ctr = Counter()
    for i, x in enumerate(L):
        if i >= winlen:
            ctr[L[i-winlen]] -= 1
            match -= ctr[L[i-winlen]]
        match += ctr[x]
        ctr[x] += 1
        if i >= winlen - 1:
            totalMatch += match
    return totalMatch

def test():
    for n in range(10):
        print('testing', n)
        for T in product([1, 2, 3], repeat=n):
            L = list(T)
            winlen = 3
            expect = original(L, winlen)
            result = Manuel(L, winlen)
            assert result == expect, (L, expect, result)

def bench():
    L = [1,2,1,3,4,5,1,2,1,2,2,2,3] * 20
    winlen = 3 * 20
    for _ in range(3):
        for func in original, Manuel:
            t = min(repeat(lambda: func(L, winlen), number=1))
            print('%6.2f ms ' % (t * 1e3), func.__name__)
        print()

test()
bench()

Answer 2

您可以在for循环中使用np.bincount，确定每个数字/bin的组合数，并将其与总数相加。

import numpy as np

L = [1, 2, 1, 3, 4, 5, 1, 2, 1, 2, 2, 2, 3]
winlen = 3

L = np.array(L) # convert to array to speed up indexing

total = 0
for i in range(len(L) - winlen + 1):
    bc = np.bincount(L[i:i+winlen]) # bincount on the window
    bc = bc[bc>1] # get rid of all single and empty values
    bc = bc * (bc-1) // 2 # gauss addition, number of combinations of each number
    total += np.sum(bc) # sum up combinations, and add to total

print(total)
# 8