C#数据结构算法

我最近接受了一家TOP软件公司的采访.我完全陷入了面试官问我的一个问题,那就是

问:我有一台512 mb/1 GB RAM的机器,我必须对4 GB大小的文件(XML或任何)进行排序.我该怎么办？什么是数据结构,我将使用哪种排序算法以及如何使用？

你认为这是可以实现的吗？如果是,那么请您解释一下吗？

提前致谢!

面试官可能想要的答案可能是你如何设法有效地对超出系统内存的数据集进行排序.以下部分来自维基百科:

内存使用模式和索引排序

当要排序的数组的大小接近或超过可用的主存储器时,必须使用(慢得多)磁盘或交换空间,排序算法的内存使用模式变得很重要,并且算法可能是公平的当阵列容易适合RAM时,效率可能变得不切实际.在这种情况下,比较的总数变得(相对)不那么重要,并且必须从磁盘复制或交换存储器部分的次数可以支配算法的性能特征.因此,通过次数和比较的定位可能比原始的比较更重要,因为附近元素之间的比较发生在系统总线速度(或者,缓存,甚至是CPU速度),

例如,流行的递归快速排序算法提供了相当合理的性能和足够的RAM,但是由于它复制了数组部分的递归方式,当数组不适合RAM时变得不太实用,因为它可能导致一些缓慢复制或移动操作进出磁盘.在那种情况下,即使需要更多的总比较,另一种算法也可能是优选的.

解决此问题的一种方法是,当复杂记录(例如在关系数据库中)由相对较小的关键字段进行排序时,该方法是在数组中创建索引,然后对索引进行排序,而不是整个阵列.(然后可以通过一次传递生成整个数组的排序版本,从索引读取,但通常甚至这是不必要的,因为排序索引是足够的.)因为索引比整个数组小得多,所以它可能很容易适应整个阵列所不具备的内存,有效地消除了磁盘交换问题.此过程有时称为"标签排序".[5]

克服存储器大小问题的另一种技术是以一种利用每种算法的优势来提高整体性能的方式组合两种算法.例如,可以将数组细分为大小适合RAM的块(例如,几千个元素),使用有效算法(例如quicksort或heapsort)对块进行排序,并根据mergesort合并结果.这比首先进行mergesort效率低,但它比整个阵列上的完全快速排序需要更少的物理RAM(实用).

技术也可以组合.为了对非常大的超出系统存储器的数据集进行排序,甚至可能需要使用算法或算法组合对索引进行排序,以便与虚拟存储器合理地执行,即减少所需的交换量.