Building data structures that are smaller than an array and faster (in C)

Re:Building data structures that are smaller than an array a... by nadam on Thursday March 01, 2012 @04:56AM (#3651550)

What kind of compressed data structure I would use depends heavily on so much things (the probability distribution of the data, the probability distribution of different access patterns) that it is very hard to design a data structure for a generic case. Designing for a specific use case is a lot of fun though!

For example this: "Use less memory than an array in all circumstances" is just plain impossible if your data distribution is uniform. You just cannot store 1000 32 bit random intergers (preserving their order) in a smaller place than 1000*32 bits; (it comes from from simple combinatorics considerations.)

[ Parent | on HN ]

Re:Building data structures that are smaller than an array a... by alexgartrell on Thursday March 01, 2012 @12:13PM (#3652971)

I agree with your point 100%, but if they're sorted you could probably just store the deltas an then use something like the varints that google protocol buffers to compress those deltas down from 32 bits (with a thousand of them, you are guaranteed that some of the deltas will be less than 22 bits because 1000 * 2^22 > 2^32).

With custom compression, where there's a will there's generally a way :)

[ Parent | on HN ]