如何基于嵌套键值高效检索sortedcontainers.SortedKeyList中的元素

错误原因分析 #

你遇到的TypeError: string indices must be integers, not 'str'，本质是检索时的参数传递错误——要么是你把字典传给了bisect方法，要么是误将排序键的字符串值当成字典去访问键，导致把字符串当作字典操作，触发索引类型错误。

正确实现步骤 #

1. 确认SortedKeyList的初始化 #

首先确保创建SortedKeyList时，正确指定了提取嵌套键token_str的key函数：

from sortedcontainers import SortedKeyList

# 初始化时指定key，按字典的token_str字段排序
self.tokenized_files = SortedKeyList(key=lambda item: item["token_str"])

2. 基于二分查找的高效检索 #

SortedKeyList内置了bisect_left、bisect_right等二分查找方法，直接基于你指定的排序键工作，时间复杂度O(log n)，无需遍历整个列表。

检索单个匹配元素

target_token = "需要查找的token_str值"
# 获取目标token的插入位置（即第一个匹配元素的索引）
idx = self.tokenized_files.bisect_left(target_token)

# 验证索引有效性并确认元素匹配
if idx < len(self.tokenized_files) and self.tokenized_files[idx]["token_str"] == target_token:
    matched_item = self.tokenized_files[idx]
else:
    matched_item = None  # 无匹配元素

检索所有匹配元素（处理重复token_str）

如果存在多个字典的token_str值相同，可通过bisect_left和bisect_right获取匹配区间：

target_token = "需要查找的token_str值"
left_idx = self.tokenized_files.bisect_left(target_token)
right_idx = self.tokenized_files.bisect_right(target_token)

# 区间[left_idx, right_idx)内的所有元素都是匹配项
matched_items = self.tokenized_files[left_idx:right_idx]

关键注意点 #

• 调用bisect方法时，传入的是**token_str的字符串值**，不是字典，这是避免类型错误的核心。
• 必须验证索引对应的元素是否真的匹配，因为bisect_left返回的是插入位置，即使目标不存在也会返回一个合法索引。
• 确保初始化时的key函数正确指向嵌套键token_str，键名拼写错误会导致排序或检索失效。

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