12

I'm taking a first look at the python language from Python wikibook.

For sets the following is mentioned:

We can also have a loop move over each of the items in a set. However, since sets are unordered, it is undefined which order the iteration will follow.

and the code example given is :

s = set("blerg")

for letter in s:
     print letter

Output:

 r b e l g

When I run the program I get the results in the same order, no matter how many times I run. If sets are unordered and order of iteration is undefined, why is it returning the set in the same order? And what is the basis of the order?

martineau
  • 119,623
  • 25
  • 170
  • 301
palerdot
  • 7,416
  • 5
  • 41
  • 47
  • Order in which the items are stored is unordered, but that will be consistent (atleast in Python 2.x). – thefourtheye Feb 11 '14 at 12:17
  • The order is undefined, but not random. The same set of values, inserted in the same order, will allways show up in the same order – Ricardo Cárdenes Feb 11 '14 at 12:18
  • Ie. the documentation is telling you: "Don't trust things to be in a certain order, because you may be (and will be) surprised". If you need order, then use some customized set (there's such customization for dictionaries). – Ricardo Cárdenes Feb 11 '14 at 12:19

1 Answers1

15

They are not randomly ordered, they are arbitrarily ordered. It means you should not count on the order of insertions being maintained as the actual internal implementation details determine the order instead.

The order depends on the insertion and deletion history of the set.

In CPython, sets use a hash table, where inserted values are slotted into a sparse table based on the value returned from the hash() function, modulo the table size and a collision handling algorithm. Listing the set contents then returns the values as ordered in this table.

If you want to go into the nitty-gritty technical details then look at Why is the order in dictionaries and sets arbitrary?; sets are, at their core, dictionaries where the keys are the set values and there are no associated dictionary values. The actual implementation is a little more complicated, as always, but that answer will suffice to get you most of the way there. Then look at the C source code for set for the rest of those details.

Compare this to lists, which do have a fixed order that you can influence; you can move items around in the list and the new ordering would be maintained for you.

Community
  • 1
  • 1
Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
  • For a particular set, if it is unchanged, set is same as an ordered list ? – palerdot Feb 11 '14 at 12:20
  • @Vader: no it shouldn't :-) It's a jargon term. The meaning of something being undefined by documentation is a common concept in software engineering. It's a shame that each novice programmer first hits it in a different place, but it wouldn't help the rest of us to have it spelled out in full in every piece of documentation in the world every time it's used. – Steve Jessop Feb 11 '14 at 12:20
  • @palerdot: an unordered list with no duplicates. – Martijn Pieters Feb 11 '14 at 12:21
  • Thank you for your answer Martijn, but would it please be possible to clarify what you mean by the second line: the order depends on the insertion and deletion history of the set? This confuses me as I read the first sentence as saying sets are ordered arbitrarily according to the implementation and not insertion order. – user51462 Jul 10 '22 at 23:33
  • @user51462: (very, very late reply): yes, the order is implementation dependent, but the implementation has been stable for a long time now. The implementation is such that the order seen depends on what you have inserted already and if anything was removed. The order should be seen as arbitrary as tracking the exact implementation details for any given exact sequence of values that have been inserted and deleted is going to be tedious. – Martijn Pieters Aug 12 '22 at 16:52