Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: How to store a set of four 5-bit values in one 16-bit value

github.com

Post reply on HN
Print view View original

61–70 of 149 posts

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#61

Post by sirclueless »

nightcracker wrote: post #37

It 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…

Can you elaborate on the second part? Are you saying you're going to expand the size of the universe by a factor of 2^(k-1) to use as locations of the "bars"?

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#62

Post by mturmon »

londons_explore wrote: post #18
ajkjk wrote: post #6

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...

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.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#63

Post by sirclueless »

joshuamorton wrote: post #42
raphlinus wrote: post #34

Earlier quoted context omitted.

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.

But if I pick my buckets right, I can store only the lsb in each bucket. 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?

You're sort of on the right track, but of course you have to encode those counts very carefully because 1M counts will exceed 2MB of memory unless you work hard.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#64

Post by nightcracker »

sirclueless wrote: post #61
nightcracker wrote: post #37

It 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…

Can you elaborate on the second part? Are you saying you're going to expand the size of the universe by a factor of 2^(k-1) to use as locations of the "bars"?

Yes, the universe is expanded.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#66

Post by yorwba »

sabujp wrote: post #44

how are you getting 3876 unique values for a set of 4 4 bit values (16, 16, 16, 16) ?

It's not the number of sets with at most 4 elements (which would be 1820), it's the number of bags with exactly 4 elements (i.e. the multiplicity of duplicate elements matters).

https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_mul...

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#67

Post by sirclueless »

_wmd wrote: post #39
twouhm wrote: post #35

Earlier quoted context omitted.

So what is the trick?

It's the opening problem from Programming Pearls: http://www.fusu.us/2013/06/bitmap-sort.html (edit: better link)

How is this relevant? A bitmap of size 2^32 is 512MB in size and you only have 2MB of memory.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#68

Post by [deleted] »

jack9 wrote: post #26
londons_explore wrote: post #18

Earlier 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...

The maximum entropy is what is important, to the encoding challenge, as I understood it.

[deleted]

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#69

Post by tveita »

nightcracker wrote: post #37

It 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…

Arithmetic coding will work too, without any special trick to code duplicates.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#70

Post by lalaland1125 »

twouhm wrote: post #35
raphlinus wrote: post #3

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?

The trick is that you only need to store the unordered list of seen integers as your state while you sort. This takes about 1.5MB or so. The reduction in space comes from the fact that you don't have to store the order (for example, you could store the numbers sorted and only record offsets. That saves space because the offsets will be smaller)
Post reply on HN