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

Порядок ключів у dict (insertion order)⚑

Summary

Починаючи з Python 3.7, словники гарантовано зберігають порядок вставки ключів на рівні специфікації мови. У CPython це працювало як деталь реалізації з 3.6 завдяки переходу на compact dict layout - окремий компактний масив записів зберігається саме в тому порядку, в якому ключі додавалися, а хеш-таблиця тримає лише невеликі індекси в цей масив.

Гарантія мови

З "What's New in Python 3.7":

"the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec."

До 3.6 порядок не гарантувався взагалі - він залежав від послідовності вставок, видалень та розмірів таблиці. У 3.6 CPython отримав нову внутрішню структуру, яка випадково (з точки зору контракту) почала зберігати порядок; у 3.7 цю властивість зафіксували в специфікації, тому інші реалізації Python (PyPy, MicroPython) також зобов'язані її підтримувати.

Compact dict layout (як це працює всередині CPython)

До 3.6 словник зберігав записи безпосередньо в комірках хеш-таблиці (див. Як працює хеш-таблиця): кожен слот містив (hash, key, value) і займав фіксований розмір. Розріджена таблиця з ~⅓ порожніх слотів давала оверхед пам'яті, а ітерація проходила всі слоти у внутрішньому порядку хеш-індексів.

Compact layout розділяє цю структуру на дві частини:

• dk_indices - компактний масив маленьких цілих, розміром 2^dk_log2_size. Це власне хеш-таблиця: за хешом ключа знаходимо позицію в цьому масиві, де лежить індекс запису в наступному масиві. Розмір кожного індексу адаптивний (1, 2, 4 або 8 байт залежно від кількості записів - поле dk_log2_index_bytes), тому для малих словників він майже не займає пам'яті.
• dk_entries - щільний масив записів (hash, key, value), заповнений строго в порядку вставки ключів. Без дірок між активними записами.

dk_indices (sparse hash table):  [ix0][ix1][...][ixN]   -> N = 2^dk_log2_size
                                    │              │
                                    ▼              ▼
dk_entries (dense, insertion order): [(h,k,v)_0][(h,k,v)_1][...]

Структура задана у Include/internal/pycore_dict.h (struct _dictkeysobject, поля dk_log2_size, dk_log2_index_bytes, dk_kind, dk_indices, далі dk_entries).

Наслідки

• Ітерація йде по dk_entries у природному порядку - тобто в порядку вставки. Жодних додаткових структур для цього не потрібно.
• Економія пам'яті. Розріджена частина (dk_indices) тримає лише маленькі цілі, а не повні (hash, key, value). Реальні записи зберігаються щільно. Це помітно зменшує оверхед пам'яті відносно докомпактної моделі - точний виграш залежить від розміру словника і ширини індексів (1-8 байтів).
• Видалення лишає "дірку" у dk_entries (record позначається як видалений), але не змінює позиції решти. При накопиченні занадто багатьох видалених записів словник перебудовується (resize) - це не повертає dict до "невпорядкованого", але порядок живих ключів зберігається.

Що НЕ гарантується

• Гарантія insertion order не означає, що порядок збігається з алфавітним чи числовим. Для впорядкування за значенням ключа все одно потрібен sorted(d.items()) або еквівалент.
• Гарантія стосується тільки dict і його підкласів (включно з defaultdict). set insertion order не зберігає.
• dict.popitem() повертає останній доданий елемент (LIFO) - ця гарантія з'явилася з тієї ж зміни в 3.7.
• Поведінка не гарантована для зовнішніх C-розширень, які реалізують свої mapping-типи поза межами dict.

Зв'язок з OrderedDict

collections.OrderedDict існував задовго до 3.7 і реалізовував insertion order через явний двозв'язний список. Після 3.7 його єдиними неунікальними перевагами залишаються:

• move_to_end(key, last=True|False) - переміщення існуючого ключа в початок/кінець.
• Рівність з урахуванням порядку: OrderedDict([("a",1),("b",2)]) != OrderedDict([("b",2),("a",1)]), тоді як dict порівнює лише вміст без урахування порядку.

Якщо ці дві властивості не потрібні - стандартний dict після 3.7 повністю покриває використання OrderedDict.

Links

• What's New in Python 3.7 - dict insertion order
• Include/internal/pycore_dict.h (CPython source)
• PEP 468 - Preserving the Order of **kwargs

Як set порівнює значення? Кейс із кастомним __eq__⚑

Summary

set (і dict) спершу шукає за __hash__, і лише при збігу хешів викликає __eq__. Якщо реалізувати __eq__ без __hash__ - Python робить клас нехешованим (__hash__ = None), і вкладати екземпляри в set не можна.

Алгоритм пошуку в set:

1. Python обчислює hash(obj) - викликає __hash__.
2. Шукає bucket з цим хешем.
3. Якщо bucket не порожній - викликає __eq__ для перевірки логічної рівності (хеш-колізії можливі, тому самого хешу недостатньо).

Кейс із кастомним класом:

class Point:
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __eq__(self, other):
        return isinstance(other, Point) and self.x == other.x and self.y == other.y

    # __hash__ is implicitly set to None - class becomes unhashable

Спроба {Point(1, 2), Point(1, 2)} дасть TypeError: unhashable type: 'Point'.

Якщо додати __hash__:

class Point:
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __eq__(self, other):
        return isinstance(other, Point) and self.x == other.x and self.y == other.y

    def __hash__(self):
        return hash((self.x, self.y))

{Point(1, 2), Point(1, 2)}  # {<Point ...>} - single element

Інваріант: якщо a == b, то hash(a) == hash(b). Інакше:

• два рівні об'єкти потраплять у різні bucket'и;
• set ніколи не дійде до __eq__-перевірки;
• множина "забуде", що вони рівні, і збереже обидва.

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

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

Open addressing (стратегія CPython)

При колізії алгоритм не створює окрему структуру для конфліктуючих ключів - він шукає іншу вільну комірку у тому ж самому масиві. Пошук наступної комірки називається пробінгом (probing). Найпростіші його варіанти - лінійний (i+1, i+2, …) і квадратичний (i+1, i+4, i+9, …) - використовуються в навчальних реалізаціях, але страждають від кластеризації колізій.

CPython використовує власну схему пробінгу з перетурбацією (perturbation), яка залучає всі біти хешу, а не лише ті, що потрапили в початковий індекс. Це знижує кластеризацію для типових структур ключів. Формула наступного індексу взята з коментаря "Major subtleties ahead" у Objects/dictobject.c (CPython main, актуальна на момент написання):

#define PERTURB_SHIFT 5

perturb >>= PERTURB_SHIFT;
i = (i*5 + perturb + 1) & mask;     /* mask = size - 1, size is a power of 2 */

perturb ініціалізується значенням хешу і на кожній ітерації зсувається на PERTURB_SHIFT біт вправо, поступово підмішуючи у пробінг старші біти хешу. Вибір значення 5 для PERTURB_SHIFT - результат експериментів Tim Peters (з того ж коментаря у джерелі): значення оптимізує сумарну кількість колізій, але 4 чи 6 дають порівнянний результат.

Алгоритм пошуку ключа:

1. Обчислити hash(key), взяти index = hash & (size - 1) (size - степінь двійки).
2. Якщо комірка порожня - ключа немає.
3. Якщо у комірці є ключ і його __eq__ дорівнює шуканому - повернути значення.
4. Інакше це колізія - обчислити наступний індекс за схемою пробінгу з перетурбацією і повторити.

При видаленні елемента на його місце ставиться спеціальний маркер dummy (tombstone) замість повного очищення комірки - інакше пошук міг би зупинитися на порожньому слоті, не дійшовши до ключа, який раніше при колізії перейшов далі.

Переваги open addressing у CPython над chaining

• Cache locality. Усі дані лежать в одному суцільному масиві, що добре дружить з кешем процесора. Chaining натомість змушує переходити по вказівниках між елементами ланцюжка, які лежать у довільних місцях heap'у.
• Менше алокацій. Не потрібно виділяти окремі вузли списку при кожній колізії.
• Передбачуваний layout. Розмір таблиці завжди степінь двійки; пробінг не вимагає додаткових структур.

Chaining (для порівняння)

У реалізаціях з chaining (Java HashMap, C++ std::unordered_map) кожна комірка таблиці зберігає вказівник на ланцюжок (зв'язаний список або, у нових версіях Java, збалансоване дерево) елементів з однаковим індексом. Пошук - спочатку по індексу, потім по ланцюжку через __eq__. Простіша модель, але гірша cache locality і додаткові алокації на колізію.

Links

• Objects/dictobject.c (CPython source)
• https://habr.com/ru/companies/otus/articles/448350/

Що таке досконала хеш-функція? Чи вирішує вона колізії⚑

Summary

Досконала хеш-функція - це функція, яка для заздалегідь відомого фіксованого набору ключів не дає жодної колізії: кожен ключ потрапляє в унікальний bucket. Тобто вона не "вирішує" колізії - вона їх просто не створює.

Коли застосовується:

• Компілятори - для розпізнавання ключових слів мови (if, for, class).
• Таблиці маршрутизації, конфігурації з фіксованими опціями.
• Lookup-таблиці у статичних структурах, де набір ключів відомий на етапі компіляції.

Властивості:

• Працює лише для заздалегідь заданого набору ключів. Як тільки додається новий ключ - гарантія зникає.
• Зазвичай створюється спеціальними інструментами (gperf, cmph тощо), які підбирають коефіцієнти функції під конкретний набір.
• Швидкість пошуку - O(1) без жодних додаткових перевірок (__eq__ не потрібний для розрізнення колізій).

Універсальні хеш-функції у словниках і множинах Python (hash()) не є досконалими - вони працюють для довільних ключів і тому покладаються на open addressing + __eq__ для розв'язання можливих колізій.

Де буде швидше пошук, а де перебір і чому: 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