Python Lambda字典非精确匹配查询超时，求优化方案

针对你在Python Lambda中遇到的大字典前缀匹配超时问题，核心原因是每次循环都全量遍历字典，时间复杂度为O(m*n)（m是循环次数，n是字典大小），以下是两种更高效的优化方案：

方案一：排序+二分查找（bisect模块） #

通过提前排序字典键，利用二分查找快速定位前缀匹配的范围，避免全量遍历：

实现步骤 #

1. 预处理（仅执行一次，放在循环外）：提取字典的所有键并排序
2. 循环内查询：通过二分查找确定前缀的起始和结束位置，直接切片获取匹配键

import bisect

# 预处理：只执行一次，放在循环外部
sorted_security_keys = sorted(security_dict.keys())

for security_data_item in security_list_per_prefix_raw_m:
    unique_id = security_data_item.get_investment_vehicle_id()
    # 构造前缀的上界（Unicode最大字符\uffff确保所有前缀匹配的键都小于等于该值）
    prefix_upper_bound = unique_id + '\uffff'
    
    # 二分查找定位范围
    start_idx = bisect.bisect_left(sorted_security_keys, unique_id)
    end_idx = bisect.bisect_right(sorted_security_keys, prefix_upper_bound)
    
    # 获取所有匹配的键
    matched_keys = sorted_security_keys[start_idx:end_idx]
    # 如需对应值，直接从字典中提取
    ext_security_values = [security_dict[key] for key in matched_keys]

优势 #

• 预处理时间O(n log n)，后续每次查询仅O(log n + k)（k为匹配键的数量），比全量遍历效率提升显著
• 实现简单，无需额外数据结构依赖

方案二：前缀树（Trie） #

构建前缀树存储所有键，查询时直接遍历前缀对应的路径即可获取所有匹配键，适合频繁进行前缀查询的场景：

实现步骤 #

1. 定义前缀树节点和树结构
2. 预处理（仅执行一次）：将所有字典键插入前缀树
3. 循环内查询：通过前缀树快速获取匹配键

class TrieNode:
    def __init__(self):
        self.children = {}
        self.matched_keys = []  # 存储以当前前缀开头的所有键

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, key):
        node = self.root
        for char in key:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.matched_keys.append(key)
    
    def get_prefix_matches(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        return node.matched_keys

# 预处理：插入所有字典键
security_trie = Trie()
for key in security_dict.keys():
    security_trie.insert(key)

# 循环内查询
for security_data_item in security_list_per_prefix_raw_m:
    unique_id = security_data_item.get_investment_vehicle_id()
    matched_keys = security_trie.get_prefix_matches(unique_id)
    ext_security_values = [security_dict[key] for key in matched_keys]

优势 #

• 查询时间仅与前缀长度相关（O(k + m)，k为前缀长度，m为匹配键数量），适合键长度较短、查询频率极高的场景

原代码问题分析 #

你之前的两种实现：

• filter + dict 方案额外做了字典转换，存在不必要的性能开销
• 列表推导式方案每次循环都全量遍历字典，在大字典+多次循环的场景下会累积大量耗时

此外，如果Lambda的内存配置过低，也可能加剧超时问题，可以适当提升Lambda的内存配额（内存提升会同时提升CPU性能）。

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