algorithm - 1MB RARAM排序1百万8-digit的数字

  显示原文与译文双语对照的内容

我有一台装有 1米内存的计算机,没有其他本地存储。 我必须使用它在TCP连接上接受 1 million 8 -digit十进制数,排序它们,然后通过另一个TCP连接发送排序列表。 数字列表中可能含有重复项,我不能丢弃这些重复项。 代码将放在ROM中,所以我不需要从 1中减去代码的大小。 我已经有了驱动以太网端口和处理 tcp/ip连接的代码,它需要 2 k的状态数据,其中包括 1 k的缓冲区,代码将读取和写入数据。 这个问题有解决办法?

的问题和答案:
http://tech.slashdot.org/comments.pl?sid=232757&cid=18925745
http://nick.cleaton.net/ramsort.html

时间:

是一些工作 C++ 代码,它解决了这个问题。

证明内存约束满足:

编辑器: 现在并没有证据的最大内存要求由作者要么在这篇文章,或者在他的博客中都推荐。 由于编码一个值所需的位数取决于以前编码的值,这样的证明很可能是 non-trivial 。 作者注意到,他遇到的最大编码大小是 1011732,并选择了缓冲区大小 1013000


typedef unsigned int u32;

namespace WorkArea
{
 static const u32 circularSize = 253250;
 u32 circular[circularSize] = { 0 };//consumes 1013000 bytes

 static const u32 stageSize = 8000;
 u32 stage[stageSize];//consumes 32000 bytes

. . .

这两个数组一起占用 1045000字节的存储空间。 对于剩余变量和堆栈空间,保留 1048576 - 1045000 - 2 ×1024 = 1528字节。

大约在我的至强 23秒它 runs. 你可以验证程序是否使用以下 python 脚本,假定程序名为 sort1mb.exe


from subprocess import *
import random

sequence = [random.randint(0, 99999999) for i in xrange(1000000)]

sorter = Popen('sort1mb.exe', stdin=PIPE, stdout=PIPE)
for value in sequence:
 sorter.stdin.write('%08dn' % value)
sorter.stdin.close()

result = [int(line) for line in sorter.stdout]
print('OK!' if result == sorted(sequence) else 'Error!')

可以在以下一系列文章中找到该算法的详细说明:

Gilmanov的回答是非常错误的假设。 它开始猜测了总部设在一个integer的一百万连续 无意义测量。 这意味着,无论多么微小,没有差距。那些随机间隙并希望将它做成一个糟糕的主意。

试试自己,得到 1万随机 27位整数,排序它们,用 7 zip,xz,无论你想要什么。 结果超过 1.5 MB 。 在上面的前提是连续数字的压缩。 甚至那是通过 1.1 增量编码的宏块 。 而且不要介意它使用 100 MB的内存进行压缩。 所以即使是压缩的整数也不适合问题 ,也不介意运行时间 RAM 。

它是saddens我如何处理漂亮的图形和合理化。


#include <stdint.h>
#include <stdlib.h>
#include <time.h>

int32_t ints[1000000];//random 27bit integers

int cmpi32(const void *a, const void *b) {
 return ( *(int32_t *)a - *(int32_t *)b );
}

int main() {
 int32_t *pi = ints;//Pointer to input ints (REPLACE W/read from net)

//Fill pseudo random integers of 27 bits
 srand(time(NULL));
 for (int i = 0; i <1000000; i++)
 ints[i] = rand() & ((1<<27) - 1);//random 32bit masked to 27 bits

 qsort(ints, 1000000, sizeof (ints[0]), cmpi32);//Sort 1000000 int32s

//Now delta encode, optional, store differences to previous int
 for (int i = 1, prev = ints[0]; i <1000000; i++) {
 ints[i] -= prev;
 prev += ints[i];
 }

 FILE *f = fopen("ints.bin","w");
 fwrite(ints, 4, 1000000, f);
 fclose(f);
 exit(0);

}

lzma 。现在.,压缩


$ xz -f --keep ints.bin # 100MB RAM
$ 7z a ints.bin.7z ints.bin # 130MB RAM
$ ls -lh ints.bin*
 3.8M ints.bin
 1.1M ints.bin.7z
 1.2M ints.bin.xz

我的建议对 的解决方案有很大的帮助

首先我假设解决方案必须处理所有可能的输入列表。 我认为流行的答案并不意味着这个假设。

众所周知没有一种形式的无损压缩会降低所有输入的大小。

所有流行的答案都假设他们能够应用压缩效果,从而允许他们额外的空间。 实际上,大块额外的空间足够大,足以以未压缩形式保存部分完整的列表,并允许它们执行排序操作。 这只是一个错误的假设。

对于这样的解决方案,任何知道如何进行压缩的人都能够设计一些不适合这个方案的输入数据,并且"解决方案"很可能由于耗尽空间而中断。

相反,我采取了一种数学方法。 我们可能的输出是长度为 0的所有长度的列表,范围为。最大值。 LEN是 1,000,000,我们的最大值是 100,000,000.

对于任意的LEN和最大值,编码这里状态所需的位数是:

Log2(MAX Multichoose LEN )

因此,对于我们的数字,一旦完成接收和排序,我们至少需要 Log2(100,000,000 MC 1,000, 000) 位来存储结果,以唯一区分所有可能的输出。

这是 ~= 988 kb 。 所以我们有足够的空间来保存我们的结果。 从这个角度看,它是可能的。

[Deleted pointless rambling now that better examples exist... ]

最佳答案在这里

另外一个很好的答案只是,实际上主要组合插入排序算法作为由一个元素( 缓冲一些元素和 pre-sorts,允许一次插入多个元素,节省一点时间) 函数来展开列表。 使用简洁的压缩状态编码,buckets位增量

假设这里任务是可能的。 只是在进行输出的,会有一个in-memory表示万排序的数字。 有多少种不同的表示方式? 在 ,因为可能有重复的数字,我们可以不使用分歧格( 选择) 多重集,但有一个操作叫做 multichoose,works.

  • 2.2e2436455 中方式中选择一种万数字范围 0.。99,999,999.
  • 需要 8,093,730 位代表每个可能的组合,或者 1,011,717字节。

所以从理论上说它也许是可能的,如果你能设计出一份理智( 足够) 表示数字的排序列表。 例如一个疯狂的表示可能需要 10 MB的查找表或者成千上万的代码行。

但是,如果" 1 m 内存"表示一百万字节,那么显然没有足够的空间。 这一事实 5%更多内存使它的理论上可能的建议,将必须非常高效的我们,这个表示,可能不理智的。

...