Как понять хешируемый ли объект
Объект называется хешируемым, если он имеет хеш-значение (целое число), которое никогда не изменяется на протяжении его жизненного цикла и возвращается методом __hash__(), и может сравниваться с другими объектами (реализует метод __eq__()). Равные хешируемые объекты должны иметь равные хеш-значения. Все стандартные неизменяемые объекты хешируемые. Все стандартные изменяемые объекты не хешируемые.
Что такое множество
Множество – это неупорядоченная коллекция хешируемых объектов, которые не повторяются. В множествах нет понятия позиции элемента. Соответственно, они не поддерживают индексацию и срезы. Встроенные классы множеств: set (изменяемое множество), frozenset (неизменяемое множество).
Для чего применяются множества
Обычно используются для проверки элемента на вхождение в множество и удаление повторений элементов и выполнения таких операций, как объединение, пересечение, разница и симметрическая разница.
Какие операции можно производить над множествами
set([iterable]), frozenset([iterable]) – создание множества (пустого или из элементов итерабельного объекта)
len(s) – количество элементов множества
x in s, x not in s – проверка нахождения элемента в множестве
s.isdisjoint(t) – проверка того, что данное множество не имеет общих элементов с заданным
s.issubset(t), s <= t – проверка того, что все элементы множества s являются элементами множества t
s < t – проверка того, что s <= t и s != t
s.isuperset(t), s >= t – проверка того, что все элементы множества t являются элементами множества s
s > t – проверка того, что s >= t и s != t
s.union(t, …), s | t | … – создание нового множества, которое является объединением данных множеств
s.intersection(t, …), s & t & … – создание нового множества, которое является пересечением данных множеств
s.difference(t, …), s - t - … – создание нового множества, которое является разницей данных множеств
s.symmetric_difference(t), s ^ t – создание нового множества, которое является симметрической разницей данных множеств (то есть, разница объединения и пересечения множеств)
s.copy() – неполная копия множества s
Операции над множествами, которые являются методами, принимают в качестве аргументов любые итерабельные объекты. Операции над множествами, записанные в виде бинарных операций, требуют, чтобы второй операнд операции тоже был множеством, и возвращают множество того типа, которым было первое множество.
Операции над изменяемыми множествами:
s.update(t, …), s |= t | … – добавить в данное множество элементы из других множеств
s.intersection_update(t, …), s &= t & … – оставить в данном множестве только те элементы, которые есть и в других множествах
s.difference_update(t, …), s -= t | … – удалить из данного множества те элементы, которые есть в других множествах
s.symmetric_difference_update(t), s ^= t – оставить или добавить в s элементы, которые есть либо в s, либо в t, но не в обоих множествах
s.add(element) – добавить новый элемент в множество
s.remove(element) – удалить элемент из множества; если такого элемента нет, возникает исключение KeyError
s.discard(element) – удалить элемент из множества, если он в нём находится
s.pop() – удалить из множества и вернуть произвольный элемент; если множество пустое, возникает исключение KeyError
s.clear() – удалить все элементы множества.
Как происходит проверка множеств на равенство
Проверка множеств на равенство происходит поэлементно, независимо от типов множеств.
Что такое отображение
Отображение (mapping) – это объект-контейнер, который поддерживает произвольный доступ к элементам по ключам и описывает все методы, описанные в абстрактном базовом классе collections.Mapping (get(), items(), keys(), values()) или collections.MutableMapping (clear(), get(), items(), keys(), pop(), popitem(), setdefault(), update(), values()). К отображениям относятся классы dict, collections.defaultdict, collections.OrderedDict и collections.Counter.
Какие нюансы есть в использовании чисел как ключей
Числовые ключи в словарях подчиняются правилам сравнения чисел. Таким образом, int(1) и float(1.0) считаются одинаковым ключом. Однако из-за того, что значения типа float сохраняются приближенно, не рекомендуется использовать их в качестве ключей.
> > > {True: ‘yes’, 1: ‘no’, 1.0: ‘maybe’}
{True: ‘maybe’}
Какие операции можно производить над отображениями
len(d) – количество элементов.
d[key] – получение значения с ключом key. Если такой ключ не существует и отображение реализует специальный метод __missing__(self, key), то он вызывается. Если ключ не существует и метод __missing__ не определён, выбрасывается исключение KeyError.
d[key] = value – изменить значение или создать новую пару ключ-значение, если ключ не существует.
key in d, key not in d – проверка наличия ключа в отображении.
iter(d) – то же самое, что iter(d.keys()).
clear() – удалить все элементы словаря.
copy() – создать неполную копию словаря.
(метод класса) dict.fromkeys(sequence[, value]) – создаёт новый словарь с ключами из последовательности sequence и заданным значением (по умолчанию – None).
d.get(key[, default]) – безопасное получение значения по ключу (никогда не выбрасывает KeyError). Если ключ не найден, возвращается значение default (по-умолчанию – None).
d.items() – в Python 3 возвращает объект представления словаря, соответствующий парам (двухэлементным кортежам) вида (ключ, значение). В Python 2 возвращает соответствующий список, а метод iteritems() возвращает итератор. Аналогичный метод в Python 2.7 – viewitems().
d.keys() – в Python 3 возвращает объект представления словаря, соответствующий ключам словаря. В Python 2 возвращает соответствующий список, а метод iterkeys() возвращает итератор. Аналогичный метод в Python 2.7 – viewkeys().
d.pop(key[, default]) – если ключ key существует, удаляет элемент из словаря и возвращает его значение. Если ключ не существует и задано значение default, возвращается данное значение, иначе выбрасывается исключение KeyError.
d.popitem() – удаляет произвольную пару ключ-значение и возвращает её. Если словарь пустой, возникает исключение KeyError. Метод полезен для алгоритмов, которые обходят словарь, удаляя уже обработанные значения (например, определённые алгоритмы, связанные с теорией графов).
d.setdefault(key[, default]) – если ключ key существует, возвращает соответствующее значение. Иначе создаёт элемент с ключом key и значением default. default по умолчанию равен None.
d.update(mapping) – принимает либо другой словарь или отображение, либо итерабельный объект, состоящий из итерабельных объектов – пар ключ-значение, либо именованные аргументы. Добавляет соответствующие элементы в словарь, перезаписывая элементы с существующими ключами.
d.values() – в Python 3 возвращает объект представления словаря, соответствующий значениям. В Python 2 возвращает соответствующий список, а метод itervalues() возвращает итератор. Аналогичный метод в Python 2.7 – viewvalues().
Что возвращает метод items
Объекты, возвращаемые методами items(), keys() и values() (viewitems(), viewkeys(), viewvalues() в Python 2.7) – это объекты представления словаря. Они предоставляют динамическое представление элементов словаря, то есть изменения данного словаря автоматически отображаются и на этих объектах.
Операции с представлениями словарей:
iter(dictview) – получение итератора по ключам, значениям или парам ключей и значений. Все представления словарей при итерировании возвращают элементы словаря в одинаковом порядке. При попытке изменить словарь во время итерирования может возникнуть исключение RuntimeError
len(dictview) – количество элементов в словаре.
x in dictview – проверка существования ключа, значения или пары ключ-значение в словаре.
Как отсортировать список словарей по определенному полю
Метод списка .sort() и встроенная функция sorted() принимают параметр key. Им должен быть вызываемый объект, который принимает очередной элемент (в нашем случае словарь) и возвращает значение-критерий сортировки.
Код ниже показывает, как отсортировать список людей по возрасту:
users = [{‘age’: 30}, {‘age’: 20}, {‘age’: 10}]
users.sort(key=lambda user: user[‘age’])
»> [{‘age’: 10}, {‘age’: 20}, {‘age’: 30}]
Что может являться ключом словаря. Что не может. Почему
Ключом словаря может быть любой хешируемый неизменяемый объект: число, строка, datetime, функция и даже модуль. Такие объекты имеют метод __hash__(), который однозначно сопоставляет объект с некоторым числом. По этому числу словарь ищет значение для ключа.
Списки, словари и множества изменяемы и не имеют метода хеширования. При подстановке их в словарь возникнет ошибка.
Хеш кортежа вычисляется рекурсивно по всем элементам. Так, кортеж
(1, (True, (42, (‘hello’, )))) состоит только из неизменяемых элементов, поэтому может быть ключом. Однако, такой кортеж
(1, (True, (42, ({‘hello’: ‘world’}, )))) содержит глубоко внутри словарь, поэтому хеш не может быть рассчитан.
Есть два списка – ключи и значения. Как составить из них словарь
keys = [‘foo’, ‘bar’, ‘baz’]
vals = [1, 2, 3]
dict(zip(keys, vals))
»> {‘baz’: 3, ‘foo’: 1, ‘bar’: 2}
Функция zip отдает список пар N-ых элементов. Конструктор dict принимает список пар. Каждую пару он рассматривает как ключ и значение соответственно.
Как работает хэш-таблица
Хэш-таблица это разреженный массив (массив, в котором имеются незаполненные позиции). В стандартных англоязычных учебниках ячейки хэш-таблицы называются “bucket”. В хэш-таблице dict каждому элементу соотвествует ячейка, содержащая два поля: ссылку на ключ и ссылку на значение элемента. Поскольку размер всех ячеек одинаков, доступ к отдельной ячейке производится по смещению.
Python стремится оставить не менее трети ячеек пустыми; если хэш-таблица становится чрезмерно заполненной, то она копируется в новый участок памяти, где есть место для большего числа ячеек.
Для помещения элемента в хэш-таблицу нужно первым делом вычислить хэш-значение ключа элемента. Это делает встроенная функция hash().
Для выборки значения с помощью выражения my_dict[search_key] Python обращается к функции hash(search_key), чтобы получить хэш-значение search_key, и использует несколько младших битов полученного числа как смещение ячейки относительно начала хэш-таблицы (сколько именно битов зависит от текущего размера таблицы). Если найденная ячейка пуста, возбуждается исключение KeyError. В противном случае в найденной ячейке есть какой-то элемент - пара ключ:значение - и тогда Python проверяет, верно ли то, что search_key == found_key. Если да, то элемент найден и возвращается found_value. Если же search_key и found_key не совпали, то имеет место коллизия хэширования. Для разрешения коллизии алгоритм берет различные биты хэш-значения, производит над ними определенные действия и использует результат как смещение другой ячейки.
Что такое коллизия
Когда хеш-функция возвращает один и тот же ответ для разных данных.
Где будет быстрее поиск, а где перебор и почему: dict, list, set, tuple
Поиск будет быстрее в dict и set, потому что это хэш-таблицы, доступ к элементу которых выполняется за O(1). Для list и tuple поиск будет выполняться в среднем за O(n).
Исключение работает только для очень маленьких списков длиной до 5 элементов. В этом случае интерпретатору будет быстрей пробежаться по списку, чем считать хеш.
В Python 2 методы словаря keys, values, items возвращают список. Тоесть перед итерацией по словарю (или сету) интерпретатор сначала создает новый список, что занимает дополнительное время и память, но после создания это уже обыкновенный список. Тоесть в Python 2 итерация по словарям и сетам выполняется дольше, за счет создания нового списка и копирования в него элементов.
В Python 3 эти методы создают объект-представление. Это определенно происходит быстрее чем создание нового списка в Python2. Но итерирование по такому представлению должно происходить немного дольше, чем по списку из-за того что данные в словарях хранятся разреженно (редко, негусто). В подтверждение вышесказанного (Python 3):
> > > l = list(range(1000000))
d = dict.fromkeys(l)
s = set(l)
def iter_list():
… for i in l:
… pass
…
def iter_dict():
… for i in d:
… pass
…
def iter_set():
… for i in s:
… pass
…
timeit.timeit(iter_list, number=1000)
6.727667486004066
timeit.timeit(iter_dict, number=1000)
9.293120226997416
timeit.timeit(iter_set, number=1000)
8.627948219014797
