用于排序大型文本文件的多相合并排序

我的编程语言是C＃。

其结构txt文件如下：

for instance   desired Result 
------------   ---------------  
    723,80     1,4 
    14,50     1,5 
    723,2     10,8 
    1,5     14,50 
    10,8     723,2 
    1,4     723,80

与此同时，记忆是对我很重要。

这个算法适合这份工作吗？

如果合适，请给出这个算法的解释。举例

谢谢。

来源

2013-12-22 gandolf

对于您所展示种类的数百万行（我认为您的意思是线条而不是算法），除非您在非常受限的环境中运行，否则C＃库中的内存快速排序将会正常。 – Gene

文本文件中有500万行 – gandolf

内置排序算法有什么问题？它是快速排序，这是最快的算法之一。或者你需要一个外部的，基于磁盘的排序？ – usr

如果你能适合内存中的数据，内置的快速排序可能会足够快。

正如在另一个答案中所建议的，使用unix实用工具sort是一个很好的选择。我以前用它来测试超过100,000,000行的运行时间为几秒的文件。

最后，如果你的数据集是真正巨大的，你可以做的是以下

拆分数据到一个可接受的大小
排序每个文件独立使用快速排序，例如不同的文件。如果需要，您可以在更多的计算机上并行执行此操作（请记住，传输文件也会带来成本！）
仅使用一个小内存缓冲区并将数据转储到磁盘上执行parallel merge结果。这可以同时在许多文件上完成。

来源

2013-12-22 14:53:26 Sklivvz

这是一个有趣的想法。这种方法不影响排序的速度吗？http：//en.wikipedia.org/wiki/External_sorting – gandolf

在就地的情况下（因此没有使用额外的内存）合并排序可能不是最好的选择，因为它的标准实现使用线性数量的额外内存。

快速排序，在其标准的实现，并没有使用更多的内存，除了为递归调用内存（具有良好的实现，堆栈内存是O（LOGN），所以它不应该是一个大问题）。

如果您不介意算法不稳定（可能会交换具有相同值的元素，请注意Quickosort），您也可以考虑使用堆排序（就地，O（nlogn），从不是二次方）通常也不稳定。）堆排序可能还需要一些堆栈内存用于递归调用，但通常不像QuickSort那样多。

我不包括QuickSort或HeapSort的说明，因为它们在线或书本上都有很好的文档。当然，许多语言都可以找到示例，包括C＃。

来源

2013-12-22 14:32:52 3yakuya

对于这个任务，我会使用GNU项目中的sort。有了正确的语言环境和-n就可以完成这项工作，我怀疑你不会用这么大的努力来击败这个测试过的程序。你甚至可以利用你所有的内核和排序文件，比你的内存大得多。

来源

2013-12-22 14:45:36

这是编程站点上的算法问题。如果你要建议一个工具/命令行命令，你应该也可以解释它是如何工作的。 – Dukeling

用于排序大型文本文件的多相合并排序

回答

相关问题