Python列表模式查找器高效实现方案咨询

针对你遇到的列表重复模式检测问题，尤其是大列表性能瓶颈的困扰，我整理了几个实用思路，兼顾准确性和效率：

一、优化基础模式检测逻辑 #

你的初始思路方向是对的，但仅依赖第一个元素的下一次出现来确定模式长度容易出错（比如遇到元素重复但不是完整模式的场景）。我们可以改进为动态验证候选模式长度：

1. 从列表起始位置开始，遍历所有可能的模式长度（范围是1到当前剩余列表长度的一半，因为至少要重复两次才算有效模式）
2. 对每个候选长度，检查后续子序列是否完全匹配当前模式
3. 找到第一个能连续重复的模式后，统计它的重复次数，跳过这些重复元素，继续处理剩余列表

示例代码：

def find_patterns(lst):
    patterns = []
    i = 0
    n = len(lst)
    while i < n:
        found = False
        # 尝试所有可能的模式长度，从1到剩余长度的一半
        max_len = (n - i) // 2
        for pattern_len in range(1, max_len + 1):
            pattern = lst[i:i+pattern_len]
            # 检查后续是否能连续匹配
            count = 1
            j = i + pattern_len
            while j + pattern_len <= n and lst[j:j+pattern_len] == pattern:
                count +=1
                j += pattern_len
            if count > 1:
                patterns.append([count, pattern])
                i = j  # 跳到当前模式结束的位置
                found = True
                break
        # 若未找到重复模式，跳过当前单个元素（可根据需求调整规则）
        if not found:
            i +=1
    return patterns

# 测试示例
test_lst = [1, 2, 6, 1, 2, 6, 1, 2, 6, 7, 8, 7, 8]
print(find_patterns(test_lst))  # 输出: [[3, [1, 2, 6]], [2, [7, 8]]]

二、滚动哈希（Rabin-Karp算法）加速大列表处理 #

对于超大列表，直接切片比较的时间复杂度太高（O(n²)），滚动哈希可以把子序列比较的时间降到O(1)，整体复杂度接近O(n)：

核心思路是预先计算每个位置的哈希值，通过滚动计算快速得到任意子序列的哈希，再通过哈希值判断子序列是否相等（为避免哈希碰撞，可搭配实际内容二次校验）。

示例代码：

def rabin_karp_hash(lst, base=911382629, mod=10**18+3):
    # 计算前缀哈希和幂次
    n = len(lst)
    prefix_hash = [0]*(n+1)
    power = [1]*(n+1)
    for i in range(n):
        prefix_hash[i+1] = (prefix_hash[i] * base + hash(lst[i])) % mod
        power[i+1] = (power[i] * base) % mod
    
    def get_hash(l, r):
        # 获取lst[l..r-1]的哈希值（左闭右开）
        return (prefix_hash[r] - prefix_hash[l] * power[r - l]) % mod
    
    return get_hash

def find_patterns_fast(lst):
    patterns = []
    n = len(lst)
    if n <2:
        return patterns
    get_hash = rabin_karp_hash(lst)
    i =0
    while i <n:
        max_len = (n -i)//2
        found = False
        for pattern_len in range(1, max_len+1):
            pattern_hash = get_hash(i, i+pattern_len)
            count =1
            j = i + pattern_len
            while j + pattern_len <=n:
                if get_hash(j, j+pattern_len) == pattern_hash:
                    # 哈希匹配后做实际校验，避免碰撞
                    if lst[i:i+pattern_len] == lst[j:j+pattern_len]:
                        count +=1
                        j += pattern_len
                    else:
                        break
                else:
                    break
            if count>1:
                patterns.append([count, lst[i:i+pattern_len]])
                i =j
                found = True
                break
        if not found:
            i +=1
    return patterns

# 测试超大列表
large_lst = [1,2,3]*10000 + [4,5]*5000
print(find_patterns_fast(large_lst))  # 输出: [[10000, [1,2,3]], [5000, [4,5]]]

三、用numpy向量化操作加速数值列表 #

如果你的列表元素是数值类型（整数、浮点数），numpy的向量化运算可以大幅降低Python循环的开销：

import numpy as np

def find_patterns_numpy(arr):
    patterns = []
    n = len(arr)
    i =0
    while i <n:
        max_len = (n -i)//2
        found = False
        for pattern_len in range(1, max_len+1):
            pattern = arr[i:i+pattern_len]
            # 计算能分成多少个完整的块
            num_blocks = (n -i) // pattern_len
            if num_blocks <2:
                continue
            # 把后续元素分块后和模式批量比较
            blocks = arr[i:i+num_blocks*pattern_len].reshape(-1, pattern_len)
            if np.all(blocks == pattern):
                patterns.append([num_blocks, pattern.tolist()])
                i += num_blocks * pattern_len
                found = True
                break
        if not found:
            i +=1
    return patterns

# 测试
test_arr = np.array([1, 2, 6, 1, 2, 6, 1, 2, 6, 7, 8, 7, 8])
print(find_patterns_numpy(test_arr))  # 输出: [[3, [1, 2, 6]], [2, [7, 8]]]

关于输出格式的建议 #

你提到想用字典但担心同模式冲突，推荐使用列表嵌套字典的格式，既清晰又不会冲突：

# 转换为字典格式
result = find_patterns(test_lst)
dict_result = [{"count": cnt, "pattern": pat} for cnt, pat in result]
print(dict_result)
# 输出: [{'count': 3, 'pattern': [1, 2, 6]}, {'count': 2, 'pattern': [7, 8]}]

这样即使相同模式在不同位置出现，也能分别记录它们的重复次数。

内容的提问来源于stack exchange，提问作者Isaac