请以您选择的语言提供代码示例。
更新：没有对外部存储设置限制。
示例：整数通过网络接收/发送。本地磁盘上有足够的空间用于中间结果。
J.F. Sebastian
问问题
31849 次
10 回答
18
将问题拆分成足够小以适合可用内存的部分，然后使用归并排序将它们组合起来。
于 2008-09-25T15:57:14.457 回答
11
于 2008-10-23T07:38:20.207 回答
4
100 万个 32 位整数 = 4 MB 内存。
您应该使用一些使用外部存储的算法对它们进行排序。以合并排序为例。
于 2008-09-25T15:55:35.100 回答
4
您需要提供更多信息。有哪些额外的存储空间可用？您应该将结果存储在哪里？
否则，最一般的答案：1.将前半部分数据加载到内存中（2MB），用任何方法排序，输出到文件。2.将后半部分数据加载到内存中（2MB），任意排序，保存在内存中。3. 使用合并算法将两个排序后的一半合并，并将完整的排序数据集输出到一个文件中。
于 2008-09-25T15:57:52.847 回答
3
这篇关于外部排序的维基百科文章有一些有用的信息。
于 2008-09-25T16:38:14.327 回答
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
于 2008-09-25T18:33:12.380 回答
0
- 嗯，将它们全部存储在一个文件中。
- 内存映射文件（你说只有 2M 的 RAM；假设地址空间足够大，可以内存映射文件）。
- 使用文件后备存储对它们进行排序，就好像它现在是真实内存一样！
于 2009-02-12T08:09:50.283 回答
0
这是一个有效且有趣的解决方案。
将一半的数字加载到内存中。对它们进行堆排序并将输出写入文件。对另一半重复。使用外部排序（基本上是考虑文件 i/o 的合并排序）来合并两个文件。
另外：面对缓慢的外部存储，使堆排序更快：
在所有整数都在内存中之前开始构建堆。
在堆排序仍在提取元素时开始将整数放回输出文件
于 2013-01-16T05:43:37.217 回答
-2
正如上面提到的 32 位 4 MB 的 int 类型。
使用 C++ 中的 int、short 和 char 类型将尽可能多的“数字”放入尽可能少的空间。通过进行几种类型的强制转换来到处塞满东西，你可能会很聪明（但有奇怪的脏代码）。
它在我座位的边缘。
小于 2^8(0 - 255) 的任何内容都存储为 char（1 字节数据类型）
小于 2^16(256 - 65535) 且 > 2^8 的任何内容都存储为短（2 字节数据类型）
其余的值将被放入 int。（4字节数据类型）
您需要指定 char 部分的开始和结束位置、short 部分的开始和结束位置以及 int 部分的开始和结束位置。
于 2008-09-25T16:28:46.127 回答
-3
没有例子，但是桶排序的复杂度相对较低，并且很容易实现
于 2008-09-25T20:28:13.900 回答