41

Why does the iteration order of a Python set (with the same contents) vary from run to run, and what are my options for making it consistent from run to run?

I understand that the iteration order for a Python set is arbitrary. If I put 'a', 'b', and 'c' into a set and then iterate them, they may come back out in any order.

What I've observed is that the order remains the same within a run of the program. That is, if my program iterates the same set twice in a row, I get the same order both times. However, if I run the program twice in a row, the order changes from run to run.

Unfortunately, this breaks one of my automated tests, which simply compares the output from two runs of my program. I don't care about the actual order, but I would like it to be consistent from run to run.

The best solution I've come up with is:

  1. Copy the set to a list.
  2. Apply an arbitrary sort to the list.
  3. Iterate the list instead of the set.

Is there a simpler solution?

Note: I've found similar questions on StackOverlow, but none that address this specific issue of getting the same results from run to run.

3
  • If what you're testing is that 'the program outputs the same thing both times', the sorted list option is your best bet. If what you're testing is that 'the program creates the same set both times', you'll need to do a set comparison (by pickling the output of both runs, then unpickling the output of both and set-comparing those, or something morally equivalent). Oct 3, 2010 at 1:28
  • @Russell: I have unit tests that verify the set contents. But I also have this test that compares the output from two runs as a sanity check. The output is dependent, in part, on the order of the items in a set, but only in a roundabout way. Oct 3, 2010 at 15:26
  • Set iteration order is still variable, even now that Python dicts are ordered in insertion order. Aug 12, 2022 at 17:11

7 Answers 7

34

The reason the set iteration order changes from run-to-run appears to be because Python uses hash seed randomization by default. (See command option -R.) Thus set iteration is not only arbitrary (because of hashing), but also non-deterministic (because of the random seed).

You can override the random seed with a fixed value by setting the environment variable PYTHONHASHSEED for the interpreter. Using the same seed from run to run means set iteration is still arbitrary, but now it is deterministic, which was the desired property.

Hash seed randomization is a security measure to make it difficult for an adversary to feed inputs that will cause pathological behavior (e.g., by creating numerous hash collisions). For unit testing, this is not a concern, so it's reasonable to override the hash seed while running tests.

6
  • The addition of random hashing to Python did not occur until 2012.
    – pydsigner
    Oct 7, 2015 at 19:21
  • @pydsigner: That's interesting, since this does indeed solve the problem the problem I was facing. I returned to this project last fall, and setting PYTHONHASHSEED has made the output of my tests consistent from run to run. Mar 16, 2016 at 18:13
  • Interesting indeed.... 2.6.8 and 3.2.3 were the versions where this was introduced.
    – pydsigner
    Mar 16, 2016 at 18:26
  • @pydsigner Do you also have a link for the introduction of the randomization (not the introduction of the PYTHONHASHSEED variable)? Aug 30, 2020 at 10:49
  • 1
    @superbrain based on ocert.org/advisories/ocert-2011-003.html, it sounds like the versions align with PYTHONHASHSEED being added; backported to 2.6.8 and 3.1.5 and available everywhere beyond 2.7.3 and 3.2.3.
    – pydsigner
    Sep 2, 2020 at 0:49
17

Use the symmetric_difference (^) operator on your two sets to see if there are any differences:

In [1]: s1 = set([5,7,8,2,1,9,0])
In [2]: s2 = set([9,0,5,1,8,2,7])
In [3]: s1
Out[3]: set([0, 1, 2, 5, 7, 8, 9])
In [4]: s2
Out[4]: set([0, 1, 2, 5, 7, 8, 9])
In [5]: s1 ^ s2
Out[5]: set()
1
  • That's fine for directly comparing the sets. In my tests, however, I'm looking for a simple way to just compare output from one run to another, and that output is affected by the iteration order. Sep 11, 2015 at 18:48
14

What you want isn't possible. Arbitrary means arbitrary.

My solution would be the same as yours, you have to sort the set if you want to be able to compare it to another one.

8
  • 17
    I guess I assumed arbitrary meant that it would depend on the contents, not on the phase of the moon. Oct 3, 2010 at 0:54
  • 1
    Well, there's arbitrary, then there's non-deterministic. There's probably a way you can determine what the order in the set will be, but I'd wager that's more trouble than it's worth. Check for an ordered-set, or similar in python...
    – JoshD
    Oct 3, 2010 at 0:56
  • 6
    Even if it were consistent from run to run, there would be no guarantee it would be consistent from machine to machine, python version to python version, cpython versus jython etc.
    – Mike Axiak
    Oct 3, 2010 at 0:58
  • 3
    And 'the same contents' is no guarantee either, even in the same Python build on the same machine. Items are inserted based on hash value. When multiple items have the same hash value, they get inserted in different places based on the order they are inserted in. Deletions of items can cause more different orderings. And then there's items whose hash value depends on their memory location, which makes it different between runs. There's not much you can do, other than use sorted() for a convenient way to write the 3 steps. Oct 3, 2010 at 1:19
  • 1
    Not certain, but I'd guess that at some point things are getting hashed by address (i.e. by id()), and some asynchronous thing in the system is perturbing the memory manager in different ways from run to run. I would not expect cpython to involve a PRNG in hashing at all. Oct 3, 2010 at 18:48
6

The set's iteration order depends not only its contents, but on the order in which the items were inserted into the set, and whether there were deletions along the way. So you can create two different sets, using different insertions and deletions, and end up with the same set at the end, but with different iteration orders.

As others have said: if you care about the order of the set, you have to create a sorted list from it.

2
  • 1
    Running my program twice in a row with the same input, involves the same sequence of insertions, deletions, and set operations, yet the iteration order still changes. It's as though there's something more involved, like the time of day, process ID, or something else that varies from run to run. Oct 3, 2010 at 15:42
  • 4
    Thomas Wouters points out in his comment above that some classes use id() in the hash function, meaning the object's hash depends on its memory address, and who knows what might make that differ. If you are using your own classes, you can write your own hash function to get rid of some of that indeterminancy, but you're probably better off simply sorting the results anyway. Oct 3, 2010 at 16:41
5

Your question transformed into two questions: A) how to compare "the output of two runs" in your specific case; B) what's the definition of the iteration order in a set. Maybe you should distinguish them and post B) as a new question if appropriate. I'll answer A.

IMHO, using a sorted list in your case is not a very clean solution. You should decide whether you care for iteration order once and for all and use the appropriate structure.

Either 1) you want to compare the two sets to see if they have equal content, irrespective of the order. Then the simple == operator on sets seems appropriate. See python2 sets, python3 sets.

Or 2) you want to check whether the elements were inserted in the same order. But this seems reasonable only if the order of insertion somehow matters to the users of your library, in which case using the set type was probably inappropriate to begin with. Put another way, it is unclear what you mean exactly by "comparing the output of two runs" and why you want to do that.

In all cases, I doubt a sorted list is appropriate here.

1

You can set the expected result to be also a set. And checks if those two sets are equal using ==.

0
-1

Contrary to sets, lists have always a guaranteed order, so you could toss the set and use the list.

1
  • Yup, but I'm creating the sets using several set operations, (unions, intersections, etc.). Those are less efficient as lists. Oct 3, 2010 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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