我有一台有1mb内存的电脑,没有其他本地存储。我必须使用它通过TCP连接接受100万个8位十进制数字,对它们进行排序,然后通过另一个TCP连接发送排序的列表。
数字列表可能包含重复的,我不能丢弃。代码将放在ROM中,所以我不需要从1 MB中减去我的代码的大小。我已经有了驱动以太网端口和处理TCP/IP连接的代码,它需要2 KB的状态数据,包括1 KB的缓冲区,代码将通过它读取和写入数据。这个问题有解决办法吗?
问答来源:
slashdot.org
cleaton.net
我有一台有1mb内存的电脑,没有其他本地存储。我必须使用它通过TCP连接接受100万个8位十进制数字,对它们进行排序,然后通过另一个TCP连接发送排序的列表。
数字列表可能包含重复的,我不能丢弃。代码将放在ROM中,所以我不需要从1 MB中减去我的代码的大小。我已经有了驱动以太网端口和处理TCP/IP连接的代码,它需要2 KB的状态数据,包括1 KB的缓冲区,代码将通过它读取和写入数据。这个问题有解决办法吗?
问答来源:
slashdot.org
cleaton.net
当前回答
下面是一些可以解决这个问题的c++代码。
满足内存约束的证明:
编辑:无论是在这篇文章中还是在他的博客中,都没有作者提供的最大内存要求的证据。由于编码值所需的比特数取决于先前编码的值,因此这样的证明可能不是简单的。作者指出,根据经验,他可能遇到的最大编码大小是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字节作为剩余变量和堆栈空间。
它在我的至强W3520上运行大约23秒。您可以使用以下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('%08d\n' % value)
sorter.stdin.close()
result = [int(line) for line in sorter.stdout]
print('OK!' if result == sorted(sequence) else 'Error!')
该算法的详细解释可以在以下一系列帖子中找到:
1MB排序说明 算术编码与1MB排序问题 使用定点数学的算术编码
其他回答
你用的是哪种电脑?它可能没有任何其他“正常”的本地存储,但它是否有视频RAM,例如?100万像素x每像素32位(比如说)非常接近你所需的数据输入大小。
(我主要是问旧的Acorn RISC PC的内存,如果你选择低分辨率或低颜色深度的屏幕模式,它可以“借用”VRAM来扩展可用的系统RAM !)这在只有几MB普通RAM的机器上非常有用。
我想试试基数树。如果可以将数据存储在树中,那么就可以执行顺序遍历来传输数据。
我不确定你是否能把它装进1MB,但我认为值得一试。
(我原来的答案是错误的,对不起,数学不好,见下面的休息。)
这个怎么样?
前27位存储您所看到的最小数字,然后是与下一个数字的差值,编码如下:5位存储用于存储差值的位数,然后是差值。使用00000表示您再次看到了该数字。
这是因为插入的数字越多,数字之间的平均差值就越小,所以当你添加更多的数字时,你用更少的比特来存储差值。我想这叫做增量表。
我能想到的最糟糕的情况是所有数字都等距(以100为间隔),例如假设0是第一个数字:
000000000000000000000000000 00111 1100100
^^^^^^^^^^^^^
a million times
27 + 1,000,000 * (5+7) bits = ~ 427k
Reddit来拯救你!
如果你要做的只是把它们排序,这个问题就简单了。它需要122k(100万比特)来存储你看到的数字(如果看到0,则第0位,如果看到2300,则第2300位,等等。
读取数字,将它们存储在位域中,然后在保持计数的同时将位移出。
但是,你必须记住你看过多少。我受到上面的子列表答案的启发,想出了这个方案:
用2位或27位代替1位:
00表示你没有看到这个数字。 01表示你看过一次 1表示你看过,接下来的26位是看了多少次。
我认为这是可行的:如果没有重复,你就有一个244k的列表。 在最坏的情况下,你看到每个数字两次(如果你看到一个数字三次,它会缩短列表的其余部分),这意味着你不止一次看到了50,000个,你0次或1次看到了950,000个项目。
50,000 * 27 + 950,000 * 2 = 396.7k.
如果你使用以下编码,你可以做进一步的改进:
0表示你没有看到这个数字 10表示你看过一次 11是你计数的方式
这将导致平均280.7k的存储空间。
编辑:我周日早上的数学算错了。
最坏的情况是,我们两次看到50万个数字,所以数学就变成了:
500,000 *27 + 500,000 *2 = 1.77M
交替编码导致平均存储为
500,000 * 27 + 500,000 = 1.70M
: (
由于ROM大小不计算,因此除了TCP缓冲区外,不需要任何额外的RAM。只需要实现一个大的有限状态机。每个状态表示读入的多组数字。在读取了一百万个数字之后,只需打印出与所达到的状态相对应的数字。
您只需要按顺序存储数字之间的差异,并使用编码来压缩这些序列号。我们有2^23位。我们将它分成6位块,让最后一位表示这个数字是否扩展到另外6位(5位加上扩展块)。
因此,000010是1,000100是2。000001100000表示128。现在,我们考虑用最坏的类型来表示不超过10,000,000的数字序列的差异。可能有10000000 /2^5的差异大于2^5,10000000 /2^10的差异大于2^10,10000000 /2^15的差异大于2^15,等等。
所以,我们把表示这个序列所需要的比特数相加。我们有1,000,000*6 +汇总(10,000,000/2^5)*6+汇总(10,000,000/2^10)*6+汇总(10,000,000/2^15)*6+汇总(10,000,000/2^20)*4=7935479。
2^24 = 8388608。由于8388608 > 7935479,我们应该很容易有足够的内存。我们可能还需要一点内存来存储插入新数字时的和。然后我们遍历这个序列,找到插入新数字的位置,如果必要的话减少下一个差值,并将它之后的所有内容都右移。