(从这里)
我上周参加了一个采访,问了这个问题:
如何在基于8080处理器的计算机中仅使用640KB内存的文件中对十亿行数据进行排序？没有虚拟内存,没有外部磁盘.
我明确地询问了面试官我是否可以使用硬盘驱动器,所以我可以在排序树时对其进行序列化,然后在最后进行组合.他说不.我尝试了很多方法,不同的算法.他没有同意.
我放弃了,礼貌地问他,"你会怎么做？" 他直言不讳地说:"我不会告诉你的." (采访在那之后就结束了.我不是故意得罪他,作为一名开发人员,我很好奇.而且,这是一个本能的问题,就像我在工作场所问过任何人一样.)
这次访谈是为了一家非常大的银行.
那么,怎么会有人解决这个问题呢？
给定硬盘上的100 GB整数数据,RAM为2 GB,如何使用最少的磁盘操作对整数进行排序.这里从磁盘中获取一个数字被视为一个磁盘操作(尽管实际上可以获取一个数据块).
我们可以使用磁盘上的额外空间进行临时存储,而无需考虑清理使用的临时空间的操作.
我有一个包含超过1000万行的文本文件.这样的行:
37024469;196672001;255.0000000000
37024469;196665001;396.0000000000
37024469;196664001;396.0000000000
37024469;196399002;85.0000000000
37024469;160507001;264.0000000000
37024469;160506001;264.0000000000
如你所见,分隔符是";".我想根据第二个元素使用python对这个文本文件进行排序.我不能使用拆分功能.因为它会导致MemoryError.我该怎么办呢？
排序最多1000万个7位数字.约束:1M RAM,高速.几秒钟是好的.
[编辑:来自提问者的评论:输入值不同]
使用位图数据结构是解决此问题的好方法.
这意味着我需要一个字符串,长度最多为1000万???? RAM足够了吗？困惑在这里.谢谢