Ruo*_*ang 9 java sorting algorithm
这是破解编码访谈的另一个问题,我在阅读之后仍有一些疑问.
9.4 If you have a 2 GB file with one string per line, which sorting algorithm
would you use to sort the file and why?
解
当面试官给出2GB的大小限制时,它应该告诉你一些东西 - 在这种情况下,它表明他们不希望你把所有数据都带入内存.那么我们该怎么办？我们只将部分数据带入内存..算法:
我们有多少内存？假设我们有X MB的内存可用.
将文件分成K个块,其中X*K = 2 GB.将每个块放入内存并使用任何O(n log n)算法照常排序.将行保存回文件.
现在将下一个块放入内存并进行排序.
完成后,将它们逐个合并.
上述算法也称为外部排序.第3步称为N路合并使用外部排序的基本原理是数据的大小.由于数据太大而我们无法将其全部存入内存,因此我们需要采用基于磁盘的排序算法.
怀疑:
在步骤3中,进行合并排序,同时比较2个数组,每次比较时我们是否需要2*X空间？限制是X MB.我们应该把块打成(X/2)*2K = 2GB吗？这样每个块将是X/2 MB,并且将有2K块.或者我只是理解合并排序错误？谢谢!
http://en.wikipedia.org/wiki/External_sorting
快速浏览维基百科告诉我,在合并过程中,你永远不会在内存中占据一大块.所以基本上,如果你有K块,你将有K个打开文件指针,但在任何给定时间你只能从内存中的每个文件中保留一行.您将比较内存中的行,然后将最小的行(例如,从块5)输出到已排序的文件(也是打开的文件指针,而不是内存中),然后用该文件中的下一行覆盖该行(在我们的例子中,文件5)进入内存并重复,直到你到达所有块的末尾.
首先,第3步本身不是合并排序,整个事情是合并排序.第3步只是一个合并,根本不涉及任何排序.
至于所需的存储空间,有两种可能性.
第一种是将分类数据合并为两组.假设你有三组:
A: 1 3 5 7 9
B: 0 2 4 6 8
C: 2 3 5 7
根据该方法,你会合并A,并B在到一个组Y,然后合并Y,并C进入最终的结果Z:
Y: 0 1 2 3 4 5 6 7 8 9 (from merging A and B).
Z: 0 1 2 2 3 3 4 5 5 6 7 7 8 9 (from merging Y and C).
这具有非常小的常量内存要求的优点,因为您只需要存储来自两个列表中的每一个的"下一个"元素,但是,当然,您需要执行多个合并操作.
第二种方式是"正确的"N路合并,您可以从任何组中选择下一个元素.有了它,你会检查每个列表中的最低值,看看下一个是哪一个:
Z: 0 1 2 2 3 3 4 5 5 6 7 7 8 9 (from merging A, B and C).
这只涉及一次合并操作,但需要更多存储空间,每个列表基本上只有一个元素.
您选择哪一个取决于可用内存和元素大小.
例如,如果您有100M内存可供使用且元素大小为100K,则可以使用后者.这是因为,对于2G文件,您需要20个组(每个100M)用于排序阶段,这意味着正确的N路合并将需要100K乘20或大约2M,远低于您的内存可用性.
或者,假设您只有1M可用.这将是大约2000(2G/1M)组,并乘以100K给出200M,远远超出你的容量.
所以你必须在多次传递中进行合并.请记住,它不必是合并两个列表的多次传递.
你可以找到一个中间地带,例如每个通道合并十个列表.十组100K只是一个兆位,因此将适合您的内存约束,这将导致更少的合并传递.