Any reason why store last 4 bits as is and not just making a LUT out of 4 sorted 5-bit values?
Show HN: How to store a set of four 5-bit values in one 16-bit value
141–149 of 149 posts
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#142Earlier quoted context omitted.
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.
I really don’t understand why not caring about the order would save space. Could you explain in simple terms please?
If you care about the order then
1, 2, 3, 4 has to be stored differently than 4, 3, 2, 1, as well as 1, 3, 2, 4, and so on.
If you don't care about the order all of those can be stored in exactly the same way. Think of it like lossy compression, if you don't care about some of the detail you an ignore it (the order of the numbers in this case) and save some space.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#143De Brujin Sequences
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#144Earlier quoted context omitted.
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 c…
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.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#145Earlier quoted context omitted.
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.
The idea is good, but base128 won't work. The worst case scenario is around 250k offsets of 2^14 (requiring 3 bytes each) and 750k offsets of 2^7 (requiring 2 bytes each). That's 2.25 MB
That's true. A 5 bits header before each number that specifies how many bits a number uses would be enough.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#146Earlier quoted context omitted.
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?
Say the first number is 100, then the following one is 300, then 1000. You'd encode [100, 200, 700].
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#147Why is this first line true: "This works because there are 3876 possible unique values for a set of 4 4 bit values" Each 4 bit number has 16 possible values. And you can order them in the set in 4! = 24 ways. So I thought you would get 24 * 16 = 384. Can someone explain?
They're taking the multiset [0]. So it's \binom{2^4 + 4 - 1}{4} = 3876 In other words, there are 3876 multisets of cardinality 4 with elements taken from the set containing all 4 bit values. [0] https://en.wikipedia.org/wiki/Multiset
Can you explain the top number (2^4 + 4 - 1)?
I understand the bottom number 4 is probably because you're choosing 4 values out of the set of numbers from the top, but not sure how you got 2^4 + 4 - 1.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#148Earlier quoted context omitted.
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 c…
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.…
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.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#149Earlier quoted context omitted.
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.…
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 wh…
I'll add HAMT and tries to my reading list, thanks.