如何用更少/微薄的内存排序数百万行数据的文件 [英] How to sort millions of rows of data in a file with less/meagre memory

问题描述

（从<一个href="http://stackoverflow.com/questions/134158/how-would-you-sort-1-million-32-bit-integers-in-2mb-of-ram/3961223#3961223">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.

这篇关于如何用更少/微薄的内存排序数百万行数据的文件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！