Наборы сортируются от 0 до 9 каждый раз в python ?! Неупорядоченный - PullRequest
Новая
       4

Наборы сортируются от 0 до 9 каждый раз в python ?! Неупорядоченный

1 голос
/ 26 марта 2020

Сначала я подумал, что это совпадение, поэтому я написал тест, чтобы проверить его, и это правда, я запускал его 1 миллион раз, и каждый раз, когда набор возвращался, заказывал и сортировал. Это происходит только в том случае, если вы используете целые числа от 0 до 9, как только вставлено целое число> 9, тогда все целые числа, вставленные после, не будут отсортированы. Почему это? Также для поплавков это вроде как, но не все время, так странно, я думал, что они совершенно неупорядочены. Любой совет о том, почему 0-9 сортируется каждый раз, был бы очень признателен, я сначала тоже не поверил, так что вот код, который я использовал, вы можете легко запустить его самостоятельно и увидеть, что это правда. 

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

1 Ответ

3 голосов
/ 27 марта 2020

Эти целые имеют га sh сами по себе: 

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

Когда вы добавляете числа от 0 до 9 к набору, набор освобождает место как минимум для 10 чисел (я думаю, на самом деле 32). Таким образом, его внутренний массив имеет по крайней мере индексы от 0 до 9. И поскольку эти числа имеют sh для себя, они хранятся во внутреннем массиве набора по своему собственному индексу (значение i сохраняется в индексе hash(i) = i). Поэтому, когда вы выполняете итерацию, вы сортируете их.

Дальнейшая иллюстрация с небольшими примерами:

Устанавливает начало с внутреннего размера 8, а значение i хочет go для индекса hash(i) % 8. Поэтому, если вы добавите 0 и 8, оба захотят go индексировать 0. Тот, который идет первым, на самом деле попадает в индекс 0, другой должен go в какой-то другой (больший) индекс. Следовательно: 

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

Если вместо этого добавить 1 и 8, то 1 хочет go для индексации 1 и 8 хочет go для индексации 0, поэтому 8 всегда стоит первым независимо от порядка вставки: 

>>> {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}
...