如何在 2MB RAM 中对 100 万个 32 位整数进行排序？

Question

请提供您选择的语言的代码示例。

更新： 对外部存储没有设置限制。

示例：通过网络接收/发送整数。 本地磁盘有足够的空间用于保存中间结果。

Answer 1

将问题分成足够小的部分以适合可用内存，然后使用合并排序将它们组合起来。

Answer 2

对 2MB 中的一百万个 32 位整数进行排序Guido van Rossum 使用 Python 构建 RAM

Answer 3

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

您应该使用某种使用外部存储的算法对它们进行排序。 例如，合并排序。

Answer 4

您需要提供更多信息。 有什么额外的存储空间可用？ 你应该将结果存储在哪里？

否则，最普遍的答案是：
1. 将前半部分数据加载到内存（2MB），用任意方法排序，输出到文件。
2.将后半部分数据加载到内存中（2MB），用任意方法排序，保留在内存中。
3. 使用合并算法将已排序的两半进行合并，并将完整的已排序数据集输出到文件中。

Answer 5

这篇有关外部排序的维基百科文章提供了一些有用的信息。

Answer 6

双锦标赛排序与多阶段合并

#!/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

Answer 7

• 嗯，将它们全部存储在一个文件中。
• 内存映射文件（你说只有 2M 的 RAM；我们假设地址空间足够大，可以内存映射文件）。
• 使用文件后备存储对它们进行排序，就好像它现在是真实内存一样！

Answer 8

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

将一半的数字加载到内存中。 对它们进行堆排序并将输出写入文件。 对另一半重复上述步骤。 使用外部排序（基本上是考虑文件 I/O 的合并排序）来合并两个文件。

在旁边：
在面对缓慢的外部存储时，使堆排序更快：

• 在所有整数进入内存之前开始构建堆。

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

  在

Answer 9

正如上面的人提到的 32 位 4 MB 的 int 类型。

使用 C++ 中的 int、short 和 char 类型将尽可能多的“数字”放入尽可能小的空间中。 你可以通过进行多种类型的转换来将东西塞满各处，从而变得狡猾（但有奇怪的脏代码）。

它就在我座位的边缘。

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

任何小于 2^16(256 - 65535) 且 > 的内容 都会存储为 char（1 字节数据类型） 2^8 被存储为短整型（2 字节数据类型），

其余值将被放入 int 中。 （4 字节数据类型）

您需要指定 char 部分开始和结束的位置、short 部分开始和结束的位置以及 int 部分开始和结束的位置。

Answer 10

没有示例，但是桶排序复杂度相对较低，并且很容易实现