使用1 MB RAM对1百万个8位十进制数字进行排序
我有一台具有1 MB
RAM且没有其他本地存储的计算机。我必须使用它来通过TCP连接接受一百万个8位十进制数字，对它们进行排序，然后通过另一个TCP连接将排序后的列表发送出去。
数字列表可能包含重复项，我不能丢弃。该代码将放置在ROM中，因此我不必从1 MB中减去代码的大小。我已经有了驱动以太网端口和处理TCP /
IP连接的代码，它的状态数据需要2 KB，包括一个1 KB的缓冲区，代码将通过该缓冲区读写数据。有解决这个问题的方法吗？
slashdot.org
cleaton.net
回答：
仅由于1兆字节和1百万字节之间的差异，才可能找到解决方案。8093729.5的幂大约有2种，可以选择100万个8位数字（允许重复且顺序不重要），因此一台仅具有100万字节RAM的计算机没有足够的状态来表示所有可能性。但是1M（对于TCP
/ IP，小于2k）是1022 * 1024 * 8 = 8372224位，因此可以解决。
这种方法所需的资源略高于1M，我将对其进行改进以适应以后的100万。
我将数字的紧凑排序列表存储在0到99999999之间，作为7位数字子列表的序列。第一个子列表保存从0到127的数字，第二个子列表保存从128到255的数字，依此类推。100000000/128恰好是781250，因此需要781250这样的子列表。
每个子列表由一个2位子列表标头和一个子列表主体组成。子列表主体每个子列表条目占用7位。子列表全部串联在一起，其格式使得可以知道一个子列表在哪里结束，下一个开始。完全填充的列表所需的总存储量为2
* 781250 + 7 * 1000000 = 8562500位，大约为1.021 M字节。
4个可能的子列表标头值为：
空的子列表，什么也没有。
Singleton，子列表中只有一个条目，接下来的7位保存该条目。
子列表至少包含2个不同的数字。条目以非降序存储，但最后一个条目小于或等于第一个条目。这样可以确定子列表的末尾。例如，数字2,4,6将存储为（4,6,2）。数字2,2,3,4,4将存储为（2,3,4,4,2）。
子列表包含一个数字的2个或更多重复。接下来的7位给出数字。然后是零个或多个值为1的7位条目，然后是值为0的7位条目。子列表主体的长度决定了重复次数。例如，数字12,12将存储为（12,0），数字12,12,12将存储为（12,1,0），12,12,12,12将存储为（12,1
，1,0）等。
我从一个空列表开始，读入一堆数字并将其存储为32位整数，将新数字排序到位（可能使用堆排序），然后将它们合并为新的紧凑排序列表。重复直到没有更多的数字可读取，然后再次遍历压缩列表以生成输出。
下面的行表示列表合并操作开始之前的内存。“ O”是保存排序的32位整数的区域。“ X”是保存旧压缩列表的区域。“ =”符号是紧凑列表的扩展空间，“
O”中的每个整数7位。“ Z”是其他随机开销。
ZZZOOOOOOOOOOOOOOOOOOOOOOOOOO==========XXXXXXXXXXXXXXXXXXXXXXXXXX合并例程从最左边的“ O”和最左边的“ X”开始读取，并从最左边的“
=”开始写入。在合并所有新的整数之前，写入指针不会捕获紧凑列表读取指针，因为两个指针对于旧子压缩列表中的每个子列表前进2位，对于每个条目前进7位，并且有足够的额外空间来容纳压缩列表读取指针。新数字的7位输入。
要将上述解决方案压缩为1M，我需要使压缩列表格式更紧凑。我将摆脱一种子列表类型，以便只有3种可能的子列表标头值。然后，我可以使用“ 00”，“ 01”和“
1”作为子列表标题值并保存一些位。子列表类型为：
一个空的子列表，什么也没有。
B Singleton，子列表中只有一个条目，接下来的7位保存该条目。
C子列表至少包含2个不同的数字。条目以非降序存储，但最后一个条目小于或等于第一个条目。这样可以确定子列表的末尾。例如，数字2,4,6将存储为（4,6,2）。数字2,2,3,4,4将存储为（2,3,4,4,2）。
D子列表由2个或多个重复的单个数字组成。
我的3个子列表标头值将为“ A”，“ B”和“ C”，因此我需要一种表示D型子列表的方法。
假设我有C型子列表标头，后跟3个条目，例如“ C [17] [101]
[58]”。如上所述，这不能成为有效C类型子列表的一部分，因为第三个条目小于第二个条目，但大于第一个条目。我可以使用这种类型的构造来表示D型子列表。用位来讲，任何我有“
C {00 ?????} {1 ??????} {01
?????}”的地方都是不可能的C类型子列表。我将用它来表示一个由3个或更多重复的单个数字组成的子列表。前两个7位字对数字进行编码（下面的“
N”位），后跟零个或多个{0100001}字，后跟一个{0100000}字。
For example, 3 repetitions: "C{00NNNNN}{1NN0000}{0100000}", 4 repetitions: "C{00NNNNN}{1NN0000}{0100001}{0100000}", and so on.剩下的列表只包含一个数字的2个重复。我将用另一个不可能的C类型子列表模式来代表它们：“ C {0 ??????} {11 ??????} {10
?????}”。前两个字中的数字的7位有足够的空间，但是此模式比它表示的子列表更长，这使事情变得更加复杂。可以将结尾处的五个问号视为模式的一部分，因此我将“
C {0NNNNNN} {11N ????} 10”作为我的模式，并将要重复的数字存储在“ N”中的。那太长了2位。
在这种模式下，我将不得不借用2个比特并从4个未使用的比特中偿还它们。读取时，遇到“ C {0NNNNNN} {11N00AB} 10”时，输出2个以“
N”表示的数字实例，在末尾用位A和B覆盖“ 10”，然后将读取指针后退2位。此算法可以进行破坏性读取，因为每个紧凑列表仅被遍历一次。
当写一个包含2个重复的子列表时，写“ C {0NNNNNN}
11N00”并将借位计数器设置为2。在每次写时借位计数器为非零值时，写入的每个位都会递减，当计数器为零时，将写入“
10”。因此，接下来写入的2位将进入插槽A和B，然后将“ 10”放到末尾。
使用“ 00”，“ 01”和“ 1”表示的3个子列表标题值，我可以将“
1”分配给最受欢迎的子列表类型。我需要一个小表来将子列表标头值映射到子列表类型，并且我需要每种子列表类型的出现计数器，以便知道最佳的子列表标头映射是什么。
最糟糕的情况是，当所有子列表类型都同样流行时，会出现完全填充的紧凑列表的最小表示形式。在那种情况下，我为每3个子列表标题保存1位，因此列表大小为2 *
781250 + 7 * 1000000-781250/3 = 8302083.3位。舍入到32位字边界，即8302112位或1037764字节。
1M减去TCP / IP状态的2k，缓冲区为1022 * 1024 = 1046528字节，剩下8764字节可用来玩。
但是，更改子列表标头映射的过程呢？在下面的内存映射中，“ Z”是随机开销，“ =”是可用空间，“ X”是压缩列表。
ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX从最左边的“ X”开始阅读，并从最左边的“ =”开始书写，然后向右工作。完成后，压缩列表将短一些，并且将位于错误的内存末尾：
ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======因此，我需要将其右移：
ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX在头映射更改过程中，多达1/3的子列表头将从1位更改为2位。在最坏的情况下，这些都将排在列表的首位，因此在开始之前，我至少需要781250/3位可用存储空间，这使我回到了精简列表的早期版本的内存要求：
（
为了解决这个问题，我将781250个子列表分为10个子列表，每个子列表包含78125个子列表。每个组都有自己的独立子列表标头映射。对组使用字母A到J：
ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ在子列表标头映射更改期间，每个子列表组都会缩小或保持不变：
ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJZZZAAAAAA=====BBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABB=====CCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCC======DDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDD======EEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEE======FFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFF======GGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGG=======HHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHH=======IJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHI=======JJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ=======
ZZZ=======AAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
在映射更改期间，子列表组的临时扩展的最坏情况是78125/3 =
26042位，小于4k。如果我为完全填充的压缩列表允许4k加上1037764字节，则将内存映射中的“ Z”留给我8764-4096 = 4668字节。
对于10个子列表标头映射表，30个子列表标头出现计数以及我需要的其他一些计数器，指针和小缓冲区，以及我不注意使用的空间（例如，函数调用返回地址的堆栈空间和局部变量。
如果列表为空，则1位列表头将用于一个空子列表，列表的起始大小为781250位。在最坏的情况下，列表中每个增加的数字都会增加8位，因此，要将32位数字中的每个数字都放在列表缓冲区的顶部，然后进行排序和合并，则需要32
+ 8 = 40位可用空间。在最坏的情况下，更改子列表标头映射会导致2 * 781250 + 7 *条目-781250/3位的空间使用。
如果在列表中至少有80万个数字之后，每五次合并后更改子列表标头映射的策略，最坏的情况将涉及总共约30M的紧凑列表读写活动。
以上是 使用1 MB RAM对1百万个8位十进制数字进行排序 的全部内容， 来源链接： utcz.com/qa/419509.html
