Гарантирует ли набор пересечений набор целых чисел для сортировки?

Я пытаюсь сделать огромное количество простых операций "пересечения" с целыми числами. К сожалению, в настройках нет numpy/scipy, и я не могу это изменить.

Я заметил в stackru, что операция множеств Python хорошо сортирует данные, что не только ускоряет загрузку дел, но и в моем случае, я на самом деле хотел бы также сортировать данные, таким образом, это был бы потрясающий бонус.

Я сейчас просто боюсь, что это не всегда работает, поэтому я пошел тестировать:

import random 

one = range(100)
two = range(50)
three = range(50)

for i in xrange(1000000):
    # shuffle the lists
    random.shuffle(one)
    random.shuffle(two)    

    # do set operation  
    res = [v for v in set(one) & set(two)]
    if res != three:
        print res

В результате все образцы сортируются (неправильные случаи не печатаются).

Хотя это довольно убедительно, я хотел бы знать, будет ли случай, когда целые числа не сортируются полностью при использовании пересечения множеств?

Источник

3 ответа

Решение

Нет, это не так.

Реализация пересечения множеств в CPython работает путем параллельной итерации по двум наборам в порядке хеширования. Соответствующие хэши дополнительно проверяются на равенство.

Если у вас есть набор небольших смежных ints, они все будут хэшировать себе, так что все будет хорошо. Но если наборы - это что-то еще (широко расставленные целые, строки, что угодно), этот же эффект не появится.

Источник

Набор не имеет порядка, поэтому любой порядок является случайным. Или, если быть точным, у него есть некоторый порядок, но вы не можете делать никаких предположений относительно этого. Если вы хотите, чтобы результат был отсортирован, вам нужно отсортировать его самостоятельно, используя sorted(),

Источник

Контрпримеры очень легко найти, если вы знаете, где искать

>>> [v for v in set(range(-10,0)) & set(range(-5,10))]
[-2, -5, -4, -3, -1]
Источник
Другие вопросы по тегам