Python：字典嵌套列表中子列表的高效查找优化方案

你的核心问题在于每次搜索关键词时都要线性遍历整个字典的键来匹配子串，这种方式在数据规模较大时会导致显著的性能损耗。下面是针对性的优化方案：

核心优化思路：预构建倒排索引 #

提前把数据项中的所有可搜索关键词和对应的索引关联起来，形成一个反向映射表。后续搜索时直接通过关键词查表，无需遍历整个字典，将单次搜索的时间复杂度从O(n)降到O(1)级别。

优化后的完整代码 #

from collections import defaultdict
from bisect import bisect_left

def build_inverted_index(data_list):
    """构建倒排索引：关键词 -> 对应的索引列表"""
    inverted_index = defaultdict(list)
    for idx, item in enumerate(data_list):
        # 拆分数据项中的关键词（根据你的数据格式调整拆分逻辑）
        # 示例格式："7:dog, puppy" -> 提取出"dog"、"puppy"
        _, keywords_part = item.split(":", 1)
        keywords = [kw.strip() for kw in keywords_part.split(",")]
        for kw in keywords:
            inverted_index[kw].append(idx + 1)  # 保持和原代码一致的索引从1开始
    return inverted_index

def getsublist_optimized(firstArr, secondArr):
    # 预构建倒排索引
    inverted_index = build_inverted_index(firstArr)
    
    tempArr = []
    for keyword in secondArr:
        # 直接通过倒排索引获取匹配的索引，无需遍历整个字典
        matched_indices = inverted_index.get(keyword, [])
        if matched_indices:
            print(f'Match found for: {keyword}')
            tempArr.extend(matched_indices)
    
    # 原代码中的LIS逻辑保持不变
    tail = []
    if tempArr:
        tail.append(tempArr[0])
        for num in tempArr[1:]:
            if num > tail[-1]:
                tail.append(num)
            elif num < tail[0]:
                tail.insert(0, num)
            else:
                it = bisect_left(tail, num)
                tail.insert(it, num)
    else:
        print('Did not find a match')                
    
    return tail

# 测试数据
keyword_list = ['men', 'boy', 'dog']
db_data={'male':['1:man', '2:men'], 'child':['3:boy','4:lad', '5:girl'], 'animal':['6:cat','7:dog, puppy']}

output = defaultdict(list)
for key, value in db_data.items():
    print(f'\nchecking in: {value}\n ')
    # 去掉冗余的numpy操作，直接使用原列表
    result = getsublist_optimized(value, keyword_list)
    print(f'Result: {result}')
    for x in result:
        output[key].append(value[x-1])

print(output)

关键优化点说明 #

1. 倒排索引构建：

   • 针对你的数据格式（编号:关键词1,关键词2），提前拆分每个数据项中的关键词，将每个关键词映射到对应的索引位置。
   • 后续搜索时直接通过关键词查询索引，避免了原代码中遍历整个字典的线性操作。

2. 移除冗余操作：

   • 原代码中使用numpy数组处理列表完全是多余的，直接使用原列表即可，减少了不必要的内存开销和数据转换时间。

3. 保持原有逻辑兼容：

   • 保留了你原代码中最长递增子序列（LIS）的处理逻辑，确保输出结果和原代码一致。

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