在Gayle Laakman的书Cracking the Technical Interview的第11.5节中,
"想象一下,你有一个20GB的文件,每行一个字符串.解释你如何对文件进行排序"
我最初的反应正是她提出的解决方案 - 通过读取X mb的数据,对文件进行排序,然后将其写入磁盘,将文件拆分为更小的块(兆字节).最后,合并文件.
我决定不采用这种方法,因为最终合并将涉及保留主存中的所有数据 - 我们假设这是不可能的.如果是这样的话,这个解决方案究竟是如何实现的？
我的另一种方法是基于这样的假设:我们拥有接近无限的磁盘空间,或者至少足以容纳我们已有数据的2倍.我们可以读入X mb的数据,然后为它们生成散列键 - 每个键对应一个文件中的一行.我们将继续这样做,直到所有值都经过哈希处理.然后我们只需要将该文件的值写入原始文件.
让我知道你的想法.
http://en.wikipedia.org/wiki/External_sorting更详细地解释了外部排序的工作原理。它通过解释如何通过读取已排序块的块（而不是同时读取所有已排序块）来执行 N 个已排序块的最终合并，解决了您最终必须将整个 20gB 放入内存的担忧。
| 归档时间： |
|
| 查看次数： |
1963 次 |
| 最近记录： |