Set and Dict

Множини та словники⚑

Як визначити, чи є об'єкт хешованим⚑

Об'єкт називається хешованим, якщо він має хеш-значення (ціле число), яке ніколи не змінюється протягом його життєвого циклу і повертається методом __hash__(), і може порівнюватися з іншими об'єктами (реалізує метод __eq__()).

Рівні хешовані об'єкти повинні мати однакові хеш-значення. Усі стандартні незмінні об'єкти є хешованими. Усі стандартні змінні об'єкти не є хешованими.

Для колекцій, для того щоб об'єкт був хешованим, усі внутрішні об'єкти повинні бути хешованими.

Множина (`set`)⚑

Summary

Множина (set) - це неупорядкована колекція хешованих об'єктів, які не повторюються. У множинах немає поняття позиції елемента. Відповідно, вони не підтримують індексацію і зрізи. Вбудовані класи множин: set (змінна множина), frozenset (незмінна множина).

Зазвичай множини використовуються для перевірки наявності елемента в множині, видалення повторюваних елементів і виконання операцій, таких як об'єднання, перетин, різниця та симетрична різниця.

thisset = {"apple", "banana", "cherry", "apple"}  
print(thisset)  # {'banana', 'cherry', 'apple'} - duplicate removed

Операції, які можна виконувати зі множинами⚑

set([ітерабельний_об'єкт]), frozenset([ітерабельний_об'єкт]) - створення множини (порожньої або з елементів ітерабельного об'єкта).
len(s) - кількість елементів у множині.
x in s, x not in s - перевірка наявності елемента у множині.
s.isdisjoint(t) - перевірка, чи має дана множина спільні елементи з заданою множиною t.
s.issubset(t), s <= 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 != 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(елемент) - додавання нового елемента до множини.
s.remove(елемент) - видалення елемента з множини; якщо елементу немає, виникає виключення KeyError.
s.discard(елемент) - видалення елемента з множини, якщо він там присутній.
s.pop() - видалення та повернення довільного елемента з множини; якщо множина порожня, виникає виключення KeyError.
s.clear() - видалення всіх елементів множини.

Словник (dict)⚑

Summary

Словник (dict) - це контейнерний об'єкт (хеш-таблиця), який використовується для зберігання пар ключ-значення. У словнику кожен ключ є унікальним ідентифікатором, який використовується для доступу до відповідного значення.

Ініціалізація - a = {}, a = dict()

Ключі можуть бути майже будь-якого типу даних (цілі числа, рядки, кортежі тощо), але вони повинні бути незмінними (immutable). А якщо точніше - то hashable. Наприклад, рядок або ціле число може бути ключем, але список не може. Обʼєкт може бути ключем, оскільки він hashable.

Після версії 3.7 усі словники впорядковані (OrderedDict) - ключі будуть прочитані в тому порядку, в якому вони були записані.

В Python практично всі обєкти - dict.

Доступ до ключа - O(1)

this_dict = {  
    "brand":"Ford",  
    "model":"Mustang",  
    "year": 1964  
}  
print(this_dict["brand"])  # Ford

Які нюанси існують у використанні чисел як ключів⚑

Числові ключі в словниках підпорядковуються правилам порівняння чисел. Таким чином, 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 - змінити значення або створити нову пару ключ-значення, якщо ключ не існує.
d.get(key[, default]) - безпечне отримання значення за ключем (ніколи не викидає виняток KeyError). Якщо ключ не знайдений, повертається значення default (за замовчуванням - None).
key in d, key not in d - перевірка наявності ключа в словнику.
iter(d) - те саме, що і iter(d.keys()).
clear() - видалити всі елементи словника.
copy() - створити поверхневу копію словника.
(класовий метод) dict.fromkeys(sequence[, value]) - створює новий словник з ключами з послідовності sequence і заданим значенням (за замовчуванням - None).
d.items() - в Python 3 повертає представлення словника, що відповідає парам (двоелементним кортежам) виду (ключ, значення). У Python 2 повертає відповідний список, а метод iteritems() повертає ітератор.
d.keys() - в Python 3 повертає представлення словника, що відповідає ключам словника. У Python 2 повертає відповідний список, а метод iterkeys() повертає ітератор.
d.values() - в Python 3 повертає представлення словника, що відповідає значенням. У Python 2 повертає відповідний список, а метод itervalues() повертає ітератор.
d.pop(key[, default]) - якщо ключ key існує, видаляє елемент зі словника і повертає його значення. Якщо ключ не існує і задане значення default, повертається дане значення, інакше викидається виняток KeyError.
d.popitem() - видаляє довільну пару ключ-значення і повертає її. Якщо словник порожній, виникає виняток KeyError. Метод корисний для алгоритмів, які обходять словник, видаляючи вже оброблені значення (наприклад, певні алгоритми, пов'язані з теорією графів).
d.setdefault(key[, default]) - якщо ключ key існує, повертає відповідне значення. В іншому випадку створює елемент з ключем key і значенням default. default за замовчуванням дорівнює None.
d.update(mapping) - приймає або інший словник або відображення, або ітерабельний об'єкт, що складається з ітерабельних об'єктів - пар ключ-значення, або іменовані аргументи. Додає відповідні елементи до словника, перезаписуючи елементи з існуючими ключами.

Що повертають методи `items()`, `keys()`, `values()`⚑

Об'єкти, що повертаються методами items(), keys() і values(), є об'єктами представлення словника. Вони забезпечують динамічне представлення елементів словника, тобто зміни цього словника автоматично відображаються на цих об'єктах.

Операції з представленнями словників - iter(dictview) - отримання ітератора по ключах, значенням або парам ключів і значень. Усі представлення словників при ітерації повертають елементи словника в однаковому порядку. При спробі змінити словник під час ітерації може виникнути виняток RuntimeError. - len(dictview) - кількість елементів у словнику. - x in dictview - перевірка наявності ключа, значення або пари ключ-значення в словнику.

Що повертає ітерація по словнику?⚑

Ітерація по словнику повертає ключі.

До Python 3.7 порядок слідування ключів не гарантується. Для невеликих словників порядок буде таким самим, як і при оголошенні. Для великих порядок залежить від розташування елементів в пам'яті.

Після 3.7+ включно особливий клас OrderedDict, який враховує порядок додавання ключів, використовується як словник за замовчуванням.

for key in {'foo': 1, 'bar': 2}:
    process_key(key)

Для чого може служити `missing`⚑

Метод __missing__ дозволяє уникнути винятку KeyError.

class CustomDict(dict):
    def __missing__(self, key):
        return f"The key '{key}' is missing"

custom_dict = CustomDict()
custom_dict['name'] = 'Alice'

print(custom_dict['name'])    # Outputs: Alice
print(custom_dict['age'])     # Outputs: The key 'age' is missing

Як відсортувати список словників за певним полем⚑

Метод списку .sort() і вбудована функція sorted() приймають параметр key. Ним повинен бути callable об'єкт, який приймає поточний елемент (у нашому випадку словник) і повертає значення-критерій сортування.

Наведений нижче код показує, як відсортувати список людей за віком:

users = [{'age': 30}, {'age': 20}, {'age': 10}]
users.sort(key=lambda user: user['age'])
>>> [{'age': 10}, {'age': 20}, {'age': 30}]

Що може бути ключем словника? Що не може?⚑

Ключем словника може бути будь-який хешований незмінний об'єкт: число, рядок, datetime, функція або навіть модуль. Такі об'єкти мають метод __hash__(), який однозначно відповідає об'єкту деяким числом. За цим числом словник шукає значення для ключа. А також метод __eq__() - для порівняння ключів на рівність, а не за адресами пам'яті. Це означає, що, навіть якщо два об'єкти мають різні адреси пам'яті, вони вважатимуться рівними, якщо __eq__() повертає True.

Списки, словники, множини є змінними і не мають методу хешування. При спробі вставити їх у словник виникне помилка.

Об'єкти, які є екземплярами класів, визначених користувачем, є хешованими за замовчуванням і їхнє хеш-значення базується на їхньому id(). Тобто усі будуть не рівними. Навіть якщо перевизначити метод __hash__, наступний словник поверне 2 ключі (потрібно перевизначити метод __eq__, щоб він повертав True)

class C:  
    def __hash__(self):  
        return 42 

c, d = C(), C()  
x= {c: 'c', d: 'd'}  
print(list(x.keys()))  # [<__main__.C object at 0x101656300>, <__main__.C object at 0x101655d30>]

Хеш кортежу обчислюється рекурсивно по всім його елементам. Таким чином, кортеж (1, (True, (42, ('hello', )))) складається лише з незмінних елементів, тому може бути ключем. Однак кортеж (1, (True, (42, ({'hello': 'world'},)))) не може бути ключем, оскільки в ньому є змінний словник.

Є два списки - ключі та значення. Як скласти з них словник⚑

Функція zip повертає список пар N-тих елементів. Конструктор dict приймає список пар. Кожну пару він розглядає як ключ і відповідне йому значення.

keys = ['foo', 'bar', 'baz']
vals = [1, 2, 3]
dict(zip(keys, vals))
>>> {'baz': 3, 'foo': 1, 'bar': 2}

Як працює хеш-таблиця⚑

Хеш-таблиця - це розріджений масив (масив, в якому є незаповнені позиції). У стандартних англомовних підручниках комірки хеш-таблиці називаються "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 не збігаються, відбувається колізія хешування. Для вирішення колізії алгоритм бере різні біти хеш-значення, виконує над ними певні дії і використовує результат як зміщення іншої комірки.

Links

https://web.archive.org/web/20240712214159/https://gorinenko.ru/blog/cpython-types/#a13

Що таке колізія⚑

Колізія - коли хеш-функція повертає однакове значення для різних даних. Колізії вирішуються у словнику Python за допомогою методу "open addressing" (відкрите адресування) та хеш-таблиці з ланцюжками (chaining).

При виникненні колізії, Python перевіряє інші доступні комірки (адреси у хеш-таблиці), доки не знайде вільне місце для збереження ключа та відповідного значення. Цей процес називається відкритим зондуванням. Python використовує Квадратичне зондування (Quadratic Probing) - У цьому методі зондування відстань між комірками збільшується квадратично (на квадрат). Це означає, що якщо відбулася колізія, спочатку алгоритм перевіряє наступну комірку, потім через дві комірки (1^2), потім через три комірки (2^2), і так далі, доки не буде знайдена вільна комірка.

Інші стратегії відкритого зондування - лінійне зондування або подвійне хешування.

У випадку з ланцюжками, коли виникає колізія, створюється "ланцюжок" (зв'язаний список) елементів, які мають однакове хеш-значення. Кожен елемент ланцюжка містить пару ключ-значення. При пошуку значення за ключем, проходять по цьому ланцюжку, перевіряючи кожен елемент, поки не знайде відповідну пару ключ-значення.і

Links

https://habr.com/ru/companies/otus/articles/448350/

Де буде швидше пошук, а де перебір і чому: dict, list, set, tuple⚑

Пошук буде швидше в dict і set, оскільки це хеш-таблиці, доступ до елемента яких відбувається за O(1). Для list і tuple пошук в середньому виконуватиметься за O(n). При цьому кортежі - це незмінний тип, тому вони можуть забезпечити виграш у швидкості порівняно зі списками.

Виняток становить лише дуже малий список до 5 елементів. В цьому випадку інтерпретатору буде швидше пройтись по списку, ніж розраховувати хеш. Також пошук по індексу відбувається за O(1), оскільки списки у Python реалізовані як динамічні масиви, і доступ відбувається за допомогою вказівників.

Якщо у нас дуже великий список, і нам критична швидкість - ми можемо використати NumPy, так як NumPy оптимізований для виконання математичних операцій над масивами. Якщо потрібно обійтись тільки вбудованими методами, можна використати функцію map, яка написана на C, що дозволяє їй працювати швидше, ніж інтерпретований Python-код у for loop.

У Python 2 методи словника keys, values, items повертають список. Тобто перед ітерацією по словнику (або множині) інтерпретатор спочатку створює новий список, що займає додатковий час і пам'ять, але після створення це вже звичайний список. Тобто в Python 2 ітерація по словниках і множинах виконується довше через створення нового списку і копіювання елементів в нього.

У Python 3 ці методи створюють об'єкт-представлення. Це відбувається швидше, ніж створення нового списку в Python 2. Але ітерування по такому представленню повинно займати трохи більше часу, ніж по списку, через розріджене (рідко, нещільно) збереження даних в словниках.

>>> 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