0

我想long long在 C 中按四百万的顺序排序。通常我只是malloc()一个缓冲区用作数组并调用qsort(),但四百万 * 8 字节是一大块连续内存。

最简单的方法是什么?为此,我将轻松程度置于纯粹的速度之上。我不想使用任何库,结果需要在 Windows 和 Linux 下的普通上网本上运行。

4

3 回答 3

11

只需分配一个缓冲区并调用qsort. 如今,即使在普通的上网本上,32MB 也不是很大。

如果您真的必须拆分它:对较小的块进行排序,将它们写入文件,然后合并它们(合并对每个被合并的事物进行一次线性传递)。但是,真的,不要。就排序吧。

(在 Knuth 的第 2 卷中对排序和合并方法进行了很好的讨论,它被称为“外部排序”。当 Knuth 写那篇文章时,外部数据本来应该在磁带上,但原理不是很清楚与磁盘不同:您仍然希望 I/O 尽可能连续。SSD 的权衡有点不同。)

于 2011-04-07T21:47:53.967 回答
1

32MB?那不是太大....快速排序应该可以解决问题。

于 2011-04-07T21:49:22.520 回答
0

如果可能,您最好的选择是防止数据无序。就像已经提到的那样,您最好将数据从磁盘(或网络或任何来源)直接读取到自组织容器(一棵树,也许std::set可以)中。

这样一来,您就不必对大量内容进行分类,也不必担心内存管理。std::vector(initialcapacity)如果您知道容器所需的容量,您可能会通过使用或预先调用来挤出额外的性能vector::reserve

然后最好建议您使用std::make_heap堆化任何现有元素,然后使用逐个元素添加元素push_heap(另请参见参考资料pop_heap)。这本质上是与自排序集相同的范式,但

  • 重复没问题
  • 存储被“优化”为平面数组(非常适合共享内存映射内存映射文件

(哦,小细节,注意sort_heap在堆上最多进行 N log N 比较,其中 N 是元素的数量)

如果您认为这是一种有趣的方法,请告诉我。我真的需要更多关于用例的信息

于 2011-04-07T21:54:32.793 回答