Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM
by dpark on Monday October 22, 2012 @09:54AM
(#4683107)
> 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.
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.