2

I understand the difference between ordered and unordered sets, and I understand why for many purposes, we don't need ordered sets. But all set operations are still possible on ordered sets, and sets have to be stored internally with some order anyway, so why aren't sets ordered by default? Is the performance impact of preserving the order of sets too large?

  • Note that the "ordering" of values in an unordered collection may depend more on insertion order and less (if at all) on the values themselves, which isn't an ordering in the sense usually used (which comes from the mathematical term). – outis Nov 17 '17 at 10:05
  • This question may be considered off-topic, as it isn't about developing a particular program but rather language design. – outis Nov 17 '17 at 10:06
  • @outis I wasn't sure as to the correct sub-site, is there another one that you would suggest? – oulenz Nov 17 '17 at 10:23
4

The point is not that the overhead is particularly large, more that it is there at all.

Language features must always strike a balance of cost-effectiveness. Dictionaries are absolutely fundamental to Python programming, so it would be very bad for them to be even slightly slower than they have to be just to preserve insertion order, when most of the time you don't need ordering. It was the correct decision to discard the insertion order in return for slightly faster access, and leave order-preserving data structure for special classes. If there was another data structure that could do all that a dict can, and dict was a lesser-used wrinkle of the language, things might look different.

  • My counter-argument to that would be: use a more efficient unordered dict datatype for internal dictionaries (just like there's deque to optimise performance in certain other contexts) but let the main user-facing dict datatype preserve order. – oulenz Nov 17 '17 at 10:32
  • 2
    Also, am I right in understanding that the CPython implementation of 3.6 does in fact preserve insertion order for dicts? – oulenz Nov 17 '17 at 10:40
8

You are correct that item are store internally with some order, but this internal order is determined by the hash code of the key, which is what allows retrieval to be so fast. So if a set/dict should be ordered, it would need to maintain a separate internal data structure (say an ordered list of keys) for this.

This would of course increase the size. But perhaps worse, it will affect performance. For example removing an item from a set is an O(1) operation, but if it also have to remove the key from an internal ordered list it would become O(n). Such a cost would be disastrous for some applications. Given that it is pretty rare you need an ordered set, such a trade-off is not be worth it for the standard set/dict types.

7

Your premise is incorrect. As of Python 3.6, dicts remember their insertion order. This was an implementation detail, and was promoted to full language feature in 3.7. In 3.6, for the specific case of **kwargs, order preservation is specifically guaranteed.

  • Yes, I wasn't aware of this when I asked the question, since it's not yet a language feature, just an implementation detail in one implementation. But it seems that at least dictionaries will become ordered long-term, and hopefully also sets. – oulenz Nov 19 '17 at 9:36
  • @oulenz it's no longer an implementation detail, it's required as of Python 3.7 – Boris Aug 22 at 17:27
4

An ordered set is only possible when the elements to be stored have an ordering (i.e. a comparison method) in the first place - but that is not always a given.

The default set/map implementation in most environments nowadays is based on an autoresizing hashtable, which has these advantages:

  • faster
  • uses less memory
  • doesn't require the elements to provide an ordering

sets have to be stored internally with some order anyway

But this internal order doesn't necessarily have any meaning, nor does it stay the same. Indeed, one property of hashtables that sometimes confounds inexperienced developers is that the iteration order, which is based on the internal ordering, can change completely when elements are added (i.e. when a resize is triggered) or between different runs.

  • I don't understand your first remark. We don't need a comparison method, the ordering could just be inherited, e.g. from a list or a string literal {3, 5, 4}. – oulenz Nov 17 '17 at 10:27
  • @oulenz inherited still means there is an ordering. What if there simply is no ordering, conceptually? – Michael Borgwardt Nov 17 '17 at 10:42
  • Why is that relevant? The point is that we can always choose an ordering (as long as we don't allow uncountable sets). Just use the initial internal ordering if no other ordering is available from the context. – oulenz Nov 17 '17 at 10:46
  • 2
    @oulenz: if you don't mind the ordering being meaningless and varying over time, then every set is ordered, because there will be some kind of iteration order. But "ordered set" implies that the ordering is semantic for the elements, and that is not always possible. I don't really understand why you want all sets to be ordered. – Michael Borgwardt Nov 17 '17 at 15:16
  • "Ordered set" does not imply that the ordering is semantic, just that there is some ordering. Of course I do care that once this ordering is established, it is preserved, unless its contents are modified. – oulenz Nov 17 '17 at 15:20
1

The general idea behind a set or a dictionary is that you plan to be performing a lot of lookup operations. It is optimized for said lookup operations by using a hash which allows O(1) lookup in most cases.

Order is done using arrays or linked lists and in fact performing operations where order is important, they are optimized for that such as appending a value at the end or beginning.

By the nature of these two data structures, neither is optimized for both. This isn't to say it isn't possible, but it involves both data structures if you want both lookup and order-based operations to be optimized.

So you have this tradeoff between:

lookup operation optimization <=> order-based operations <=> memory usage

The general consensus is that as a programmer, you generally want to optimize for one or the other but not both, and certainly nobody advocates doubling your memory usage when you only need to optimize one of the two.

That said, there are implementations with both, or at least in Java, specifically LinkedHashMap is both an array and a hash-based dictionary. Sometimes you may need both, but it is adviced to use ArrayList if you only need a list and a HashMap if you only need a dictionary.

  • Huh? A Java LinkedHashMap is not "both an array and a hash-based dictionary". It's basically a HashMap (i.e. uses an array internally) superimposed with a linked list to allow iteration in insertion order. – Michael Borgwardt Nov 17 '17 at 15:19
  • Linear data structures aren't the only ordered data structures; binary trees can also be ordered (such as red-black and AVL trees,). Another operation that can be involved in the trade-off is insertion (arrays are quite efficient in terms of lookup, iteration and memory usage, but slowest when it comes to insertion). – outis Nov 17 '17 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.