如何在C/C++/Fortran中快速将多维数组B按A的顺序排序，适配十亿级点集

解决方案 #

十亿级数据量下不要用常规的全量比对排序，核心思路是用A的顺序给B的数据打排序标签，再按标签做低复杂度排序，具体方案分场景实现：

场景1：可以直接提取数据点的唯一索引 #

你提到坐标字段末尾的数字是点的索引，比如cx7对应点ID为7，这种情况是效率最高的，完全不需要构建映射：

• 遍历B的每一行数据，从坐标字段提取点ID，作为排序标签拼到行首
• 对拼接后的文件按首列ID做基数排序，排序完成后删掉首列即可
• 工具层面直接用Linux原生sort命令即可完成十亿级外存排序，示例命令：

# 给B加ID列后排序，自动用外存处理超大数据，-S参数可以指定允许占用的内存上限
sort -n -k1,1 -S 50% B_with_id.txt -o B_sorted.txt

整个流程时间复杂度只有O(N)的ID提取 + O(N)的基数排序，是最优解。

场景2：无法直接提取点ID，需要通过坐标匹配 #

子场景2.1 单节点内存足够容纳A的全量映射（10亿条坐标+索引约占16GB内存，常规服务器都可满足）

• 遍历数据集A，为每个坐标(cx, cy, cz)生成顺序索引（第一行索引为0，第二行为1，以此类推），构建哈希映射：
  优化点：不要用字符串存储坐标作为key，直接将三个坐标值序列化为固定长度的二进制串（比如3个float32共12字节），哈希查询效率可以提升3倍以上，占用内存也更小
• 遍历数据集B，为每行提取坐标查询映射得到对应索引，将索引拼到行首输出为临时文件
• 对临时文件按首列索引做基数排序，完成后移除首列即得到符合A顺序的B数据集

子场景2.2 单节点内存不足以容纳A的全量映射

采用分桶关联的思路处理：

• 按坐标的取值范围（比如按cx的数值区间）将A划分为N个桶，每个桶的大小控制在内存可容纳范围内，遍历A时将坐标和对应索引存入对应桶的文件
• 用完全相同的分桶规则，将B的所有行划分到对应的桶文件中
• 逐个加载每个A桶到内存构建映射，为同桶的B行打索引标签，按索引排序后输出该桶的排序结果
• 按桶的顺序拼接所有桶的输出结果，即得到最终排序后的B数据集

注意事项 #

• 所有流程中B的坐标和速度字段都是整行处理，不会出现关联关系错乱的问题
• 优先用系统原生的排序工具，比自行实现的外存排序稳定性和效率都高很多

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