我想在C中排序四百万long long
s。通常我只是malloc()
一个缓冲区用作数组并调用qsort()
但是四百万* 8字节是一大块连续内存。
最简单的方法是什么? 为此,我对速度感到轻松。 我不想使用任何库,结果将需要在Windows和Linux下的适度上网本上运行。
只需分配一个缓冲区并调用qsort
。 即使在适度的上网本上,如今32MB还不是很大。
如果你真的必须拆分它:对较小的块进行排序,将它们写入文件,然后合并它们(合并对每个被合并的东西进行一次线性传递)。 但是,真的,不要。 只是排序吧。
(关于Knuth第2卷中的排序和合并方法有一个很好的讨论,它被称为“外部排序”。当Knuth写这篇文章时,外部数据会出现在磁带上,但原理并不是很好不同的光盘:你仍然希望你的I / O尽可能顺序。与SSD的权衡有点不同。)
32 MB? 这不是太大……快速排序应该做的伎俩。
您最好的选择是尽可能防止数据无序。 就像它已经提到的那样,你最好将数据从磁盘(或网络或任何源)直接读入一个自组织容器(一棵树,也许std::set
会这样做)。
这样,您将永远不必排序,或者不得不担心内存管理。 如果您知道容器所需的容量,则可以通过使用std::vector(initialcapacity)
或先调用vector::reserve
来挤出额外的性能。
然后,建议您最好使用std::make_heap
来堆积任何现有元素,然后使用push_heap
逐个元素地添加元素(另请参阅pop_heap
)。 这基本上与自我排序集相同,但是
(哦,小细节,请注意堆上的sort_heap
最多需要N log N比较,其中N是元素数)
如果您认为这是一种有趣的方法,请告诉我。 我真的需要关于用例的更多信息
以上就是c/c++开发分享如何在C中对非常大的数组进行排序相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/519619.html