# конспект · шаг 7 из 7
Конспект: что внутри list, dict и set
Понятия
Ёмкость списка - сколько мест выделено под ссылки; длина - сколько занято. Список хранит ссылки по 8 байт, объекты лежат отдельно.
Компактный словарь (Python 3.6+) - таблица индексов (номера записей, по байту на ячейку до 128 ячеек) плюс плотный массив записей в порядке вставки.
Пустышка - метка удалённого ключа в таблице: поиск проходит её насквозь, вставка может занять. «Пусто» обрывает поиск.
Договор хеша: a == b ⇒ hash(a) == hash(b), и хеш объекта не меняется, пока он лежит в множестве
или словаре.
Что унести
LIST
ёмкость: n + n // 8 + 6, кратно 4 -> 4, 8, 16, 24, 32, 40, 52, 64, 76
миллион append: 86 переездов, 8,45 копии на элемент (удвоение: 19 и 1,05)
копий всего < n · r / (r − 1): множитель решает константу, не асимптотику
O(1): a[i], len, append (амортизированно), pop()
O(n): insert(0, x), pop(0), del a[0], x in a
10⁶ float: ссылки 8 МБ + объекты 23 МБ; array('d') - 7,8 МБ
[[0] * 3] * 3 - три ссылки на одну строку
DICT
поиск: i = h & маска, perturb = h
perturb >>= 5; i = (5·i + perturb + 1) & маска
хеш целого = само число: 0..299 - 300 проб, k << 16 без perturb - 45150
запас записей = 2/3 таблицы; удаление запас не возвращает
перестройка: степень двойки ≥ max(8, 3 · живых ключей)
пороги роста: 6, 11, 22, 43, 86 ключей (таблицы 16, 32, 64, 128, 256)
порядок вставки гарантирован с Python 3.7
SET
ячейка: хеш + ключ, 16 байт; первые 8 ячеек внутри объекта
сравнение: хеш -> тот же объект? -> ==
коллизия: ячейка и 9 соседних, потом прыжок 5·i + 1 + perturb
перестройка при 60% (вместе с пустышками), рост вчетверо: 8, 32, 128, 512
{1, 1.0, True} == {1}; hash(-1) == -2; хеш int - по модулю 2⁶¹ − 1
два разных NaN - два элемента; один и тот же NaN находится по тождеству
ЧТО ВЗЯТЬ ВМЕСТО LIST
края (очередь, окно) deque: блоки по 64, O(1) на краях, d[i] - O(n)
минимум из меняющегося heapq: куча в списке, O(log n)
поиск в отсортированном bisect: O(log n), но insort сдвигает - O(n)
много чисел одного типа array / NumPy: без объектов
200 000 вставок: insort 4,3 с, heappush 20 мс
Ловушки джокера
Очередь на list. pop(0) сдвигает все ссылки: сто тысяч вставок в начало - две секунды.
«Список - 8 байт на элемент». Это только ссылки; число в списке стоит ещё 24-28 байт объекта.
Таблица через повтор списка. [[0] * m] * n - n ссылок на одну строку.
Удалённый ключ как пустая ячейка. Поиск обрывается и теряет ключи из той же цепочки.
Хеш по изменяемым полям. Объект лежит в множестве, но его не найти.
__eq__ без согласованного __hash__. Либо unhashable, либо дубликаты в множестве.
Словарь-кеш «без роста». Удаление не возвращает запас: периодическая перестройка всё равно будет.
insort на потоке вставок. Поиск за log n, вставка за n - квадрат в сумме.
Индекс в deque в цикле. Каждое d[i] идёт по блокам; обходить дек надо самим for.
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий