31–40 of 149 posts
This is quite related to the problem of sorting a million 32 bit integers using only 2M of RAM (and no disk). It can be done.
If I only have 8 bytes of ram and a program counter I can do it... For (I=0; I Shoddy runtime, but hey...
Earlier quoted context omitted.
To answer the obvious next question: Four 5-bit values in order have 20 bits of entropy, so cannot be stored in 16 bits. Four 5-bit values without order have 20 - log2(4!) =~ 20 - 4.59 = 15.41 bits of entropy (corresponding to log(2^20/4!) possible configurations), and thus can fit in 16 bits of data if you're clever about it.
Your math is wrong. If two of the numbers happen to be the same, order no longer matters for those numbers, so your log2(4!) needs to be larger...
log2((32*31*30*29)/(4*3*2) + (32*31*30)/2 + (32*31) + (32*31)/2) = 15.675
which is still smaller than 16.Earlier quoted context omitted.
If I only have 8 bytes of ram and a program counter I can do it... For (I=0; I Shoddy runtime, but hey...
Yes, this is a problem that requires careful specification. You only get streaming access to your input, not random.
Earlier quoted context omitted.
Yes, this is a problem that requires careful specification. You only get streaming access to your input, not random.
Couldn't you just do that with radix sort or am I missing something?
This is quite related to the problem of sorting a million 32 bit integers using only 2M of RAM (and no disk). It can be done.
That is one big-ass makefile though. I realize it has some extra niceties but I have to ask, did you ever try make main without any makefile at all? If you haven't done so, delete the makefile now (you have it in version control anyway) and give it a try.
The first trick is to make a function that can calculate the nth set with k elements from some universe U (in this case U = {0..2^5-1} without order (no duplicates) directly. This is done using the https://en.wikipedia.org/wiki/Combinatorial_number_system. This is very efficient.
Then, to encode duplicates you use the stars and bars trick.
This is quite related to the problem of sorting a million 32 bit integers using only 2M of RAM (and no disk). It can be done.
I got a worst case of exactly 2 MB (1.907 MiB) (all deltas being 4294, so the list is 0, 4294, 8588...), but maybe it's possible to get better than that.
It would be uber slow though, probably n^2.
This is quite related to the problem of sorting a million 32 bit integers using only 2M of RAM (and no disk). It can be done.
So what is the trick?
(edit: better link)
This is quite related to the problem of sorting a million 32 bit integers using only 2M of RAM (and no disk). It can be done.