如何高效筛选集合中未被支配的数对？寻求优化方案

问题背景 #

需要从数对列表中筛选出未被其他数对支配的子集（同时去重），支配定义为：存在另一个数对，其两个元素分别≥当前数对对应元素，且至少有一个元素严格大于。原方案使用cross join实现，大数据集下计算量爆炸，需更高效的方法。

示例 #

输入：

(1,2)
(1,5)
(2,2)
(1,2)
(2,2)
(9,1)
(1,1)

输出：

(1,5)
(2,2)
(9,1)

原实现问题 #

原代码通过cross join进行全量两两对比，时间复杂度为O(n²)，当n较大时（如数千甚至上万条数据），计算量会呈指数级增长，无法高效处理。

高效解决方案：帕累托前沿线性扫描算法 #

这个问题本质是寻找帕累托前沿（Pareto Frontier），经典的高效算法通过排序+线性扫描实现，时间复杂度为O(n log n)，仅由排序步骤主导。

算法逻辑 #

1. 去重：先移除重复数对，减少后续计算量。
2. 排序：按数对第一个元素降序、第二个元素降序排序。这样保证：
   • 所有a更大的数对排在前面；
   • 相同a的数对中，b更大的排在前面。
3. 线性扫描：跟踪遍历过程中遇到的最大b值，仅保留b等于当前最大b值的数对——这些数对不会被任何其他数对支配。

Polars实现代码 #

import polars as pl

pairs_list = [
    (1,2),
    (1,5),
    (2,2),
    (1,2),
    (2,2),
    (9,1),
    (1,1),
]

# 转换为DataFrame并去重
df = pl.DataFrame(pairs_list, schema=["a", "b"]).unique()

# 按a降序、b降序排序，确保大a优先，同a下大b优先
sorted_df = df.sort(by=["a", "b"], descending=[True, True])

# 计算累计最大b值，筛选出未被支配的数对
result = sorted_df.with_columns(
    pl.col("b").cum_max().alias("max_b_so_far")
).filter(
    pl.col("b") == pl.col("max_b_so_far")
).select("a", "b")

# 可选：按示例格式排序输出（不影响结果正确性）
result = result.sort(by=["a", "b"], descending=[False, True])

print(result)

算法正确性说明 #

• 排序后，前面的数对a≥当前数对的a；
• cum_max()计算的是遍历到当前位置时的最大b值：
  • 如果当前数对的b等于max_b_so_far，说明不存在前面的数对能支配它（前面的数对要么a更大但b更小，要么a相同但b不大于它），同时后面的数对a更小，不可能满足a≥当前数对的a，因此该数对属于帕累托前沿；
  • 如果当前数对的b小于max_b_so_far，说明存在前面的数对（a≥当前a且b≥当前b，且至少一个严格大于），因此该数对被支配，需过滤。

性能优势 #

相比原方案的O(n²)时间复杂度，该算法仅需O(n log n)的排序时间，在大数据集下性能提升极其显著：例如当n=1000时，原方案需要100万次对比，而该算法仅需约1万次排序操作。

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