4
h = [9, 8, 7, 4, 5, 6, 3, 2, 1, 5, 5]
new_h = {x*2 for x in h}

Почему при генерации множество получается упорядоченное по возрастанию? Оно же вроде рандомное и без индексации

3
  • 1
    Похоже для ваших данных случайно так получается. Возможно причина в какой-то оптимизации для маленьких чисел. Добавьте в свой массив 20, например, и множество будет уже неупорядоченным.
    – dzhioev
    22 авг 2022 в 20:26
  • У этой случайности есть объяснение. 22 авг 2022 в 21:25
  • Я удивляюсь вашей наблюдательности. Браво! 22 авг 2022 в 21:33

2 ответа 2

4

Нет, оно не получается упорядоченным. Мало того, видимый порядок элемента множества может зависеть от способа взгляда на него.

$ python
Python 3.10.6 (main, Aug  3 2022, 03:52:09) [Clang 11.0.3 (clang-1103.0.32.62)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> h = [9, 8, 7, 4, 5, 6, 3, 2, 1, 5, 5, 10, 20]
>>> new_h = {x*2 for x in h}
>>> print(new_h, [i for i in new_h])
{2, 4, 6, 8, 40, 10, 12, 14, 16, 18, 20} [2, 4, 6, 8, 40, 10, 12, 14, 16, 18, 20]
>>> new_h, [i for i in new_h]
({2, 4, 6, 8, 40, 10, 12, 14, 16, 18, 20}, [2, 4, 6, 8, 40, 10, 12, 14, 16, 18, 20])

и

$ ipython
Python 3.10.6 (main, Aug  3 2022, 03:52:09) [Clang 11.0.3 (clang-1103.0.32.62)]
Type 'copyright', 'credits' or 'license' for more information
IPython 8.2.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: h = [9, 8, 7, 4, 5, 6, 3, 2, 1, 5, 5, 10, 20]
   ...: new_h = {x*2 for x in h}
   ...: print(new_h, [i for i in new_h])
   ...: new_h, [i for i in new_h]
{2, 4, 6, 8, 40, 10, 12, 14, 16, 18, 20} [2, 4, 6, 8, 40, 10, 12, 14, 16, 18, 20]
Out[1]: 
({2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 40},
 [2, 4, 6, 8, 40, 10, 12, 14, 16, 18, 20])

P.S.

По результату дискуссии со @StanislavVolodarskiy следует отметить настройку "Pretty printing" в IPython (Jupyter Notebook и прочая, прочая), которая упорядочивает элементы множества при печати результата:

$ ipython 
Python 3.10.6 (main, Aug  3 2022, 03:52:09) [Clang 11.0.3 (clang-1103.0.32.62)]
Type 'copyright', 'credits' or 'license' for more information
IPython 8.2.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: from random import *

In [2]: {randrange(300) for i in range(10)}
Out[2]: {4, 6, 25, 30, 68, 90, 106, 136, 146, 262}

In [3]: %pprint
Pretty printing has been turned OFF

In [4]: Out[2]
Out[4]: {4, 68, 262, 6, 136, 106, 146, 25, 90, 30}

In [5]: %pprint
Pretty printing has been turned ON

In [6]: Out[2]
Out[6]: {4, 6, 25, 30, 68, 90, 106, 136, 146, 262}
2
  • Кажется, вы правы про ipython. Он что-то делает с печатью переменных типа set. Возможно сортировка значений при выполнении new_h ? 23 авг 2022 в 11:14
  • @StanislavVolodarskiy , да это "Pretty print" так работает.
    – Serge3leo
    23 авг 2022 в 12:23
3

Это особенность реализации set. Хеш коды неотрицательных целых чисел до 261 - 2 равны самим этим числам.

Если заполнять хешсет последовательно с меньших чисел до больших, они станут занимать последовательные корзины. Номер корзины вычисляется как хеш код по модулю текущей вместимости хешсет. А вместимость в этой ситуации больше любого хешкода. Итерация ведётся по корзинам, получаем упорядоченное множество. Если порядок заполнения другой, в процессе заполнения порядок хешсета может быть произвольным, но после последнего rehashing (как это будет по-русски?) элементы в хешсет снова займут последовательные корзины. Потому что все их хешкоды меньше вместимости и совпадают с самими числами.

P.S. Никогда не используйте в программировании это случайное свойство хешсетов последовательных целых чисел. Реализация и хешсета и хешкодов целых чисел может быть изменена и упорядоченность исчезнет. Никаких гарантий тут быть не может.

P.P.S. Ответ предполагает что вы знаете как устроен хешсет. Если нет, пишите комментарии. Тема занятная.

P.P.P.S. Зная как распределяются числа по корзинам легко придумать множества чисел на которых производительность set будет деградировать. :(

5
  • Вы пишите, "А вместимость в этой ситуации больше любого хешкода.", но h = [20, 10, 9, 8, 7, 4, 5, 6, 3, 2, 1]; new_h = {x*2 for x in h}; print(new_h); new_h выдаёт упорядоченный результат только в ipython и только оператором new_h. Есть тому объяснение?
    – Serge3leo
    23 авг 2022 в 7:05
  • @Serge3leo . Почитал реализацию set в CPython. Да, есть. Окончательное множество - 11 элементов. Размер выделенного массива будет - 32. Если вы возьмёте любые 11 чисел в диапазоне [0, 31] они окажутся упорядочены. В вашем примере есть элемент - 40. Здесь как повезёт. 23 авг 2022 в 10:51
  • @Serge3leo, зато можно предсказать что 8 и 40 в итерации множества из 11 элементов всегда будут рядом (если между ними не встрянут другие числа вида 8 + 32k). 23 авг 2022 в 10:54
  • На мой взгляд, более примечательно, что, как минимум, в ipython 8.2.0 на основе python 3.6.10, операторы print(new_h); new_h выдают разный результат.
    – Serge3leo
    23 авг 2022 в 11:07
  • @Serge3leo, это для меня полная загадка. Я могу догадаться что ipython меняет процедуры вывода. Это может коснуться как print так и просто печати переменной. В такой ситуации будет правильно печатать tuple(new_h) (если мы интересуемся именно устройством set а не вводом/выводом ipython). 23 авг 2022 в 11:10

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.