问题描述
（从here)
我参加了上周接受采访时，这问题是问：
I attended an interview last week and this question was asked:
如何在仅有的640KB内存在基于8080处理器机器上的文件进行排序十亿行的数据？否虚拟内存，没有外部磁盘。
How do you sort a billion rows of data in a file with only 640KB of memory in a 8080 processor based machine? No virtual memory, no external disk.
我明确问面试官，如果我可以用一个硬盘驱动器，这样我就可以序列化的树，因为我对它们进行排序，然后组合在最后。他说没有。我试了很多方法，不同的算法。没有他同意了。
I explicitly asked the interviewer if I could use a hard drive, so I can serialize trees as I sort them and then combine at the end. He said no. I tried many ways, different algorithms. Nothing he agreed.
我放弃了，问他礼貌，你会怎么做呢？他直言不讳地说，我不会告诉你。 （右后，面试结束了。我不是有意冒犯他，作为一个开发者，我得到了好奇。而且，这是一种本能的问题，就像我想请人在我的工作场所。）
I gave up and asked him politely, "how would you do that?" He bluntly said, "I would not tell you." (The interview ended right after that. I didn't mean to offend him, as a developer, I got curious. Moreover, it was an instinctive question, just as I would ask anyone at my workplace.)
这是采访一个真正的大银行。
This interview was for a really big bank.
那么，如何会有人解决这个问题？
So, how would anyone approach this problem?
推荐答案
堆排序将是我的reccomendation。这是比较快，当n很大，而你只需要看三个要素有明确indecies一次。
Heapsort would be my reccomendation. It's relatively quick when n is large, and you only have to look at three elements with definite indecies at once.
话虽这么说，我的直觉告诉我，即使在C整理一个十亿行上8080将是unfeasibly慢。
That being said, my intuition tells me that sorting a billion rows on an 8080 even in C would be unfeasibly slow.
这篇关于如何用更少/微薄的内存排序数百万行数据的文件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！