Ordering python sets

[Duncan Booth]

Peter Otten <__peter__ at web.de> wrote:

> I guess I have to move the goal posts to beat you:
> 
>>>> set([-1,-2]), set([-2,-1])
> (set([-2, -1]), set([-1, -2]))
> 
> For that one the number of slots doesn't matter because
> 
>>>> hash(-1), hash(-2)
> (-2, -2)
> 

Neat.

>>> last = []
>>> for i in range(0,10000,5):
	pair = list(set(range(-2,i)))[-2:]
	if pair != last:
		print "%4d(%4d): %s" % (i, i*3/2, pair)
		last = pair

		
   0(   0): [-1, -2]
   5(   7): [-2, -1]
  20(  30): [-1, -2]
  85( 127): [-2, -1]
 340( 510): [-1, -2]
1365(2047): [-2, -1]
5460(8190): [-1, -2]

The order of those two values reverses each time the hash table is 
resized, but they will always appear at the end of a set of consecutive 
integers from -2 upwards. (Highly implementation dependant of course.)

I think this demonstrates quite nicely how the hash table always 
contains  some power of 2 slots and is resized whenever it is about 
2/3rds full. Also it shows that even when you construct a set from a 
list, the set is grown one element at a time rather than pre-allocated 
(otherwise you wouldn't get the alternating order).

-- 
Duncan Booth http://kupuguy.blogspot.com