Hacker News Reader

Comment by amptorn | Hacker News Reader

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.

Is there a specific topic of study that taught you those formulas?

Not the person you asked but

4! is the number of permutations of a list - it's commonly seen throughout CS theory and other forms of discrete math.

log_2(n) is the number of bits needed to store a integer from 0 to n - it's reasonably commonly used in CS theory education.

Probability theory and information theory.

As cameldrv said, information theory. The late David MacKay has a good free book:

http://www.inference.org.uk/itprnn/book.html

The intro chapters cover the topic of measuring informational entropy.

Aside: One interesting application is to the problem of “use a balance scale only three times to determine which of twelve balls has the wrong weight (too heavy or light)”. You choose the weighings so as as to maximize the entropy of the outcome i.e. so there are many possible outcomes of equal probability.

try combinatorics branch of mathematics

https://en.wikipedia.org/wiki/Information_theory

As others have mentioned, it comes up in information theory, or maybe in some subfields of combinatorics and probability. I learned it tangentially in various parts of physics.

But I might just recommend going to the source! which is Claude Shannon's seminal masters thesis on coding: http://affect-reason-utility.com/1301/4/shannon1948.pdf . It's surprisingly readable and worth at least skimming if you like this stuff.

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.

Right. So the true answer is

    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.

Are you sure you don't mean

   log2((32*31*30*29)/(4*3*2*1) + (32*31*30)/(3*2*1) + (32*31)/(2*1) + 32/1) = 15.34

using the number of sets of values from {0, 2^5-1} with at most 4 elements?

If on the other hand you want to store exactly 4 values, possibly with duplicates (while still ignoring order), you need to count multisets ( https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_mul... )

  log2( (35*34*33*32)/(4*3*2*1) ) = 15.676

The second answer, 15.676, is the correct one. It can also be arrived at by:

log2(32C4 + 32C3 * 3 + 32C2 * 3 + 32C1)

I followed the original link as well as this calculation. Why not use this to map them directly (instead of breaking it into 12 bits and 4 bits) ? We'll just have some unused headroom in 16 bits. This would seem more natural than thinking of the 12 + 4 solution.

It uses more memory.

What the parent message did is: log2(32+4-1 C 4), because the number of k-sized combinations of n objects with repetitions is (n+k-1)Ck. One way to prove it is that you sort the objects (so you can establish an order among the objects in the combination) and add k-1 dummy objects for "the second is the same as the first, the third is the same as the second,..., the last is the same as the penultimate".

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.

You’re right, correction appreciated.

Actually the log2(4!) needs to be smaller, because as yorwba below says, duplicates don't have 24 permutations.

Does this implementation allow duplicates? Typically a set is defined as an unordered collection with no duplicate items.

[deleted]

They're not ordered: that's the whole point.

My bad, I misread!

Well, the title literally says "a set of" and "not a sequence of".

Yup so no ARGB5555 16 bit type :-)

But an MSAA 4-fragment each 5-bit 16-bit type.

Or MSAA4x ARGB5555 in 64-bit (instead of 80 bit)

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.

Many common data structures fail to preserve order. Maps (aka dictionaries) based on hash tables come to mind.

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.

I believe, based on the math, that 6 6-bit values barely don't fit in 32 bits. :(

The number of bags of k N-bit numbers is 2^N + k - 1 choose k:

https://en.wikipedia.org/wiki/Multiset#Counting_multisets

The number of bits required to uniquely represent such a bag is thus ⌈log2((2^N+k-1) choose k)⌉. For (N, k) we have:

(6, 6) -> ⌈log2(69 choose 6)⌉ = ⌈log2(119877472)⌉ = 27 bits (6, 7) -> ⌈log2(70 choose 7)⌉ = ⌈log2(1198774720)⌉ = 31 bits

So you can store seven 6-bit integers without order in one int32. I don't know if it'll be slow, though. It should be possible to infer an encoding algorithm from the proof of the counting formula but it might be slow.

My understanding is you can't tell order using this trick. I guess the bitmap is just an optimization to skip the hash lookup? Order doesn't matter for you?

Something I came up with is packing the pointers/values into a contiguous array and using the bitfield to tell not only if it's present, but what offset is at (mask + popcnt) * size of(value). This eliminates wasted space due to unused buckets in the hash table. I'm sure it's been done before, but I haven't seen it anywhere.

How's your Go? Want a remote contact doing Go microservices that pays very well? Email is in my profile.

That's pretty much exactly how hash array mapped tries work.

Take the first 5 bits of a 32 bit hash, use it to set a flag in the bitfield, a populated field indicates a populated child array element, find out which one using popcnt. When you find a conflict on insert take a step down the tree, use the next 5 bits in the 32 bit hash rinse and repeat.

A HAMT is the basis of a fully concurrent data structure for maps which can also do fast atomic snapshots called a ctrie.

I'll add HAMT and tries to my reading list, thanks.

Reply on news.ycombinator.com