ansaurus

Question

Python set iteration order varies from run to run

Answer 1

+4 A:

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.

Turtle 2010-10-03 00:52:43

I guess I assumed arbitrary meant that it would depend on the contents, not on the phase of the moon.

Adrian McCarthy 2010-10-03 00:54:32

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 2010-10-03 00:56:34

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 2010-10-03 00:58:20

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.

Thomas Wouters 2010-10-03 01:19:30

I've marked this as the answer, but I'm still curious about what changes from run to run to cause this behavior. Does Python use a PRNG to generate the constants for a hashing function? I'm talking about the same program, with the same inputs, run twice in a row, on the same machine with the same Python interpretter.

Adrian McCarthy 2010-10-03 15:23:39

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.

Russell Borogove 2010-10-03 18:48:17

Answer 2

A:

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

knitti 2010-10-03 01:25:08

Yup, but I'm creating the sets using several set operations, (unions, intersections, etc.). Those are less efficient as lists.

Adrian McCarthy 2010-10-03 15:26:48

Answer 3

+1 A:

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.

Ned Batchelder 2010-10-03 02:36:30

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.

Adrian McCarthy 2010-10-03 15:42:54

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.

Ned Batchelder 2010-10-03 16:41:56

Answer 4

+2 A:

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()

Brian C. Lane 2010-10-03 16:30:12

ansaurus

tags:

views:

answers:

Python set iteration order varies from run to run

related questions