Polars中如何以O(n)时间实现分组列值连续及组内指定排序？
2026-6-21
关于Polars中DataFrame行重排的O(n)复杂度实现问题
核心需求
- 对DataFrame行进行重排，满足以下要求：
- 指定列（如
col1）值相同的行连续排列，不关心该列的具体排序顺序，目标是将时间复杂度从常规排序的O(nlogn)降至O(n) - 扩展场景：支持多列规则——前M列仅需保证同值行连续（任意顺序），后N-M列按标准顺序排序，避免常规排序对前M列做不必要的有序性计算
- 指定列（如
实际场景示例
城市年度人口数据集（格式：
Date, String, Int），要求同一城市的行连续且按年份排序，但不关心城市间的先后顺序
理论上通过哈希分组可实现O(n)复杂度，需验证Polars内置操作是否比常规排序更高效。
测试结果补充
场景1：仅实现分组行（M=1, N=2，1000万行，平均每组10行）
| 方法 | 耗时 | 排名 |
|---|---|---|
| SORT | 0.26s | 2 |
| EXPLODE | 0.22s | 1 |
| PARTITION | 3.89s | 3 |
各方法说明：
- SORT：
df.sort(["col1", "col2"]) - EXPLODE：
df.group_by("col1").all().explode(pl.exclude("col1")) - PARTITION：
pl.concat(df.partition_by("col1"))
场景2：分组且组内按第二列排序（M=1, N=2，100万行，平均每组10行）
| 方法 | 耗时 | 排名 |
|---|---|---|
| SORT | 0.03s | 1 |
| PARALLELPARTITION | 1.49s | 2 |
| PARTITION | 5.05s | 3 |
各方法说明：
- SORT：
df.sort(["col1", "col2"]) - PARTITION：
pl.concat([x.sort('col2') for x in df.partition_by("col1")]) - PARALLELPARTITION：
pl.concat([x.lazy().sort('col2') for x in df.partition_by("col1")]).collect()
内容的提问来源于stack exchange，提问作者Bananach
相关产品推荐
相关产品推荐
