41–50 of 149 posts
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.
Is there a specific topic of study that taught you those formulas?
Earlier quoted context omitted.
Couldn't you just do that with radix sort or am I missing something?
Yes, you're missing something. Radix sort, like most sorting algorithms, requires storing the intermediate results in memory. This problem seems impossible at first blush because storing 1 million 4-byte integers would seem to require 4M of RAM, and only 2M is available.
Or more efficient, dynamically construct an implicit trie/heap type thing, where each leaf is the count of times that int appears (and the int itself is encoded in the location)
That feels really, really handwavy but promising?
Earlier quoted context omitted.
Hmm, it's interesting to me that order would be expected. I nearly always think of storage and ordering as entirely separate problems.
Usually, when you store a value, you want to be able to get exactly that value back. If you store multiple values without keeping the ordering, you lose that capability. I.e. you can't replace all possible uses of four 5-bit variables with one 16-bit variable, only those where the variables are interchangeable.
Slightly adrift of the topic...
I have a HAMT (hash array map trie) implementation that uses a 32-bit unsigned int as a bitfield to indicate which of the 32 possible children nodes are populated. With this trick I could encode any node with 5 or fewer bits flagged with a 16-bit unsigned int instead.
I just checked and 1 million keys created roughly 1.3 million nodes (1 million keys, 300k internal nodes). Nearly 90% of the 300k internal nodes have 5 or fewer bits set. This trick would make the HAMT overhead nearly half the size.
Very useful!
Now, how about 6-bit values in one 32-bit value? I'd like to try this with a 64-bit HAMT. Can this be easily generalized?
Edit: Oops, that should be nodes with 4 or fewer bits set, there are only 4, 5-bit values. Interestingly that apparently doesn't make much of a difference for HAMTs only about 2k internal nodes out of 300k have 5 children. So the results remain the same.
Ah, without preserving order. That's a set of four 5-bit values, not a sequence of four 5-bit values.
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.
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.
[deleted]
Earlier quoted context omitted.
Couldn't you just do that with radix sort or am I missing something?
Yes, you're missing something. Radix sort, like most sorting algorithms, requires storing the intermediate results in memory. This problem seems impossible at first blush because storing 1 million 4-byte integers would seem to require 4M of RAM, and only 2M is available.
You're right, that does sound impossible. :O
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.
Sure, just pick a sorting algorithm that uses constant memory and the optimal O(n lg n) time complexity: https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o...
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.
Heh, that big ass makefile is the generic makefile [1] I came up with a few years ago. Definitely a bit of overkill for a single file project, but some of us are lazy when it comes to such things. [1]: https://github.com/mbcrawfo/GenericMakefile