Недавно я с удивлением обнаружил, что, хотя dicts гарантированно сохраняет порядок вставки в Python 3.7+, наборы не являются:
>>> d = {'a': 1, 'b': 2, 'c': 3}
>>> d
{'a': 1, 'b': 2, 'c': 3}
>>> d['d'] = 4
>>> d
{'a': 1, 'b': 2, 'c': 3, 'd': 4}>>> s = {'a', 'b', 'c'}
>>> s
{'b', 'a', 'c'}
>>> s.add('d')
>>> s
{'d', 'b', 'a', 'c'}В чем причина такой разницы? Разве те же улучшения эффективности, которые привели команду Python к изменению реализации dict, не применимы и к наборам?
Я не ищу указателей на реализации упорядоченных наборов или способов использования dicts в качестве замены для наборов. Мне просто интересно, почему команда Python не сделала встроенные наборы сохраняющими порядок в то же время, что и для диктовок.
dictиsetначиная с 2.7.Ответы:
Наборы и дикты оптимизированы для разных вариантов использования. Основное использование набора - быстрое тестирование членства, которое не зависит от порядка. Для диктов стоимость поиска является наиболее важной операцией, и ключ, скорее всего, будет присутствовать. При использовании наборов наличие или отсутствие элемента заранее неизвестно, и поэтому реализация набора должна оптимизироваться как для найденного, так и для не найденного случая. Кроме того, некоторые оптимизации для общих операций над множествами, таких как объединение и пересечение, затрудняют сохранение порядка множеств без снижения производительности.
Хотя обе структуры данных основаны на хэше, распространенное заблуждение состоит в том, что наборы просто реализуются как диктовки с нулевыми значениями. Еще до реализации компактного dict в CPython 3.6 реализации set и dict уже значительно отличались, с небольшим повторным использованием кода. Например, в диктовках используется рандомизированное зондирование, но в наборах используется комбинация линейного зондирования и открытой адресации для улучшения локальности кэша. Первоначальный линейный зонд ( 9 шагов по умолчанию в CPython) проверит ряд смежных пар ключ / хэш, улучшая производительность за счет снижения затрат на обработку коллизий хэшей - последовательный доступ к памяти дешевле, чем разбросанных проб.
dictobject.c- мастер , версия 3.5.9setobject.c- мастер , версия 3.5.9Теоретически было бы возможно изменить реализацию набора CPython, чтобы она была похожа на компактный, но на практике есть недостатки, и известные разработчики ядра были против такого изменения.
- Гвидо ван Россум
- Раймонд Хеттингер
Подробное обсуждение вопроса о том, следует ли компактизировать наборы для 3.7, и ответы о том, почему было принято решение, можно найти в списках рассылки python-dev.
Таким образом, основные моменты заключаются в том, что шаблоны использования различны ( полезны правила размещения вставок, такие как ** kwargs , в меньшей степени - для наборов), экономия пространства для компактных наборов менее значительна (поскольку для уплотнения, в отличие от ключей, хэшей и значений), и вышеупомянутая линейная зондирование в наборах несовместима с компактной реализацией.
Я воспроизведу пост Рэймонда ниже, который охватывает наиболее важные моменты.
С [Python-Dev] Python 3.6 dict становится компактным и получает приватную версию; и ключевые слова становятся упорядоченными , сентябрь 2016.
источник
Обсуждение
Ваш вопрос уместен и уже интенсивно обсуждался на python-devs . Р. Хеттингер поделился списком обоснований в этой теме . Состояние вопроса теперь остается открытым, вскоре после подробного ответа Т. Петерса.
Короче говоря, реализация современных диктов, которая сохраняет порядок вставки, уникальна и не считается подходящей для множеств. В частности, dicts используются везде для запуска Python (например,
__dict__в пространствах имен объектов). Основным мотивом современного диктата было уменьшение размера, что делает Python более эффективным в плане памяти. Напротив, наборы менее распространены, чем диктанты в ядре Python, и, таким образом, отговаривают такой рефакторинг. См. Также доклад Р. Хеттингера о современной реализации диктов.перспективы
Неупорядоченная природа множеств в Python аналогична поведению математических множеств . Заказ не гарантируется.
Если заказ любого рода был введен для множеств в Python, то это поведение соответствовало бы совершенно отдельной математической структуре, а именно упорядоченному множеству (или Oset). Осет играет отдельную роль в математике, особенно в комбинаторике. Одно практическое применение осетов наблюдается при смене колоколов .
Наличие неупорядоченных множеств согласуется с очень общей и вездесущей структурой данных, которая раскручивает самую современную математику, т.е. теорию множеств . Я утверждаю, что неупорядоченные наборы в Python - это хорошо иметь.
Смотрите также похожие посты, которые раскрывают эту тему:
источник