基于排序arr_1匹配arr_2元素构建字典的高效方法问询

针对你提到的40亿级数组的分组需求，原方案因重复遍历全数组导致效率极低，利用arr_1已排序的特性，可以通过一次分割实现分组，将时间复杂度从O(N*K)降至O(N)（N为数组长度，K为唯一元素数量），大幅缩短耗时。

核心思路 #

已排序数组的相同元素必然连续，只需找到元素发生变化的边界位置，就能直接确定每个唯一元素对应的arr_2切片范围，无需对每个唯一元素单独扫描全数组。

代码实现 #

import numpy as np

# 示例输入（实际可替换为40亿级的numpy数组或内存映射文件）
arr_1 = np.array([1,1,1,2,2,3])
arr_2 = np.array([16,11,12,13,14,15])

# 1. 找到数组中元素变化的边界索引
split_indices = np.where(np.diff(arr_1) != 0)[0] + 1
# 2. 补全首尾边界，形成完整的分组区间
split_points = np.concatenate([[0], split_indices, [len(arr_1)]])
# 3. 获取每个分组的唯一键（取每个区间的第一个元素）
unique_keys = arr_1[split_points[:-1]]
# 4. 遍历区间构建目标字典
target_dict = {}
for key, start, end in zip(unique_keys, split_points[:-1], split_points[1:]):
    target_dict[key] = arr_2[start:end].tolist()

print(target_dict)
# 输出: {1: [16, 11, 12], 2: [13, 14], 3: [15]}

优化说明 #

• 避免重复扫描：仅通过一次np.diff和np.where完成边界定位，无需对每个唯一元素执行全数组匹配。
• 内存友好：若数组过大无法加载到内存，可使用np.memmap将数组映射到磁盘文件，上述代码无需修改即可直接运行（切片操作仅读取对应磁盘区域）。
• 时间效率：对于40亿级数组，该方案的耗时主要集中在np.diff和切片转列表的操作，远低于原方案的多次全数组扫描。

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