为什么一组数字看起来是有序的? [英] Why does a set of numbers appear to be sorted?

问题描述

多次运行此代码

t = {'a', 'b', 'c', 'd'}打印(吨)

可以打印如下内容:

{'c', 'b', 'a', 'd'}{'d', 'b', 'c', 'a'} # 不同{'d', 'b', 'c', 'a'} # 相同{'a', 'd', 'b', 'c'} # 不同{'a', 'b', 'c', 'd'} # 不同# 等等

(如果你是用控制台复制的，请确保每次在重新粘贴代码并执行之前都点击Rerun.如果仍然无法复制，也许你有哈希随机化不等于 random.在 Python 3.3 及更高版本上, 哈希随机化默认开启.)

<小时>

另一方面，下面的代码总是打印相同的集合，而且实际上是排序的:

s = {1, 6, 3.3, 4}印刷)# 印刷:# {1, 3.3, 4, 6}# {1, 3.3, 4, 6}# {1, 3.3, 4, 6}# {1, 3.3, 4, 6}

问题:
为什么数字集看起来总是排序的，而它们真的总是排序的?

解决方案

注意，我手边没有 python3.4，但在 python2.7 上情况并非总是如此(我希望它是python3.4也是如此).

我什至可以根据将元素放入集合的方式更改元素的顺序:

<预><代码>>>>打印({1, 9})设置([9, 1])>>>打印({9, 1})设置([1, 9])>>>设置([9, 1])设置([9, 1])>>>设置([1, 9])设置([1, 9])

顺序由元素的哈希值和插入时间决定(在哈希冲突的情况下).在 CPython 中，整数对自身进行哈希处理，并且一个 dict/set 有 8 个空闲槽可以开始.由于有 8 个可用点，我们可以散列数字 0 -> 7(含)而不会发生散列冲突.但是，如果我们尝试对同一集合中的 8 和 0(或 9 和 1)进行散列，则会发生冲突.如果 9 已经在集合中，然后我们尝试将 1 放入，python 看起来会说哦，快点，那个插槽被占用了——现在我需要把它放进去下一个最有利的位置".冲突解决的细节超出了我的研究范围，所以我无法深入了解这是什么插槽......

请注意，如果集合中有超过 5 个元素，那么它会被调整大小(IIRC，到 16，然后是 32，然后是 64，...)这会改变哪些元素会(自然地)发生碰撞.

Running this code multiple times

t = {'a', 'b', 'c', 'd'}
print(t)

could print something like:

{'c', 'b', 'a', 'd'} 
{'d', 'b', 'c', 'a'} # different
{'d', 'b', 'c', 'a'} # same
{'a', 'd', 'b', 'c'} # different
{'a', 'b', 'c', 'd'} # different
# etc

(If you are using the console to replicate it, make sure you click Rerun every time before you re-paste the code and execute it. If you still can't replicate, perhaps you have hash randomization not equal to random. On Python 3.3 and greater, hash randomization is turned on by default.)

---

On the other hand, the code below always prints the same set, and it's actually sorted:

s = {1, 6, 3.3, 4}
print(s) 

# prints: 
# {1, 3.3, 4, 6}
# {1, 3.3, 4, 6}
# {1, 3.3, 4, 6}
# {1, 3.3, 4, 6}

Question:
Why do sets of numbers appear to be always sorted and are they really always sorted?

解决方案

Note, I don't have python3.4 handy, but on python2.7 this isn't always the case (and I'd expect that to be true of python3.4 too).

I can even change the order of the elements based on how I put them into the set:

>>> print({1, 9})
set([9, 1])
>>> print({9, 1})
set([1, 9])
>>> set([9, 1])
set([9, 1])
>>> set([1, 9])
set([1, 9])

The order is determined by the hash of the element and by when it was inserted (in the case of hash collisions). In CPython, integers hash to themselves and a dict/set has 8 slots free to start with. Since there are 8 spots available, we can hash numbers 0 -> 7 (inclusive) without a hash collision. However, if we try to hash 8 and 0 (or 9 and 1) in the same set, we'll get a collision. if 9 is already in the set and then we try to put 1 in, python looks and says "Oh snap, that slot's taken -- Now I need to put it in the next most favorable slot". The details of collision resolution are beyond what I've looked into, so I can't offer insight into what slot that is ...

Note if we had more than ~5 elements in the set, then it would be resized (IIRC, to 16, then 32, then 64, ...) which changes which elements would collide (naturally).

这篇关于为什么一组数字看起来是有序的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！