Skip to content

01joy/external-sorting

Repository files navigation

海量浮点数外部排序算法

在512MB内存限制下,排序2.5亿个浮点数。

主要特点:

  • 浮点数基数排序
  • Grisu算法加速浮点数转换为字符串
  • 败者树加速k-路归并
  • C++11多线程技术
# Doubles File Size Rep. 1 Rep. 2 Rep. 3 Avg. (sec.)
100,0000 16.80MB 0.41 0.34 0.33 0.36
10,000,000 168.00MB 4.57 4.36 4.30 4.41
100,000,000 1.64GB 48.95 50.76 47.33 49.01
250,000,000 4.10GB 153.69 173.00 162.45 163.05

运行时间几乎是线性增长的。