如何高效根据索引从Python的两个关联字典中获取目标对象？

核心思路 #

避免构建全量二维矩阵，通过预计算前缀和边界+二分查找快速定位目标标签，再计算对应标签内的局部索引。这种方法查询时间复杂度为O(log n)（n为标签数量），仅需O(n)的预计算时间与空间，远优于全量矩阵方案的空间开销。

具体步骤 #

1. 预计算前缀和边界：将dict_count转换为有序的标签-累计总数列表，比如原{1:400,2:300,3:200,4:100}会转为[(1, 400), (2, 700), (3, 900), (4, 1000)]，每个元素的第二个值是当前标签及之前所有标签的对象总数。
2. 二分查找定位标签：给定全局索引，找到第一个累计值大于该索引的标签，即为目标标签。
3. 计算局部索引：用全局索引减去前一个标签的累计总数（若为第一个标签则直接使用全局索引），得到目标对象在dict_object对应标签列表中的位置。

代码实现 #

import bisect

# 示例数据
dict_count = {1: 400, 2: 300, 3: 200, 4: 100}
dict_object = {
    1: [f"obj_1_{i}" for i in range(400)],
    2: [f"obj_2_{i}" for i in range(300)],
    3: [f"obj_3_{i}" for i in range(200)],
    4: [f"obj_4_{i}" for i in range(100)],
}

# 预计算前缀和边界（若原字典标签无序，需先执行sorted(dict_count.items())）
prefix_bounds = []
current_total = 0
for label, count in dict_count.items():
    current_total += count
    prefix_bounds.append((label, current_total))
cumulative_counts = [bound[1] for bound in prefix_bounds]

def get_object_by_global_index(index):
    pos = bisect.bisect_right(cumulative_counts, index)
    target_label = prefix_bounds[pos][0]
    local_index = index if pos == 0 else index - prefix_bounds[pos-1][1]
    return dict_object[target_label][local_index]

# 测试示例：索引450
print(get_object_by_global_index(450))  # 输出 obj_2_50

注意事项 #

• 若dict_count的标签无序，必须先对标签排序再计算前缀和，否则索引映射会出错。
• 预计算仅需执行一次，后续所有查询均为O(log n)的高效操作，适合频繁查询的场景。
• 该方案空间开销极小，尤其适合对象总数极大、无法存储全量矩阵的场景。

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