Ordering python sets
Duncan Booth
duncan.booth at invalid.invalid
Wed Oct 22 20:29:45 CEST 2008
Peter Otten <__peter__ at web.de> wrote:
> Here's another one:
>
>>>> set([1,9])
> set([1, 9])
>>>> set([9,1])
> set([9, 1])
>
> This time I did indeed search systematically...
>
You missed one with smaller values:
>>> set([8,0])
set([8, 0])
>>> set([0,8])
set([0, 8])
You can work some of it out quite easily instead of searching. The hash
value for an integer is itself, the initial space allocated for the set is
8 slots so each value is reduced modulo 8. If the values you insert don't
clash then the order of insertion doesn't matter. If there are values which
coincide on the same slot then the second one inserted will go into a
different slot so the order may vary.
What Tim Chase has missed in his tests:
> s = set(r.randint(1,1000) for _ in range(1000))
is that to get the elements out of order at least one element must be
larger than the number of allocated slots. Since there are always a lot of
unused slots that means the range for the integers needs to be
significantly greater than the number of integers.
e.g.
>>> set([128]+range(84))
set([128, 0, 2, 3, 4, 5, 6, 1, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37,
38, 39, 40, 41, 42, 7, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56,
57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75,
76, 77, 78, 79, 80, 81, 82, 83, 43])
>>> set([128]+range(85))
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38,
39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57,
58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76,
77, 78, 79, 80, 81, 82, 83, 84, 128])
the 86th element added to the set makes to total size allocated large
enough that the 128 no longer conflicts with the 0.
More information about the Python-list
mailing list