Julia中基于阈值高效比对超大规模列表的最优方案

问题背景 #

需要比对200多万个各包含3136个元素的列表（由下三角矩阵向量化并排序得到），通过**近似相等（atol=0.0001）**的规则去重。当前双重循环逐元素比对的实现耗时极长，集合方法因近似值无法直接使用。

当前低效实现 #

function compare_matrices(connectivity_list, configuration_list)
    i = 1
    while i <= size(connectivity_list, 1)
        x = connectivity_list[i]
        j = i + 1
        while j <= size(connectivity_list, 1)
            if all(isapprox(x[k], connectivity_list[j][k] ; atol = 0.0001) for k=1:1540)
                    deleteat!(connectivity_list, j)
                    deleteat!(configuration_list, j)
            else
                j += 1
            end
        end
        i += 1
    end
    return configuration_list
end

优化方案 #

核心思路是先通过近似特征预分组，再在组内做精确比对，将O(n²)的复杂度大幅降低，同时避免原地删除的性能损耗。

1. 生成近似特征键 #

将每个元素按atol缩放取整，把近似相等的元素映射为相同整数，用这些整数组成的元组作为分组键（元组比数组更适合作为字典键，哈希和查找更快）：

function approx_key(v; atol=0.0001)
    scale = 1 / atol
    # 缩放后取整，转成元组作为字典键
    return Tuple(round.(Int, v .* scale))
end

2. 分组后精确去重 #

用字典按近似键分组，每组内只保留与已保留元素不近似相等的项，最后收集结果：

function deduplicate_lists(connectivity_list, configuration_list; atol=0.0001)
    # 按近似键分组
    groups = Dict{Tuple{Vararg{Int}}, Vector{Tuple{Vector{Float64}, Any}}}()
    for (conn, conf) in zip(connectivity_list, configuration_list)
        key = approx_key(conn, atol=atol)
        push!(get!(groups, key, []), (conn, conf))
    end

    # 组内精确比对去重
    result_conf = []
    sizehint!(result_conf, length(configuration_list))  # 预分配内存提升性能

    for group in values(groups)
        kept_conns = []
        for (conn, conf) in group
            # 利用Julia数组级别的isapprox做向量化比对
            is_duplicate = any(c -> isapprox(conn, c; atol=atol), kept_conns)
            if !is_duplicate
                push!(kept_conns, conn)
                push!(result_conf, conf)
            end
        end
    end

    return result_conf
end

3. 额外性能优化建议 #

• 预分配内存：用sizehint!提前为结果数组分配足够空间，避免频繁扩容
• 利用排序特性：由于列表已经过排序，可优化比对逻辑（比如提前终止比对：如果当前元素与已保留列表的对应元素差距超过atol，直接跳过后续元素）
• 矩阵化处理：若内存允许，将connectivity_list转换为二维矩阵（每行一个列表），用向量化操作批量生成近似键，进一步提升效率：

  # 转换为矩阵（每行对应一个列表）
  conn_matrix = reduce(hcat, connectivity_list)'
  # 批量生成近似键元组
  scale = 1 / atol
  approx_keys = [Tuple(row) for row in eachrow(round.(Int, conn_matrix .* scale))]
  

为什么比原方法高效 #

• 避免全局O(n²)比对：通过近似键分组后，仅在小规模组内做精确比对，时间复杂度大幅降低
• 消除原地删除开销：原方法中deleteat!每次删除元素都需要移动后续元素，O(n)的操作重复百万次会产生巨大开销；新方法直接收集保留项，无此损耗
• 向量化比对：用数组级别的isapprox代替逐元素循环，充分利用Julia的编译优化和SIMD指令

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