我有一台有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
当前回答
If the numbers are evenly distributed we can use Counting sort. We should keep the number of times that each number is repeated in an array. Available space is: 1 MB - 3 KB = 1045504 B or 8364032 bits Number of bits per number= 8364032/1000000 = 8 Therefore, we can store the number of times each number is repeated to the maximum of 2^8-1=255. Using this approach we have an extra 364032 bits unused that can be used to handle cases where a number is repeated more than 255 times. For example we can say a number 255 indicates a repetition greater than or equal to 255. In this case we should store a sequence of numbers+repetitions. We can handle 7745 special cases as shown bellow:
364032/(表示每个数字所需的位数+表示100万所需的位数)= 364032 / (27+20)=7745
其他回答
假设这个任务是可能的。在输出之前,内存中会有一个百万个排序数字的表示。有多少种不同的表示法?由于可能有重复的数字,我们不能使用nCr(选择),但有一种叫做multichoose的操作,它适用于多集。
在0..99,999,999范围内有22e2436455种方法来选择一百万个数字。 这需要8,093,730位来表示每个可能的组合,或1,011,717字节。
所以理论上是可能的,如果你能想出一个合理(足够)的数字排序表。例如,一个疯狂的表示可能需要一个10MB的查找表或数千行代码。
但是,如果“1M RAM”意味着100万个字节,那么显然没有足够的空间。事实上,多5%的内存使它在理论上成为可能,这对我来说意味着表示必须非常有效,可能是不理智的。
你最多要数到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位。你只需要用一半!
如果数字的范围是有限的(只能有2个8位数,或者只有10个不同的8位数),那么你可以编写一个优化的排序算法。但如果你想对所有可能的8位数进行排序,这在内存那么少的情况下是不可能的。
排序在这里是次要问题。正如其他人所说,仅仅存储整数是困难的,并且不能在所有输入上工作,因为每个数字需要27位。
我对此的看法是:只存储连续(排序)整数之间的差异,因为它们很可能很小。然后使用压缩方案,例如,每个输入数字增加2位,来编码数字存储在多少位上。 喜欢的东西:
00 -> 5 bits
01 -> 11 bits
10 -> 19 bits
11 -> 27 bits
在给定的内存限制内,应该能够存储相当数量的可能输入列表。如何选择压缩方案以使其在最大输入数量上工作的数学超出了我的范围。
我希望您能够利用输入的领域特定知识,在此基础上找到足够好的整数压缩方案。
哦,然后,当你收到数据时,你对那个排序的列表进行插入排序。
我们可以利用网络堆栈,在我们得到所有数字之前,按顺序发送数字。如果你发送1M的数据,TCP/IP会把它分解成1500字节的数据包,并按照目标发送。每个包将被赋予一个序列号。
我们可以用手来做。在填满内存之前,我们可以对现有的数据进行排序,并将列表发送给目标,但在每个数字周围的序列中留下空洞。然后用同样的方法处理第二个1/2的数字,使用序列中的这些洞。
远端的网络堆栈将按顺序组装结果数据流,然后将其提交给应用程序。
它使用网络来执行归并排序。这是一个完全的黑客,但我是受到之前列出的其他网络黑客的启发。