在python中，集合每次从0-9排序?不是无序的 [英] Sets are sorted from 0-9 every single time in python?! Not unordered

问题描述

我认为起初这是一个巧合，所以我写了一个测试来进行测试，这是真的，我运行了100万次，每次返回套件时都进行排序和排序.仅当您插入0到9的整数时使用0到9的整数，然后插入的所有整数将不被排序时，才会发生这种情况.为什么是这样?对于浮子，它也有点排序，但并非总是如此，所以奇怪的是，我认为它们是完全无序的.任何关于为什么每次都对0-9进行排序的建议都将不胜感激，我也不是一开始就相信它，因此这是我使用的代码，您可以轻松地自己运行它并查看它的真实性.

I thought it was a coincidence at first so I wrote up a test to try it out and it's true, I ran it 1 million times and every single time the set came back ordered and sorted. This only occurs when you use integers from 0-9 as soon as an integer > 9 is inserted then any integers inserted after will not be sorted. Why is this? Also for floats it kind of sorts it but isn't right all the time, so weird I thought they were completely unordered. Any advice on why 0-9 is sorted every time would be greatly appreciated, I didn't believe it at first either so here's the code I used you can easily run it yourself and see it's true.

import random

def check_set():
    constructing = True
    s = set()
    while constructing:
        x = random.randint(0, 9)
        if x not in s: s.add(x)
        if len(s) == 10: constructing = False
    return s
def main():
    for x in range(10000):
        l = list(check_set())
        if l != [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
            print('wow')
if __name__ == '__main__':
    main()

推荐答案

这些int会自己散列:

Those ints hash to themselves:

>>> [*map(hash, range(10))]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

在将数字0到9添加到集合中时，集合为至少10个数字(实际上是32个)腾出了空间.因此，它的内部数组至少具有索引0到9.由于这些数字本身是散列的，因此它们以它们自己的索引存储在集合的内部数组中(值 i 被存储在索引 hash(i) = i ).因此，当您进行迭代时，便可以对它们进行排序.

When you add the numbers 0 to 9 to a set, the set makes room for at least 10 numbers (actually 32, I think). So its internal array has at least the indexes 0 to 9. And because those numbers hash to themselves, they're stored in the set's internal array at their own index (value i gets stored at index hash(i)=i). So when you iterate it, you get them sorted.

带有较小示例的进一步说明:

Further illustration with smaller examples:

集合以内部大小8开头，值 i 希望索引为 hash(i)％8 .因此，如果您添加 0 和 8 ，则两者都希望转到索引 0 .首先出现的一个实际上到达索引 0 ，另一个必须到达其他(更大)索引.因此:

Sets start with internal size 8, and value i wants to go to index hash(i) % 8. So if you add 0 and 8, both want to go to index 0. The one that comes first actually gets to index 0, the other has to go to some other (larger) index. Hence:

>>> {0, 8}, {8, 0}
({0, 8}, {8, 0})

如果您改为添加 1 和 8 ，则 1 想要转到索引 1 和 8 想要转到索引 0 ，因此无论插入顺序如何， 8 始终排在第一位:

If you instead add 1 and 8, then 1 wants to go to index 1 and 8 wants to go to index 0, so 8 always comes first regardless of insertion order:

>>> {1, 8}, {8, 1}
({8, 1}, {8, 1})

0到9的示例:

>>> s = set()
>>> for i in 8, 9, 0, 1, 2, 3, 4, 5, 6, 7:
        s.add(i)
        print(s)

{8}    # the only element (stored at index 0)
{8, 9}    # 9 gets stored at index 1, so after 8
{8, 9, 0}    # indices 0 and 1 are already taken, so 0 goes to some higher index
{8, 9, 0, 1}    # similar
{0, 1, 2, 8, 9}    # the set internally resized and re-added all values, each
                   # value ends up at its own index (e.g., 8 goes to index 8)
{0, 1, 2, 3, 8, 9}    # 3 goes to index 3
{0, 1, 2, 3, 4, 8, 9}    # same for the rest, all go to their own index...
{0, 1, 2, 3, 4, 5, 8, 9}
{0, 1, 2, 3, 4, 5, 6, 8, 9}
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

这篇关于在python中，集合每次从0-9排序?不是无序的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！