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

Question

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

algorithmlanguage-agnosticgoogle-moderator

14

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

更新：没有对外部存储设置约束。

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

- J.F. Sebastian

相关：使用Python对文本文件进行排序（更通用的实现），从硬盘中排序大量整数。 - jfs

10个回答

11

使用Python在只占用2MB内存的情况下对一百万个32位整数进行排序，作者是Guido van Rossum

- J.F. Sebastian

10

有点儿可疑啊 :) - skaffman

Guido应该首先优化其网站。为什么他不采用白色背景和白色字体颜色呢；-) 看起来更好。 - Noah Tony

4

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

您应该使用一些使用外部存储器的算法来对它们进行排序。例如，归并排序。

- gabr

4

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

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

- zvrba

3

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

- chakrit

1

使用多阶段合并的双重锦标赛排序

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

- J.F. Sebastian

0

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

将一半的数字加载到内存中。原地堆排序并将输出写入文件。重复另一半。使用外部排序（基本上是考虑了文件 I/O 的归并排序）来合并两个文件。

附注：使堆排序在面对缓慢的外部存储时更快：

在所有整数都在内存中之前开始构建堆。
在堆排序仍在提取元素时开始将整数放回输出文件中。

- AtlasMeh-ed

0

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

- Adam Hawes

-2

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

在C++中使用int、short和char类型，尽可能地将“数字”装入尽可能小的空间中。您可以通过多种类型的转换来使代码更加简洁（但可能会有一些奇怪的脏代码）。

以下是我的建议：

任何小于2^8（0-255）的值都将存储为char（1字节数据类型）

任何大于2^8且小于2^16（256-65535）的值都将存储为short（2字节数据类型）

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

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

- J.J.

如果所有数字都大于65535，则不会有太大的帮助，或者根本没有帮助。 - gabr

1

你要跟踪类型所浪费的空间比你节省的还多！ - Adam Hawes

-3

没有示例，但是桶排序的复杂度相对较低且易于实现。

- Harald Scheirich

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- moonshadow · Accepted Answer

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