我有一台有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
当前回答
你最多要数到99,999,999,并在沿途标明1,000,000个站点。因此,可以使用位流进行解释,即1表示递增计数器,0表示输出数字。如果流中的前8位是00110010,到目前为止我们将有0,0,2,2,3。
Log (99,999,999 + 1,000,000) / Log(2) = 26.59。你的内存中有2^28位。你只需要用一半!
其他回答
我有一台有1M内存的电脑,没有其他本地存储
另一种作弊方法:你可以使用非本地(网络)存储代替(你的问题不排除这一点),调用一个网络服务,它可以使用直接的基于磁盘的归并排序(或者只需要足够的RAM来在内存中排序,因为你只需要接受1M的数字),而不需要(公认非常巧妙的)已经给出的解决方案。
这可能是作弊,但不清楚你是在寻找一个现实问题的解决方案,还是一个让人扭曲规则的谜题……如果是后者,那么简单的欺骗可能比复杂但“真实”的解决方案(正如其他人指出的那样,后者只能用于可压缩输入)得到更好的结果。
你用的是哪种电脑?它可能没有任何其他“正常”的本地存储,但它是否有视频RAM,例如?100万像素x每像素32位(比如说)非常接近你所需的数据输入大小。
(我主要是问旧的Acorn RISC PC的内存,如果你选择低分辨率或低颜色深度的屏幕模式,它可以“借用”VRAM来扩展可用的系统RAM !)这在只有几MB普通RAM的机器上非常有用。
Gilmanov的答案在假设上是非常错误的。它开始基于毫无意义的一百万个连续整数进行推测。这意味着没有差距。这些随机的间隙,不管有多小,真的是一个糟糕的主意。
你自己试试。获得100万个27位随机整数,对它们排序,用7-Zip, xz压缩,任何你想要的LZMA。结果超过1.5 MB。上面的前提是连续数字的压缩。即使是增量编码也超过1.1 MB。没关系,这使用了超过100 MB的RAM进行压缩。因此,即使压缩的整数也不适合这个问题,更不用说运行时RAM的使用了。
让我难过的是,人们竟然投票支持漂亮的图像和合理化。
#include <stdint.h>
#include <stdlib.h>
#include <time.h>
int32_t ints[1000000]; // Random 27-bit 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 32 bits 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压缩ints.bin…
$ xz -f --keep ints.bin # 100 MB RAM
$ 7z a ints.bin.7z ints.bin # 130 MB RAM
$ ls -lh ints.bin*
3.8M ints.bin
1.1M ints.bin.7z
1.2M ints.bin.xz
如果输入流可以接收几次,这将是很大的 更简单(没有关于这方面的信息,想法和时间-性能问题)。
然后,我们可以数小数。如果是计数值的话 容易使输出流。通过计算值来压缩。它 这取决于输入流中的内容。
我们有1 MB - 3 KB RAM = 2^23 - 3*2^13位= 8388608 - 24576 = 8364032位可用。
我们给出10^8范围内的10^6个数。这给出了~100 < 2^7 = 128的平均差距
让我们首先考虑一个比较简单的问题,即当所有间距都< 128时,数字间距相当均匀。这很简单。只存储第一个数字和7位空白:
(27位)+ 10^6个7位间隔数=需要7000027位
注意重复的数字间隔为0。
但如果间隔大于127呢?
好吧,让我们直接表示小于127的间隙大小,但是127的间隙大小后面跟着一个连续的8位编码来表示实际的间隙长度:
10xxxxxx xxxxxxxx = 127 .. 16,383
110xxxxx xxxxxxxx xxxxxxxx = 16384 .. 2,097,151
etc.
注意这个数字表示描述了它自己的长度,所以我们知道下一个间隙数何时开始。
对于小于127的小间隙,仍然需要7000027位。
可能有高达(10^8)/(2^7)= 781250个23位的间隙数,需要额外的16* 781250 = 12500,000位,这是太多了。我们需要一个更紧凑和缓慢增加的差距表示。
平均差距大小是100,所以如果我们把它们重新排序 [100, 99, 101, 98, 102,…], 2, 198, 1, 199, 0, 200, 201, 202,…] 然后用密集的二进制斐波那契基编码索引它,没有对零(例如,11011=8+5+2+1=16),数字用“00”分隔,然后我认为我们可以保持足够短的差距表示,但它需要更多的分析。