3 ms·
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.
by jandrese 9y ago
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.
- lostatseajoshua 9y agoI really don’t understand why not caring about the order would save space. Could you explain in simple terms please?
- pavlov 9y agoConsider the simplest case where your set members are just bits. If you have three bits and you care about the order, that's a 3-bit number -- it can take 8 different values. If you have those same bits but you don't care about the order, the operation is a "bit count" -- you can only have 4 different values.
- jandrese 9y agoIf 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.