在1 MB RAM中排列1百万个8位数字 [英] Sorting 1 million 8-digit numbers in 1 MB of RAM
问题描述
数字列表可能包含重复项，我不能丢弃。代码将被放在ROM中，所以我不需要从1 MB删除我的代码的大小。我已经有代码来驱动以太网端口并处理TCP / IP连接，它的状态数据需要2 KB，包括1 KB的缓冲区，代码将通过该缓冲区读取和写入数据。有没有解决这个问题？
问题和答案的来源：
slashdot.org
只有解决方案是可能的因为1兆字节和100万字节之间的差异。有大约2个功率8093729.5不同的方式来选择100万个8位数字，允许重复并且不重要，所以只有一百万字节的RAM的机器没有足够的状态来表示所有的可能性。但是1M（TCP / IP少2k）是1022 * 1024 * 8 = 8372224位，所以解决方案是可能的。
第1部分，初始解决方案
这种方法需要超过1M的时间，我会将其细化为1M以后。
我将在0到99999999之间存储一个紧凑的排序列表，作为7位数字的子列表序列。第一个子列表保存从0到127的数字，第二个子列表保存数字从128到255等。100000000/128正好是781250，因此需要781250这样的子列表。
每个子列表由一个2位子列表标题和一个子列表体组成。子列表体每个子列表条目占用7位。子列表全部并置在一起，格式使得可以知道一个子列表在哪里结束，下一个开始。完全填充列表所需的总存储量为2 * 781250 + 7 * 1000000 = 8562500位，大约为1.021 M字节。
4个可能的子列表标题值是：
00 空子列表，以下没有。
01 单身人士，子名单中只有一个条目，接下来的7位保留。
10 子列表至少包含2个不同的数字。条目以非递减顺序存储，除了最后一个条目小于或等于第一条目。这允许识别子列表的结尾。例如，2,4,6号将被存储为（4,6,2）。数字2,2,3,4,4将被存储为（2,3,4,4,2）。
11 子列表包含两个或更多个单个数字的重复。接下来的7位给出数字。然后到达零个或多个7位条目，值为1，后跟一个值为0的7位条目。子列表主体的长度指定重复次数。例如，数字12,12将被存储为（12,0），数字12,12,12将被存储为（12,1,0），12,12,12,12将是（12,1 ，1,0）等等。
我从一个空列表开始，读取一堆数字并将其存储为32位整数，排序新数字到位（使用heapsort，可能），然后将它们合并到一个新的紧凑排序列表。重复一遍，直到没有更多的数字读取，然后再步行紧凑列表以生成输出。
下面的代码表示在列表合并开始之前的内存操作。 O是保存排序的32位整数的区域。 X是保存旧压缩列表的区域。 =符号是紧凑列表的扩展空间，O中的每个整数为7位。 Z是其他的随机开销。
ZZZOOOOOOOOOOOOOOOOOOOOOOOO ========== XXXXXXXXXXXXXXXXXXXXXXXXXX
合并例程开始读取最左边的O和最左边的X，并开始写在最左边=。因为两个指针都为每个子列表提前2位，而在旧的压缩列表中的每个条目为7位，所以写入指针不会捕捉紧凑列表读取指针，直到所有新的整数都被合并，并且有足够的额外空间新的号码的7位条目。
第2部分，将其填充到1M
要将上述解决方案压缩为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}字。
例如，3次重复：C {00NNNNN} {1NN0000} {0100000}，4次重复：C {00NNNNN} {1NN0000} {0100001} {0100000}，所以。
这只是保留一个数字完全重复2个列表的列表。我将用另一个不可能的C型子列表模式表示：C {0}} {11}} {10}}。前两个字中的7位数字有足够的空间，但是这种模式比它所代表的子列表更长，这使得事情有点复杂。最后的五个问号可以认为不是模式的一部分，所以我有：C {0NNNNNNN} {11N ????} 10作为我的模式，将要重复的数字存储在N S。这是2位太长。
我必须借用2位，并从这个模式中的4个未使用的位支付。当读取时，在遇到C {0NNNNNN}} {11N00AB} 10时，输出N个数的2个实例，最后用位A和B覆盖10，并将读指针倒带2位。这个算法的破坏性读取是可行的，因为每个紧凑列表只能走一次。
当写入一个单个数字的2个重复的子列表时，写C {0NNNNNN} 11N00，并将借用位设置为2.在借位比特计数器不为零的每次写入中，对于写入的每个位减1，当计数器为零时写入10。因此，写入的下一个2位将进入插槽A和B，然后10将被丢弃到最后。
具有3个子列表标题值，由 00，01和1，我可以将1分配给最受欢迎的子列表类型。我需要一个小表将子列表头值映射到子列表类型，我需要每个子列表类型的事件计数器，以便我知道最好的子列表头映射是什么。
当所有子列表类型同样受欢迎时，出现完全填充的紧凑列表的最坏情况最小表示。在这种情况下，我会为每3个子列表头保存1位，因此列表大小为2 * 781250 + 7 * 1000000 - 781250/3 = 8302083.3位。舍入到32位字边界，即8302112位或1037764字节。
1M减去2k的TCP / IP状态，缓冲区为1022 * 1024 = 1046528字节，留下我的8764字节来玩。
但是，更改子列表标题映射的过程如何？在下面的内存映射中，Z是随机开销，=是可用空间，X是紧凑列表。
ZZZ ===== XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
开始阅读最左边的X并开始写作最左边的=并且正常工作。完成后，紧凑型列表将会稍微缩短一段时间，这将在错误的内存结尾处：
ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX === ====
所以我需要把它分流到右边：
ZZZ ======= XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
在标题映射更改过程中，最多1/3的子列表头将从1位更改为2位。在最糟糕的情况下，这些都将在列表的头部，所以我需要至少781250/3位的免费存储空间才能启动，这需要我回到以前版本的压缩列表的内存要求： （
为了解决这个问题，我将781250个子列表分成10个子列表，分别为78125个子列表，每个组都有自己的独立子列表头映射，使用字母A到J组：
ZZZ ===== AAAAAABBCCCCDDDDDEFEFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJJ/ pre>
每个子列表组在子列表标题映射更改期间缩小或保持不变：
ZZZ ===== AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAA ===== BBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABB ===== CCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCC ====== DDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDD ====== EEEFFFGGG GGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
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个子列表头发生计数以及我需要的其他几个计数器，指针和小缓冲区以及我没有注意到的空间，这对于函数调用返回地址和堆栈空间来说应该是很多的，
第3部分，运行需要多长时间？
使用空的紧凑列表，1位列表头将用于一个空的子列表，并且列表的起始大小将是781250位。在最坏的情况下，列表每增加一个增加8位，因此要放置在列表缓冲区顶部的每个32位数字需要32 + 8 = 40位的可用空间，然后进行排序和合并。在最坏的情况下，更改子列表标题映射会导致2 * 781250 + 7 *条目的空间使用 - 781250/3位。
在列表中至少有80万个数字之后，每五分钟合并后的子列表标题映射，最糟糕的情况是涉及约30M的紧凑列表读写活动。
<来源：
http://nick.cleaton.net/ramsortsol.html
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.
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?
Sources Of Question And Answer:
slashdot.org解决方案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.
Part 1, initial solution
This approach needs a little more than 1M, I'll refine it to fit into 1M later.
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.
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.
The 4 possible sublist header values are:
00 Empty sublist, nothing follows.
01 Singleton, there is only one entry in the sublist and and next 7 bits hold it.
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 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.
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.
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==========XXXXXXXXXXXXXXXXXXXXXXXXXXThe 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.
Part 2, cramming it into 1M
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, there is only one entry in the sublist and and next 7 bits hold it.
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 The sublist consists of 2 or more repetitions of a single number.
My 3 sublist header values will be "A", "B" and "C", so I need a way to represent D-type sublists.
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.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.
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.
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.
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.
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 minus the 2k for TCP/IP state and buffers is 1022*1024 = 1046528 bytes, leaving me 8764 bytes to play with.
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=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXStart 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=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXIn 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 :(
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=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJEach 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=======AAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJThe 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.
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.
Part 3, how long would it take to run?
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.
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.
Source:
http://nick.cleaton.net/ramsortsol.html
这篇关于在1 MB RAM中排列1百万个8位数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
