4 ms·
Yes, the other commenter ChuckMcM showed one https://news.ycombinator.com/item?id=4680259 https://news.ycombinator.com/item?id=4680259 An ordering of a storag
by uvdiv 14y ago
Yes, the other commenter ChuckMcM showed one
https://news.ycombinator.com/item?id=4680259 https://news.ycombinator.com/item?id=4680259
An ordering of a storage scheme doesn't always store information. E.g. if the list is sorted, the ordering is completely determined by the data -- it's redundant.
For storing integers, an idea to is store the pairwise differences between sorted elements. E.g. [30,10,20] -> [10-0,20-10,30-20] = [10,10,10]. If you have N integers of typical size X, the differences will be much smaller, typically on the scale of X/N. With variable-width integers, X/N takes lg(N) fewer bits to encode than X. So you save N lg(N) bits (asymptotically the same as lg(N!)), compared to storing the integers literally.
- dpark 14y ago> Yes, the other commenter ChuckMcM showed one I saw that comment. I'm not clear how that's not still storing ordered data, or rather how the order there is not storing information. Obviously my information theory knowledge is weak. > if the list is sorted, the ordering is completely determined by the data -- it's redundant. I don't understand this. In what way is the information redundant? If there's 3.17 MB of data in the ordered list, and 2.2 MB of data in the ordering itself, the information stored in the ordering cannot be redundant, because that would mean >4.4MB of information is stored in the ordered list.