如何在2MB内存中对一百万个32位整数进行排序?

将问题分成足够小的部分,以适合可用的内存,然后使用 merge sort 把它们结合起来。

Sorting a million 32-bit integers in 2MB of RAM using Python by Guido van Rossum

100万个32位整数=4 MB内存。

您应该使用一些使用外部存储的算法对它们进行排序。例如,mergesort。

你需要提供更多的信息。有哪些额外的存储空间?你应该把结果存储在哪里?

否则,最一般的答案是: 1。将前半部分数据装入内存(2MB),按任何方法进行排序,输出到文件。 2。将数据的后半部分装入内存(2MB),按任何方法对其进行排序,并将其保存在内存中。 三。使用合并算法合并两个已排序的部分,并将完整的已排序数据集输出到一个文件。

这个 wikipedia article on External Sorting 有一些有用的信息。

Dual tournament sort with polyphased merge

#!/usr/bin/env python
import random
from sort import Pickle, Polyphase


nrecords = 1000000
available_memory = 2000000 # number of bytes
    #NOTE: it doesn't count memory required by Python interpreter 

record_size = 24 # (20 + 4) number of bytes per element in a Python list
heap_size = available_memory / record_size 
p = Polyphase(compare=lambda x,y: cmp(y, x), # descending order
              file_maker=Pickle, 
              verbose=True,
              heap_size=heap_size,
              max_files=4 * (nrecords / heap_size + 1))

# put records
maxel = 1000000000
for _ in xrange(nrecords):
    p.put(random.randrange(maxel))

# get sorted records
last = maxel
for n, el in enumerate(p.get_all()):
    if el > last: # elements must be in descending order
        print "not sorted %d: %d %d" % (n, el ,last)
        break
    last = el

assert nrecords == (n + 1) # check all records read

• 嗯,把它们都放在一个文件里。
• 内存映射文件(您说过RAM只有2米;假设地址空间足够大,可以存储映射文件)。
• 使用文件备份存储对它们进行排序,就好像它现在是真正的内存一样!

这是一个有效且有趣的解决方案。

把一半的数字装入内存。将它们堆在适当的位置,并将输出写入一个文件。对另一半重复上述步骤。使用外部排序(基本上是考虑文件I/O的合并排序)合并两个文件。

旁白: 在外部存储速度较慢的情况下加快堆排序速度:

• 在所有整数都在内存中之前开始构造堆。

• 当堆排序仍在提取元素时,开始将整数放回输出文件

如上所述,类型int为32位4 MB。

使用C++中的int、Stand和Car类型,尽可能地将尽可能多的“数字”填充到尽可能少的空间中。您可以通过执行几种类型的强制转换来填充任何地方的内容,从而变得圆滑(但有一些奇怪的脏代码)。

它在我的座位边上。

小于2^8(0-255)的任何内容都将存储为char(1字节数据类型)

小于2^16(256-65535)和2^8的任何内容都将存储为短(2字节数据类型)

其余的值将被放入int中。(4字节数据类型)

您需要指定char节的开始和结束位置、短节的开始和结束位置以及int节的开始和结束位置。

没有例子,但是 Bucket Sort 具有相对较低的复杂性,并且易于实现