使用 1 MB RAM 对 100 万个 8 位十进制数字进行排序 [英] Sorting 1 million 8-decimal-digit numbers with 1 MB of RAM
问题描述
我有一台具有 1 MB RAM 且没有其他本地存储的计算机.我必须使用它通过 TCP 连接接受 100 万个 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 中，所以我不需要从 1MB 中减去我的代码大小.我已经有了驱动以太网端口和处理 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兆字节和100万字节的区别才有可能解决.大约有 2 次方 8093729.5 种不同的方法来选择 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 部分，初步解决方案
这种方法需要1M多一点，我稍后会改进它以适应1M.
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，子列表中只有一个条目，接下来的 7 位保存它.
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"作为我的模式，要重复的数字存储在Ns.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"，输出N"中数字的2个实例，用位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.
使用00"、01"和1"表示的 3 个子列表标题值，我可以将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 减去 TCP/IP 状态和缓冲区的 2k 为 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*entries - 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 个数字，则每五次合并后更改子列表标头映射的策略，最坏的情况下运行将涉及总共约 30M 的紧凑列表读取和写入活动.
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强>
这篇关于使用 1 MB RAM 对 100 万个 8 位十进制数字进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
