какой или какие фрагменты кода создадут словари dictionary

Словари (dict, dictionary) в Python

Введение

Словарь — это пример хранилища значений ключей, также известного как Mapping в Python. Он позволяет хранить и извлекать элементы, ссылаясь на ключ. Так как словари ссылаются по ключу, в них быстро работает поиск, поскольку они в основном используются для ссылки на элементы по ключу и они не сортируются.

Доступ к значениям словаря

Строка «Hello» в этом примере называется ключом. Он используется для поиска значения в словаре, помещая ключ в квадратные скобки.

Число 1234 видно после соответствующего двоеточия в словаре. Это значение, на которое ведёт «Hello» в словаре.

x = dictionary.get(«whatever», «nuh-uh»)

Конструктор dict()

Конструктор dict() можно использовать для создания словарей из именованных аргументов или из одной итерируемой пары ключ-значение или из одного словаря и именованного аргумента.

Как избегать исключений KeyError

Распространённая ошибка при использовании словарей — доступ к несуществующему ключу. Это обычно приводит к исключению KeyError :

Другой способ избавиться от ошибки — перехватить исключение

Вы также можете проверить, есть ли ключ словаре:

Обратите внимание, что в многопоточных средах ключ может быть удален из словаря после проверки, создавая состояние, при котором всё ещё может быть выдано исключение.

Доступ к ключам и значениям

При работе со словарями часто требуется получить доступ ко всем ключам и значениям в словаре, в цикле for, в генераторе списка или просто в виде простого списка.

Словарь будет таким:

Вы можете получить список ключей, используя метод keys или функцию dict_keys :

Если вместо этого вы хотите получить список значений, используйте метод values или функцию dict_values :

Если вы хотите работать как с ключом, так и с соответствующим значением, вы можете использовать метод items или функцию dict_ items :

Введение в словарь

Создание словаря

Словари можно создавать разными способами:

С помощью литерала

С помощью генератора словаря

Через встроенный класс dict()

Модификация словаря

Чтобы добавить элементы в словарь нужно создать новый ключ со значением:

Также можно добавить список или словарь в качестве значения:

Чтобы удалить элемент, нужно удалить ключ из словаря:

Словари со значениями по умолчанию

Доступно в стандартной библиотеке как defaultdict

Если вам нужно добавить много значений, dict.setdefault() будет создавать новый экземпляр начального значения (в этом примере a[]) каждый раз, когда оно вызывается, создавая лишнюю нагрузку.

Как создать упорядоченный словарь

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

Распаковка словарей с помощью оператора **

Вы можете использовать оператор распаковки именованного аргумента слова ** для доставки пар ключ-значение в словаре в аргументы функции. Упрощенный пример из официальной документации:

Начиная с Python 3.5 вы также можете использовать этот синтаксис для объединения произвольного числа объектов [ dict ].

Этот пример показывает, что дубликаты ключей соответствуют последнему значению (например, «Клиффорд» переопределяет «Немо»).

Объединений словарей

Рассмотрим разные словари:

Python 3.5+

В этом примере, дубликаты ключей соответствуют последнему значению (например, «Клиффорд» переопределяет «Немо»).

Python 3.3+

Здесь первостепенное значение отдаётся кокретному ключу, а не последнему («Клиффорд» выбрасывается в пользу «Немо»).

Python 2.x, 3.x

Здесь используется последнее значение, как и в методе слияния [**] («Клиффорд» переопределяет «Немо»).

Замыкающая запятая

Также как в списках или кортежах, можно добавлять замыкающую запятую в своем словаре.

PEP 8 требует, чтобы вы оставляли пробел между замыкающей запятой и закрывающей скобкой.

Все комбинации значений словаря

Вы можете создать список, который возвращает все такие комбинации значений, используя следующий код.

Это дает нам следующий список, хранящийся в переменной combinations :

Перебор словаря

Если вы используете словарь в качестве итератора (например, в операторе for ), он перемещает ключи в словаре. Например:

Работает таким же образом в генераторах:

Метод items() можно использовать для одновременного зацикливания ключа и значения:

Метод values() можно использовать для перебора только значений:

Создание словаря

Правила создания словаря:

Примеры словарей

Словари сопоставляют ключи со значениями

Доступ к значениям словаря осуществляется по их ключам

Словари также могут быть созданы в стиле JSON:

Значения словаря могут быть перебраны:

Синтаксис

Примечания

Что следует помнить при использовании словаря:

– каждый ключ должен быть уникальным (иначе он будет переопределен);

– каждый ключ должен быть хэшируемым (для хеширования применяется функция hash) в противном случае возникнет исключение TypeError;

– для ключей нет определённого порядка.

Научим основам Python и Data Science на практике

Это не обычный теоритический курс, а онлайн-тренажер, с практикой на примерах рабочих задач, в котором вы можете учиться в любое удобное время 24/7. Вы получите реальный опыт, разрабатывая качественный код и анализируя реальные данные.

Источник

Генераторы словарей

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

Будет интересно в основном новичкам в Python.

Генераторы списков

Самый простой способ создать список — использовать однострочное выражение — генератор списка. Он довольно часто применяется, и я встречал его во многих примерах и в коде многих библиотек.
Предположим, что у нас есть функция возвращающая какой-то список. Хороший пример — функция range(start, end), которая возвращает числа между start и end. Начиная с версии Python 3.0 она реализована как генератор и возвращает не сразу полный список, а выдает число за числом по мере необходимости. В Python 2.* для этого использовалась функция xrange(). Получение списка чисел от 1 до 10 при помощи этой функции могло бы выглядеть так:

Если нам нужны только четные номера, мы могли бы реализовать это следующим образом:

Генераторы списков делают код намного проще. Так выглядит выражение возвращающее список в общем виде:

Используя его, первый пример можно переписать так:

Конечно такой синтаксис на первый взгляд может показаться странным, но когда к нему привыкнешь — код станет проще и понятнее.

Удаление дубликатов

Другая часто встречающаяся задача при работе с коллекциями — удаление одинаковых элементов. Ее можно решить множеством методов.
Допустим мы работаем с таким списком:

Самый сложный способ удалить дубликаты, который мне встречался, выглядит так:

Конечно и это работает, но есть решения попроще. Вы можете использовать стандартный тип множество(set). Множества не могу содержать одинаковые элементы по определению, таким образом если конвертировать список во множество — дубликаты удалятся. Но мы получим множество а не список, поэтому если мы хотим именно список уникальных значений — нужно сконвертировать еще раз:

Удаление одинаковых объектов

Совсем другая ситуация с объектами или словарями. Например у нас есть список словарей, в которых одно из значений используется в качестве идентификатора:

Удаление повторов может может быть реализовано большим или меньшим количеством кода. Конечно, чем меньше — тем лучше! Длинный вариант может выглядеть, например, так:

Можно получить то же результат, используя возможность, о которой я узнал пару дней назад: генераторы словарей. Они имеют похожий на генераторы списков синтаксис, но возвращают словарь:

Если переписать код из примера выше с использование этой фичи, останется всего одна сточка:

В этой строчке кода создается словарь, ключами которого являются поля, которые мы приняли за уникальный идентификатор, затем с помощью метода values() получаем все значения из созданного словаря. Т.к. словарь может содержать не больше одной записи для каждого ключа — полученный в итоге список не содержит дубликатов, что нам и требовалось.
Данная возможность была добавлена в Python 3.0 и бэкпортирована в Python 2.7, В более ранних версиях для решения подобной задачи можно использовать конструкцию такого вида:

Генерируется список кортежей (пар) и передается их конструктору dict(), который берет первый элемент кортежа как ключ, а второй как значение. При таком подходе решение всё той же задачи будет выглядеть так:

Источник

Реализация словаря в Python 2.7

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

На написание этой статьи меня натолкнул вопрос на Stack Overflow.
В статье рассматривается реализация CPython версии 2.7. Все примеры были подготовлены в 32-битной версии Python на 64-битной ОС, для другой версии значения будут отличаться.

Словарь в Python

Словарь в Python является ассоциативным массивом, то есть хранит данные в виде пар (ключ, значение). Словарь – измененяемый тип данных. Это значит, что в него можно добавлять элементы, изменять их и удалять из словаря. Он также предоставляет операцию поиска и возвращения элемента по ключу.

Инициализация и добавление элементов:

Ключами словаря могут быть значения только hashable типов, то есть типов, у которых может быть получен хэш (для этого у них должен быть метод __hash__()). Поэтому значения таких типов, как список (list), набор (set) и собственно сам словарь (dict), не могут быть ключами словаря:

Реализация

Словарь в Python реализован в виде хэш-таблицы. Как известно, реализация хэш-таблицы должна учитывать возможность появления коллизий – ситуаций, когда разные ключи имеют одинаковое значение хэша. Должен быть способ вставки и извлечения элементов с учётом коллизий. Существует несколько способов разрешения коллизий, например метод цепочек и метод открытой адресации. В Python используется метод открытой адресации. Разработчики предпочли метод открытой адресации методу цепочек ввиду того, что он позволяет значительно сэкономить память на хранении указателей, которые используются в хэш-таблицах с цепочками.

В рассматриваемой реализации каждая запись (PyDictEntry) в хэш-таблице словаря состоит из трёх элементов – хэш, ключ и значение.

Структура PyDictObject выглядит следующим образом:

При создании нового объекта словаря его размер равен 8. Это значение определяется константой PyDict_MINSIZE. Для хранения хэш-таблицы в PyDictObject были введены переменные ma_smalltable и ma_table. Переменная ma_smalltable с предвыделенной памятью размером PyDict_MINSIZE (то есть 8) позволяет небольшим словарям (до 8 объектов PyDictEntry) храниться без дополнительного выделения памяти. Эксперименты, проведённые разработчиками, показали, что этого размера вполне достаточно для большинства словарей: небольших словарей экземпляров и обычно небольших словарей, созданных для передачи именованных аргументов (kwargs). Переменная ma_table соответствует ma_smalltable для маленьких таблиц (то есть для таблиц из 8 ячеек). Для таблиц большего размера память ma_table выделяется отдельно. Переменная ma_table не может быть равна NULL.

Если кому-то вдруг захочется изменить значение PyDict_MINSIZE, это можно сделать в исходниках, а затем пересобрать Python. Значение рекомендуется делать равным степени двойки, но не меньше четырёх.

Ячейка в хэш-таблице может иметь три состояния

Переменные-члены структуры

Основные тонкости

Эффективность хэш-таблицы зависит от наличия «хороших» хэш-функций. «Хорошая» хэш-функция должна вычисляться быстро и с минимальным количеством коллизий. Но, к сожалению, наиболее часто используемые и важные хэш-функции (для строкового и целого типов) возвращают достаточно регулярные значения, что приводит к коллизиям. Возьмём пример:

Для целых чисел хэшами являются их значения, поэтому подряд идущие числа будут иметь подряд идущие хэши, а для строк подряд идущие строки имеют практически подряд идущие хэши. Это не обязательно плохо, напротив, в таблице размером 2**i взятие i младших бит хэша как начального индекса таблицы выполняется очень быстро, и для словарей, проиндексированных последовательностью целых чисел, коллизий не будет вообще:

То же самое будет почти полностью соблюдаться, если ключи словаря – это «подряд идущие» строки (как в примере выше). В общих случаях это дает более чем случайное поведение, что и требуется.

Взятие только i младших бит хэша в качестве индекса также уязвимо к коллизиям: например, возьмём список [i 011 ₂ & 111 ₂ = 011 ₂ = 3

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

Это объясняет хитрый момент, связанный с добавлением равных по значению, но разных по типу ключей (к примеру, float, int и complex):

То есть тот тип, который был добавлен в словарь первым, и будет типом ключа, несмотря на обновление. Это объясняется тем, что реализация хэша для float значений возвращает хэш от int, если дробная часть равна 0.0. Пример расчёта хэша для float, переписанный на Python:

А хэш от complex возвращает хэш от float. В данном случае возвращается хэш только действительной части, так как мнимая часть равна нулю:

Ввиду того, что и хэши, и значения для всех трёх типов равны, выполняется простое обновление значения найденной записи.

Замечание по поводу добавления элементов: Python запрещает добавление элементов в словарь во время итерации, поэтому при попытке добавить новый элемент произойдёт ошибка:

Получается, что индексы добавляемых в словарь элементов зависят от уже находящихся в нём элементов, и порядок ключей для двух словарей, состоящих из одного и того же набора пар (ключ, значение), может быть разным и определяется очерёдностью добавления элементов:

Это объясняет, почему словари в Python при выводе содержимого отображают хранимые пары (ключ, значение) не в порядке их добавления в словарь. Словари выводят их в порядке расположения в хэш-таблице (то есть в порядке индексов).

Произошла вставка по индексу 5. Переменные ma_fill и ma_used стали равны 1.

Произошла вставка по индексу 0. Переменные ma_fill и ma_used стали равны 2.

Произошла вставка по индексу 4. Переменные ma_fill и ma_used стали равны 3.

Произошла вставка по индексу 1. Переменные ma_fill и ma_used стали равны 4.

Пробуем добавить шестой элемент в словарь.

После добавления шестого элемента таблица будет заполнена на 2/3, а соответственно, произойдёт изменение её размера. После того как размер изменится (в данном случае увеличится в 4 раза), произойдёт полная перестройка хэш-таблицы с учётом нового размера – все «активные» ячейки будут перераспределены, а «пустые» и «неиспользованные» ячейки будут проигнорированы.

Размер хэш-таблицы теперь равен 32, а переменные ma_fill и ma_used стали равны 6. Как видно, порядок элементов полностью поменялся:

Поиск элемента

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

Коэффициент заполнения хэш-таблицы

Размер таблицы изменяется, когда она заполняется на 2/3. То есть для начального размера хэш-таблицы словаря, равного 8, изменение произойдёт после того, как будет добавлен 6 элемент.

При этом происходит перестройка хэш-таблицы с учётом её нового размера, а соответственно, меняются и индексы всех записей.

Значение 2/3 от размера было выбрано как оптимальное, для того чтобы пробирование не занимало слишком много времени, то есть вставка новой записи происходила быстро. Увеличение этого значения приводит к тому, что словарь плотнее заполняется записями, что в свою очередь увеличивает количество коллизий. Уменьшение же увеличивает разреженность записей в ущерб увеличения занимаемых ими кэш-линий процессора и в ущерб увеличения общего объема памяти. Проверка заполнения таблицы происходит в весьма чувствительном ко времени участке кода. Попытки сделать проверку более сложной (например, изменяя коэффициент заполнения для разных размеров хэш-таблицы) уменьшали производительность.

Проверить, что размер словаря действительно изменяется, можно так:

В примере возвращается размер всего объекта PyDictObject для 64-битной версии ОС.
Начальный размер таблицы равен 8. Таким образом, когда число заполненных ячеек будет равно 6 (то есть больше 2/3 от размера), размер таблицы увеличится до 32. Затем, когда число будет равно 22, увеличится до 128. При 86 увеличится до 512, при 342 – до 2048 и так далее.

Коэффициент увеличения размера таблицы

Коэффициент увеличения размера таблицы при достижении максимального уровня заполнения равен 4, если размер таблицы меньше 50000 элементов, и 2 – для таблиц большего размера. Такой подход может быть полезен приложениям с ограничениями по памяти.

Увеличение размера таблицы улучшает среднюю разреженность, то есть разбросанность записей по таблице словаря (уменьшая коллизии), за счёт увеличения объема потребляемой памяти и скорости итераций, а также уменьшает количество дорогостоящих операций выделения памяти при изменении размера для растущего словаря.

Обычно добавление элемента в словарь может увеличить его размер в 4 или 2 раза в зависимости от текущего размера словаря, но также возможно, что размер словаря уменьшится. Такая ситуация может произойти, если ma_fill (количество ненулевых ключей, сумма «активных» и «пустых» ячеек) намного больше ma_used (количество «активных» ячеек), то есть много ключей было удалено.

Удаление элемента

При удалении элемента из словаря вызывается функция PyDict_DelItem.
Удаление из словаря происходит по ключу, хотя в действительности освобождения памяти не происходит. В этой функции вычисляется хэш значение ключа, а затем происходит поиск записи в хэш-таблице с использованием всё той же функции lookdict_string или lookdict. В случае если запись с таким ключом и хэшем найдена, ключ этой записи выставляется в состояние «пустой» (то есть me_key = dummy), а значение записи – в NULL (me_value = NULL). После этого переменная ma_used уменьшится на единицу, а ma_fill останется без изменения. Если же запись не найдена, возвращается ошибка.

После удаления переменная ma_used стала равна 4, а ma_fill осталась равной 5, так как ячейка не была удалена, а всего лишь была помечена как «пустая» и продолжает занимать ячейку в хэш-таблице.

Рандомизация хэшей

Источник

Под капотом у Dictionary и ConcurrentDictionary

Итак, поехали.

Если вы уже знакомы с самим Dictionary, то можете пропустить следующий раздел.

Dictionary представляет собой реализацию стандартной Hashtable.
Здесь интересны следующие функции:

Инициализация

Инициализация происходит либо при создании (если передана начальный размер коллекции), либо при добавлении первого элемента, причем в качестве размера будет выбрано ближайшее простое число (3). При этом создаются 2 внутренние коллекции — int[] buckets и Entry[] entries. Первая будет содержать индексы элементов во второй коллекции, а она, в свою очередь, — сами элементы в таком виде:

Добавление элементов

При добавлении элемента вычисляется хэшкод его ключа и затем — индекс корзины в которую он будет добавлен по модулю от величины коллекции:

Выглядеть это будет примерно так:

Затем проверяется нет ли уже такого ключа в коллекции, если есть — то операция Add выбросит исключение, а присваивание по индексу просто заменит элемент на новый. Если достигнут максимальный размер словаря, то происходит расширение (выбирается новый размер ближайшим простым числом).
Сложность оперции соответственно — O(n).

Если происходит коллизия (то есть в корзине с индексов bucketNum уже есть элемент), то новый элемент добавляется в коллекцию, его индекс сохраняется в корзине, а индекс старого элемента — в его поле next.

Таким образом получаем однонаправленный связный список. Данный механизм разрешения коллизий называется chaining. Если при добавлении элемента число коллизий велико (больше 100 в текущей версии), то при расширении коллекции происходит операция перехэширования, перед выполнением которой случайным образом выбирается новый генератор хэшкодов.
Сложность добавления O(1) или O(n) в случае коллизии.

Удаление элементов

При удалении элементов мы затираем его содержимое значениями по умолчанию, меняем указатели next других элементов при неоходимости и сохраняем индекс этого элемента во внутреннее поле freeList, а старое значение — в поле next. Таким образом, при добавлении нового элемента мы можем повторно использовать такие свободные ячейки:

Сложность снова O(1) или O(n) в случае коллизии.

Другое

Так же стоит отметить 2 момента:
1) При очистке словаря, его внутренний размер не изменяется. То есть, потенциально, вы просто тратите место.
2) GetEnumerator просто возвращает итератор по коллекции entires (сложность O(1)). Если вы только добавляли элементы — они вернутся в том же порядке. Однако если вы удаляли элементы и добавляли новые — порядок соответственно изменится, поэтому на него полагаться не стоит (тем более, что в будущих версиях фреймворка это может измениться).

Так и что же с ConcurrentDictionary?

Казалось бы, есть 2 решения в лоб для обеспечения потокобезопасности — обернуть все обращения к словарю в блокировки или обернуть все его методы в них же. Однако, по понятным причинам, такое решение будет медленным — задержки, добавляемые lock, да и ограничение на 1 поток, который мог бы работать с коллекцией не добавляют быстродействия.

В Microsoft пошли более оптимальным путем и Dictionary притерпел некоторые изменения. Так, благодаря внутренней структуре словаря и его корзин, блокировка осуществляется по ним, с помощью метода

В то же время обычный словарь не смог бы работать с этой схемой, потому что все корзины используют один и тот же массив entries, поэтому корзины стали представлять собой обычный single linked list: volatile Entry[] m_buckets (поле объявлено как volitale, чтобы обеспечить неблокирующую синхронизацию в ситуации когда один поток пытается выполнить какую-то операцию, а другой в этот момент изменяет размер коллекции).

В итоге корзины стали выглядеть вот так:

lockNo — это индекс в новом массиве, который содержит объекты синхронизации — object[] m_locks. Его использование позволяет разным потокам изменять разные корзины в одно и то же время. Размер этой коллекции зависит от параметра ConcurrencyLevel который можно задать через конструктор. Он определяет примерное число потоков которые будут одновременное работать с коллекцией (по умолчанию это число_процессоров * 4). Чем выше это значение, тем проще будут происходить операции записи, но так же станут гораздо дороже операции, которые требуют полной блокировки всей коллекции (Resize, ToArray, Count, IsEmpty, Keys, Values, CopyTo, Clear). Также этот параметр определяет сколько элементов коллекции приходится на один lock (как отношение числа корзин к размеру этой коллекции) и когда элементов становится больше, чем надо — коллекция расширяется, потому что в противном случае поиск элемента требует не O(1), а уже O(n) за счет обхода связных списков. Чтобы немного снизить число первоначальных расширений коллекции, начальный размер словаря уже не 3, а 31.

Все операции приобрели вид:

При добавлении нового элемента приходится обойти весь связанный список просто чтобы определить есть ли уже такой ключ и если нет — добавить. Аналогично при удалении — сперва надо найти узел который удалить.

Впрочем, для некоторых операций блокировка не нужна в принципе — это TryGetValue, GetEnumerator, ContainsKey и индексация. Почему? Потому что все изменения размера корзин видны за счет того что поле volatile, любые добавления или изменения элементов происходят путем создания нового элемента и замены им старого, а удаления происходят просто заменой указателя на следующий узел.

Другое

лучше использовать dictionary.Select(x => x.Value).ToArray(), чем dictionary.Values.ToArray()

И это не совсем верно — вместо «лучше» тут должно быть «быстрее» — за счет отсутствия блокировок, но надо принять во внимание, что данные подходы могут вернуть разные данные.

Источник