5 ms·
Why is the entropy of the sorted list smaller?
by ampdepolymerase 7y ago
Why is the entropy of the sorted list smaller?
- Koshkin 7y agoBecause it's easier to compress (compared to when its contents is in a random order).
- btilly 7y agoThe entropy of a signal is the logarithm base 2 of the number of signals that you could possibly be trying to send. Because with perfect compression, that is how many bits you need to encode that many different signals. Since not all lists are sorted, there are more lists of a given size than sorted lists.
- YetAnotherNick 7y ago1M (ordered) list of numbers < 10^8 requires 3.16MB of RAM(10^6*log_2(10^8) bits). The theoretical lower bound to store unordered numbers is 0.96MB(log_2(comb(10^8+10^6-1, 10^6)) bits. Basically calculating number of different possible types of lists, taking its log is the entropy. Both the lists [1, 2] and [2, 1] are same if we don't want the ordering information. In the second case we just need counts of number with property that count[0] + count[1]+...+count[10^8] = 10^6 as counts give perfect information for the sorted list.