我有一个巨大的文件,每行都有独特的单词.文件大小约为1.6 GB(我要在此之后对其他文件进行排序,大约为15GB).直到现在,我使用的文件较小Array.sort().但对于这个文件我得到了java.lang.OutOfMemoryError: Java heap space.我知道这个错误的原因.有没有办法,而不是写完整的快速排序或合并排序程序.
我读到Array.sort()在内部使用Quicksort或Hybrid Sort.有没有像Array.sort()??的程序？
如果我必须编写一个程序进行排序,我应该使用哪一个？Quicksort或Merge排序.我担心最坏的情况.
根据要存储的数据的结构,您可以执行许多不同的操作.
如果结构良好的数据需要按一个或多个特定字段排序(在这种情况下系统工具可能没有用),那么最好使用允许排序的数据存储区.考虑到尺寸不超过几百GB,我认为MongoDB非常适合这种情况.其他NoSQL数据存储也可能很好地适应这个法案,尽管Mongo的使用和安装简单以及对JSON数据的支持使它成为一个非常好的候选者.
如果你真的想要使用java方法,它会变得非常棘手.这是你在求职面试时提出的问题,我实际上也不会指望任何人实现代码.但是,一般的解决方案是合并排序(使用随机访问文件是一个坏主意,因为它意味着插入排序,即非最佳运行时间,考虑到文件的大小可能会很糟糕).
通过合并排序我的意思是在足够小的时间读取文件的一大块以使其适合内存(因此它取决于你有多少RAM),对其进行排序然后将其写回磁盘上的新文件.读完整个文件后,您可以通过只读取每个文件的头部并将两个文件中较小的文件(两个记录中较小的一个)写回第三个文件,一次开始合并两个块文件.为"第一代"文件执行此操作,然后继续使用第二代文件,直到最终得到一个大的已排序文件.请注意,这基本上是实现合并排序的自下而上的方式,学术递归算法是自上而下的方法.
注意,通过使用多路合并算法可以完全避免使用中间文件.这通常基于堆/优先级队列,因此实现可能稍微复杂一些,但它会减少所需的I/O操作数.
使用一些精心设计在java中实现上述内容应该不会太困难,尽管它肯定会变得棘手.我仍然强烈推荐像Mongo这样开箱即用的解决方案.
| 归档时间： |
|
| 查看次数： |
1343 次 |
| 最近记录： |