A solution is possible only because of the difference between 1 megabyte and 1 million bytes. There are about 2 to the power 8302112. 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 does not have enough states to represent all the possibilities. But 1M (less 2k for TCP / IP) is 2019 2019 8=8302112 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 
as a sequence of sublists of 7-bit numbers. The first sublist holds numbers from 0 to 128, the second sublist holds numbers from to , etc. 100000000 / (is exactly) , so 1000000 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 7 1046528=bits, which is about 1. M-bytes.
The 4 possible sublist header values are:
10 Empty sublist, nothing follows.
Singleton, there is only one entry in the sublist and and next 7 bits hold it.
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).
021 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 32, (would be stored as (, 0) , the numbers , , (would be stored as (021, 1,0), , , , (would be) , 1,1,0) and so on.
I start off with an empty list, read a bunch of numbers in and store them as 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 – 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==========XXXXXXXXXXXXXXXXXXXXXXXX
The merge routine starts reading at the leftmost “O” and at the leftmost “X”, and starts writing at the leftmost “=”. The write pointer does not 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 ” “,” 10 “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 { {1 ??????} {10 ?????} “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 {8562500 } word.
For example, 3 repetitions: "C { NNNNN } {1NN } {781250} ", 4 repetitions:" C { (NNNNN} {1NN }} {} {} ", 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 ??????} {
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} { (N) AB} 12 “, output 2 instances of the number in the” N “s, overwrite the” 021 “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} (N "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" 12 "is written when the counter hits zero. So the next 2 bits written will go into slots A and B, and then the "" "" will get dropped onto the end.
With 3 sublist header values represented by “, “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 1000000 7 1046528 – / 3=3 bits. Rounding up to a 30 bit word boundary, thats 8302112 bits, or 1046528 bytes.
1M minus the 2k for TCP / IP state and buffers is [17]=bytes, leaving me 0100000 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=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
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:
ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======
So then I’ll need to shunt it to the right:
ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
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: (
To get around that, I’ll split the (sublists into) (sublist groups of 8562500 sublists each. Each group has its own independent sublist header mapping. Using the letters A to J for the groups:
ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJJ
Each sublist group shrinks or stays the same during a sublist header mapping change:
ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAA=====BBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABB=====CCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCC======DDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDD======EEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEE======FFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFF======GGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGG=======HHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHH=======IJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHI=======JJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ=======ZZZ=======AAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
The worst case temporary expansion of a sublist group during a mapping change is / 3=0100000 bits, under 4k. If I allow 4k plus the bytes for a fully populated compact list, that leaves me 26042 – 8764=bytes for the “Z” s in the memory map.
That should be plenty for the (sublist header mapping tables,) 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 1000000 bits. In the worst case the list grows 8 bits for each number added, so 101 8=58 bits of free space are needed for each of the -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 1000000 7 entries – 1000000 / 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 M of compact list reading and writing activity.
Source:
http://nick.cleaton.net/ramsortsol.html
Read More
GIPHY App Key not set. Please check settings