使用1 MB RAM对1百万个8进制数字进行排序 [英] Sorting 1 million 8-decimal-digit numbers with 1 MB of RAM
问题描述
我有一台具有1 MB RAM且没有其他本地存储的计算机。我必须使用它来通过TCP连接接受一百万个8位十进制数字，对它们进行排序，然后通过另一个TCP连接将排序后的列表发送出去。
I have a computer with 1 MB of RAM and no other local storage. I must use it to accept 1 million 8-digit decimal numbers over a TCP connection, sort them, and then send the sorted list out over another TCP connection.
数字列表可能包含重复项，我不能丢弃。该代码将放置在ROM中，因此我不必从1 MB中减去代码的大小。我已经有了驱动以太网端口和处理TCP / IP连接的代码，它的状态数据需要2 KB，包括一个1 KB的缓冲区，代码将通过该缓冲区读写数据。有解决这个问题的方法吗？
The list of numbers may contain duplicates, which I must not discard. The code will be placed in ROM, so I need not subtract the size of my code from the 1 MB. I already have code to drive the Ethernet port and handle TCP/IP connections, and it requires 2 KB for its state data, including a 1 KB buffer via which the code will read and write data. Is there a solution to this problem?
问题和答案来源：
推荐答案
仅由于1兆字节与1百万字节之间的差异，才有可能解决方案。 8093729.5的幂大约有2种，可以选择100万个8位数字（允许重复且顺序不重要），因此，只有100万字节RAM的计算机没有足够的状态来表示所有可能性。但是1M（对于TCP / IP，少于2k）是1022 * 1024 * 8 = 8372224位，因此可以解决。
A solution is possible only because of the difference between 1 megabyte and 1 million bytes. There are about 2 to the power 8093729.5 different ways to choose 1 million 8-digit numbers with duplicates allowed and order unimportant, so a machine with only 1 million bytes of RAM doesn't have enough states to represent all the possibilities. But 1M (less 2k for TCP/IP) is 1022*1024*8 = 8372224 bits, so a solution is possible.
第1部分，初始解决方案
此方法需要超过100万，我将对其进行改进以使其在以后适应100万。
This approach needs a little more than 1M, I'll refine it to fit into 1M later.
我将在0到99999999范围内存储紧凑的数字列表，作为7位数字子列表的序列。第一个子列表保存的数字从0到127，第二个子列表保存的数字从128到255，依此类推。100000000/128恰好是781250，因此需要781250这样的子列表。
I'll store a compact sorted list of numbers in the range 0 to 99999999 as a sequence of sublists of 7-bit numbers. The first sublist holds numbers from 0 to 127, the second sublist holds numbers from 128 to 255, etc. 100000000/128 is exactly 781250, so 781250 such sublists will be needed.
每个子列表由一个2位子列表头和一个子列表主体组成。子列表主体每个子列表条目占用7位。子列表全部串联在一起，并且格式可以告诉一个子列表在哪里结束，下一个开始。完全填充的列表所需的总存储量为2 * 781250 + 7 * 1000000 = 8562500位，大约为1.021 M字节。
Each sublist consists of a 2-bit sublist header followed by a sublist body. The sublist body takes up 7 bits per sublist entry. The sublists are all concatenated together, and the format makes it possible to tell where one sublist ends and the next begins. The total storage required for a fully populated list is 2*781250 + 7*1000000 = 8562500 bits, which is about 1.021 M-bytes.
4个可能的子列表标头值分别是：
The 4 possible sublist header values are:
00 空子列表，什么也没有。
00 Empty sublist, nothing follows.
01 单例，子列表中只有一个条目，接下来的7位保存着它。
01 Singleton, there is only one entry in the sublist and and next 7 bits hold it.
10 2个不同的数字。条目以非降序存储，但最后一个条目小于或等于第一个条目。这样可以确定子列表的末尾。例如，数字2,4,6将存储为（4,6,2）。数字2,2,3,4,4将存储为（2,3,4,4,2）。
10 The sublist holds at least 2 distinct numbers. The entries are stored in non-decreasing order, except that the last entry is less than or equal to the first. This allows the end of the sublist to be identified. For example, the numbers 2,4,6 would be stored as (4,6,2). The numbers 2,2,3,4,4 would be stored as (2,3,4,4,2).
11 子列表包含2个或多个重复的单个数字。接下来的7位给出数字。然后是零个或多个值为1的7位条目，然后是值为0的7位条目。子列表主体的长度决定了重复次数。例如，数字12,12将存储为（12,0），数字12,12,12将存储为（12,1,0），12,12,12,12将存储为（12,1 ，1,0）等。
11 The sublist holds 2 or more repetitions of a single number. The next 7 bits give the number. Then come zero or more 7-bit entries with the value 1, followed by a 7-bit entry with the value 0. The length of the sublist body dictates the number of repetitions. For example, the numbers 12,12 would be stored as (12,0), the numbers 12,12,12 would be stored as (12,1,0), 12,12,12,12 would be (12,1,1,0) and so on.
我从一个空列表开始，读取一堆数字并将其存储为32位整数，并对新数字进行排序就位（可能使用堆排序），然后将它们合并为新的紧凑排序列表。重复直到没有更多的数字可读取，然后再次遍历压缩列表以生成输出。
I start off with an empty list, read a bunch of numbers in and store them as 32 bit integers, sort the new numbers in place (using heapsort, probably) and then merge them into a new compact sorted list. Repeat until there are no more numbers to read, then walk the compact list once more to generate the output.
下面的行表示列表合并开始之前的内存操作。 O是保存排序的32位整数的区域。 X是保存旧压缩列表的区域。 =符号是紧凑列表的扩展空间， O中的每个整数7位。 Z是其他随机开销。
The line below represents memory just before the start of the list merge operation. The "O"s are the region that hold the sorted 32-bit integers. The "X"s are the region that hold the old compact list. The "=" signs are the expansion room for the compact list, 7 bits for each integer in the "O"s. The "Z"s are other random overhead.
ZZZOOOOOOOOOOOOOOOOOOOOOOOOOO==========XXXXXXXXXXXXXXXXXXXXXXXXXX
合并例程在最左边的 O和最左边的 X开始读取，并在最左边开始写入 =。在合并所有新的整数之前，写入指针不会捕获紧凑列表读取指针，因为两个指针对于旧列表中的每个子列表前进2位，对于每个条目前进7位，并且有足够的额外空间来容纳压缩列表读取指针。新数字的7位输入。
The merge routine starts reading at the leftmost "O" and at the leftmost "X", and starts writing at the leftmost "=". The write pointer doesn't catch the compact list read pointer until all of the new integers are merged, because both pointers advance 2 bits for each sublist and 7 bits for each entry in the old compact list, and there is enough extra room for the 7-bit entries for the new numbers.
第2部分，将其塞入1M
要将上述解决方案压缩为1M，我需要使压缩列表格式更紧凑。我将摆脱其中一种子列表类型，以便只有3种可能的子列表标题值。然后，我可以使用 00， 01和 1作为子列表标题值并保存一些位。子列表类型为：
To Squeeze the solution above into 1M, I need to make the compact list format a bit more compact. I'll get rid of one of the sublist types, so that there will be just 3 different possible sublist header values. Then I can use "00", "01" and "1" as the sublist header values and save a few bits. The sublist types are:
一个空的子列表，不包含任何内容。
A Empty sublist, nothing follows.
B Singleton，只有一个条目
B Singleton, there is only one entry in the sublist and and next 7 bits hold it.
C子列表至少包含2个不同的数字。条目以非降序存储，但最后一个条目小于或等于第一个条目。这样可以确定子列表的末尾。例如，数字2,4,6将存储为（4,6,2）。数字2,2,3,4,4将存储为（2,3,4,4,2）。
C The sublist holds at least 2 distinct numbers. The entries are stored in non-decreasing order, except that the last entry is less than or equal to the first. This allows the end of the sublist to be identified. For example, the numbers 2,4,6 would be stored as (4,6,2). The numbers 2,2,3,4,4 would be stored as (2,3,4,4,2).
D子列表包含2个或更多
D The sublist consists of 2 or more repetitions of a single number.
我的3个子列表标头值将为 A， B和 C，所以我需要一种表示D型的方法
My 3 sublist header values will be "A", "B" and "C", so I need a way to represent D-type sublists.
假设我有C型子列表标题，后跟3个条目，例如 C [17] [101] [58]。如上所述，这不能成为有效的C型子列表的一部分，因为第三个条目小于第二个条目，但大于第一个条目。我可以使用这种类型的构造来表示D型子列表。用位来讲，任何我有 C {00 ?????} {1 ??????} {01 ?????}的地方都是不可能的C型子列表。我将用它来表示一个由3个或更多重复的单个数字组成的子列表。前两个7位字对数字（下面的 N位）进行编码，后跟零个或多个{0100001}个字，后跟一个{0100000}个字。
Suppose I have the C-type sublist header followed by 3 entries, such as "C[17][101][58]". This can't be part of a valid C-type sublist as described above, since the third entry is less than the second but more than the first. I can use this type of construct to represent a D-type sublist. In bit terms, anywhere I have "C{00?????}{1??????}{01?????}" is an impossible C-type sublist. I'll use this to represent a sublist consisting of 3 or more repetitions of a single number. The first two 7-bit words encode the number (the "N" bits below) and are followed by zero or more {0100001} words followed by a {0100000} word.
For example, 3 repetitions: "C{00NNNNN}{1NN0000}{0100000}", 4 repetitions: "C{00NNNNN}{1NN0000}{0100001}{0100000}", and so on.
这只剩下只包含2个重复数的列表。我将用另一个不可能的C型子列表模式来代表它们： C {0 ??????} {11 ??????} {10 ?????}。前2个单词中的7位数字有足够的空间，但是此模式比它所代表的子列表更长，这使事情变得更加复杂。可以将结尾处的五个问号视为模式的一部分，因此我将 C {0NNNNNN} {11N ????} 10作为我的模式，并将要重复的数字存储在 N中的。这太长了2位。
That just leaves lists that hold exactly 2 repetitions of a single number. I'll represent those with another impossible C-type sublist pattern: "C{0??????}{11?????}{10?????}". There's plenty of room for the 7 bits of the number in the first 2 words, but this pattern is longer than the sublist that it represents, which makes things a bit more complex. The five question-marks at the end can be considered not part of the pattern, so I have: "C{0NNNNNN}{11N????}10" as my pattern, with the number to be repeated stored in the "N"s. That's 2 bits too long.
我将不得不借用2位并从此模式中的4个未使用位中偿还它们。读取时，遇到 C {0NNNNNN} {11N00AB} 10时，输出2个以 N表示的数字实例，在末尾用位A和B覆盖 10，并将读指针后退2位。对于该算法，破坏性读取是可行的，因为每个紧凑列表仅被遍历一次。
I'll have to borrow 2 bits and pay them back from the 4 unused bits in this pattern. When reading, on encountering "C{0NNNNNN}{11N00AB}10", output 2 instances of the number in the "N"s, overwrite the "10" at the end with bits A and B, and rewind the read pointer by 2 bits. Destructive reads are ok for this algorithm, since each compact list gets walked only once.
在编写包含单个数字的2个重复的子列表时，请写入 C {0NNNNNN} 11N00，并将借用位计数器设置为2。在每次写入时，借用位计数器为非零值，则写入的每个位都会递减，并且当计数器达到零时将写入 10。因此，接下来写入的2位将进入插槽A和B，然后将 10放到末尾。
When writing a sublist of 2 repetitions of a single number, write "C{0NNNNNN}11N00" and set the borrowed bits counter to 2. At every write where the borrowed bits counter is non-zero, it is decremented for each bit written and "10" is written when the counter hits zero. So the next 2 bits written will go into slots A and B, and then the "10" will get dropped onto the end.
带有3个由 00， 01和 1，我可以将 1分配给最受欢迎的子列表类型。我需要一个小表将子列表标头值映射到子列表类型，并且每个子列表类型都需要一个出现计数器，以便知道什么是最好的子列表标头映射。
With 3 sublist header values represented by "00", "01" and "1", I can assign "1" to the most popular sublist type. I'll need a small table to map sublist header values to sublist types, and I'll need an occurrence counter for each sublist type so that I know what the best sublist header mapping is.
当所有子列表类型都同样受欢迎时，最坏的情况是完全填充的紧凑列表的最小表示形式出现。在那种情况下，我为每3个子列表标题保存1位，因此列表大小为2 * 781250 + 7 * 1000000-781250/3 = 8302083.3位。舍入到32位字边界，即8302112位或1037764字节。
The worst case minimal representation of a fully populated compact list occurs when all the sublist types are equally popular. In that case I save 1 bit for every 3 sublist headers, so the list size is 2*781250 + 7*1000000 - 781250/3 = 8302083.3 bits. Rounding up to a 32 bit word boundary, thats 8302112 bits, or 1037764 bytes.
1M减去2k（用于TCP / IP状态），缓冲区为1022 * 1024 = 1046528字节，剩下8764个字节可玩。
1M minus the 2k for TCP/IP state and buffers is 1022*1024 = 1046528 bytes, leaving me 8764 bytes to play with.
但是更改子列表标头映射的过程呢？在下面的内存映射中， Z是随机开销， =是可用空间， X是紧凑列表。
But what about the process of changing the sublist header mapping ? In the memory map below, "Z" is random overhead, "=" is free space, "X" is the compact list.
ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
从最左边的 X开始阅读，并从最左边的 =，然后右移。完成后，压缩列表将变短一些，并且将位于错误的内存末尾：
Start reading at the leftmost "X" and start writing at the leftmost "=" and work right. When it's done the compact list will be a little shorter and it will be at the wrong end of memory:
ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======
所以我需要将它向右分流：
So then I'll need to shunt it to the right:
ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
在标头映射更改过程中，最多1/3的子列表标头将从1位更改为2位。在最坏的情况下，这些都将排在列表的首位，因此在开始之前，我至少需要781250/3位可用存储空间，这使我回到了精简列表的早期版本的内存要求： （
In the header mapping change process, up to 1/3 of the sublist headers will be changing from 1-bit to 2-bit. In the worst case these will all be at the head of the list, so I'll need at least 781250/3 bits of free storage before I start, which takes me back to the memory requirements of the previous version of the compact list :(
为了解决这个问题，我将781250子列表分为10个子列表组，每个子列表包含78125个子列表。每个组都有自己独立的子列表标题映射。使用字母从A到J的组：
To get around that, I'll split the 781250 sublists into 10 sublist groups of 78125 sublists each. Each group has its own independent sublist header mapping. Using the letters A to J for the groups:
ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
在子列表标头映射更改期间，每个子列表组收缩或保持不变：
Each sublist group shrinks or stays the same during a sublist header mapping change:
ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAA=====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字节。
The worst case temporary expansion of a sublist group during a mapping change is 78125/3 = 26042 bits, under 4k. If I allow 4k plus the 1037764 bytes for a fully populated compact list, that leaves me 8764 - 4096 = 4668 bytes for the "Z"s in the memory map.
对于10个子列表标头映射表，30个子列表标头出现计数以及我需要的其他一些计数器，指针和小缓冲区，以及我不注意使用的空间（例如，函数调用返回地址的堆栈空间和局部变量。
That should be plenty for the 10 sublist header mapping tables, 30 sublist header occurrence counts and the other few counters, pointers and small buffers I'll need, and space I've used without noticing, like stack space for function call return addresses and local variables.
第3部分，运行需要多长时间？
如果压缩列表为空，则1位列表头将用于空子列表，列表的起始大小为781250位。在最坏的情况下，列表中每个增加的数字都会增加8位，因此，要将32位数字中的每个数字都放在列表缓冲区的顶部，然后进行排序和合并，则需要32 + 8 = 40位可用空间。在最坏的情况下，更改子列表标头映射会导致2 * 781250 + 7 *条目的空间使用-781250/3位。
With an empty compact list the 1-bit list header will be used for an empty sublist, and the starting size of the list will be 781250 bits. In the worst case the list grows 8 bits for each number added, so 32 + 8 = 40 bits of free space are needed for each of the 32-bit numbers to be placed at the top of the list buffer and then sorted and merged. In the worst case, changing the sublist header mapping results in a space usage of 2*781250 + 7*entries - 781250/3 bits.
通过更改一旦列表中至少有800000个数字，则在进行第五次合并后，生成子列表标头映射，最坏的情况是总共需要进行约3000万个紧凑列表读写操作。
With a policy of changing the sublist header mapping after every fifth merge once there are at least 800000 numbers in the list, a worst case run would involve a total of about 30M of compact list reading and writing activity.
来源：
http://nick.cleaton.net/ramsortsol.html
http://nick.cleaton.net/ramsortsol.html
这篇关于使用1 MB RAM对1百万个8进制数字进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
