[deleted]
Show HN: How to store a set of four 5-bit values in one 16-bit value
71–80 of 149 posts
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#72It's pretty cool and all but what are the uses for this? What set of 4 un ordered 5-bit numbers would i need to store that I couldn't just store as 3 bytes? I waste only 4 bits while preserving the order if need be of the values I'm storing. I can think of a very very small few occasions 4 bits would matter over order but nothing realistic. Again It's a cool trick and I'm not trying to be a dick about it. I like cool…
It's 4 5-bit values, not 5 4-bit values. 5-bits is enough to enumerate each bit in a 32-bit bitfield. This means for any application that might set 4 or fewer flags out of a possible 32 need only use a 16-bit bitfield.
As I said in another comment I just tested this with a 32-bit hash array mapped trie, and it would result in a significant reduction in the storage overhead of the trie (which is already more efficient than typical hash tables for map like data structures).
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#73This 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.
A list of deltas should do it. In the worst case, the deltas would use log2[2^32/1000000] * 1000000 bits, so about 1.5 MB. Plus some space because of base 128 encoding (it increases size up to 37/32, rounded up per byte). 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.
How are you encoding the deltas exactly?
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#74Earlier quoted context omitted.
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...
These need random access to use constant memory, he was talking about streaming access
Yeah, I didn't pay attention that you can't really store 1 million 32 bit integers in 2MiB without encoding/compressing them somehow.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#75That 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.
Is there a way to make it work with just make? I'm way too used to just typing make at this point and it's not too much work to just copy the same makefile everywhere.
echo "all: main" > Makefile
make
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#76Earlier quoted context omitted.
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...
His math is right. The factorial already took care of the fact that order does not matter. If you want to optimize storage of duplicates, you still have to store the number of duplicate numbers, and you are back where you started.
The factorial is taking too much care of the fact that order does not matter. If I wanted to store four 1-bit numbers, ajkjk's math would suggest that I need log2(2^4/4!) = -0.58, i.e. a negative number of bits. You can't just divide by 4! because not all combinations of 4 numbers have 4! unique permutations.
> If you want to optimize storage of duplicates, you still have to store the number of duplicate numbers, and you are back where you started.
No, because you can shave off a few bits by ignoring the ordering of the non-duplicates.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#77how are you getting 3876 unique values for a set of 4 4 bit values (16, 16, 16, 16) ?
He doesn't care about the order so 1, 2, 3, 4 is stored the same as 4, 3, 2, 1. That's where the savings is coming from.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#78It is possible to do this in O(1) memory, for arbitrary sized collections, efficiently. 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 b…
I'm pretty sure that computing N choose k requires O(k log N) memory to store the result (for N >> k). Neat trick though.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#79Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#80Conversely: the order for 5 4-bit values itself has 4-bits of information.