Множества и словари

Внимание: подробный рассказ про хеш-функции и хеш-таблицы см. в записях предыдущих лет.

Множества и hash()

• id() — уникальность объекта, ничего не знает про равенство

• сравнение двух объектов может быть тяжёлой операцией

• hash() — числовой хеш от константного объекта

  • создаётся вместе с объектом
    • для изменяемого объекта (например, списка) смысла не имеет
  • если хеши не равны, объекты тоже не равны
    • обратное, в целом, неверно

Множества

• Задаются перечислением или сборкой в { }

• Поддерживают теоретико-множественные операции "| & ^ -"

Множества в Python реализованы как хеш-таблицы:

• размер таблицы приблизительно пропорционален количеству элементов (изменение размера как в списках)
• повторное хеширование при коллизии

• константный поиск в среднем (+линейное масштабирование)

Элементы множества неупорядочены (в действительности, почти упорядочены по хешам, с учётом перехеширования и масштабирования):

   1 >>> s = {str(i) for i in range(10,30)}
   2 >>> s
   3 {'18', '19', '25', '29', '23', '27', '16', '11', '17', '20', '15', '28', '14', '24', '26', '13', '22', '10', '12', '21'}
   4 >>> [hash(c)%128 for c in s]
   5 [8, 10, 11, 10, 25, 32, 39, 40, 39, 64, 72, 76, 95, 100, 106, 110, 115, 122, 125, 127]
   6 

Словари

Задача: хранить произвольные объекты, каждый из которых взаимно однозначно соответствует хорошо хешируемой константе.

• (до Python3.6 — множество ключей + ссылка на хранимый объект)

• (современный Python) хеш-таблица + журнал

  • Сохраняет порядок добавления элементов

  • Операция добавления легче операции удаления (кому нужно удалять из словаря?)

Использование

• dict — как массив с константными элементами вместо индекса

• Задание и обращение к элементу
• Циклический конструктор
• Работа со словарём

• keys(), values(), items()

  • цикл по словарю

• [] vs .get() vs .setdefault()

• .update() и прочие методы

• Относительно новое — | и |=

Словари внутри Python:

• globals()/locals()

     1 >>> QQ
     2 Traceback (most recent call last):
     3   File "<stdin>", line 1, in <module>
     4 NameError: name 'QQ' is not defined
     5 >>> globals()
     6 {'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <_frozen_importlib_external.SourceFileLoader object at 0x7f434c1b4190>, '__spec__': None, '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>, '__cached__': None, 'rlcompleter': <module 'rlcompleter' from '/usr/lib64/python3.7/rlcompleter.py'>}
     7 >>> globals()["QQ"]=100500
     8 >>> QQ
     9 100500
    10 >>> globals()
    11 {'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <_frozen_importlib_external.SourceFileLoader object at 0x7f434c1b4190>, '__spec__': None, '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>, '__cached__': None, 'rlcompleter': <module 'rlcompleter' from '/usr/lib64/python3.7/rlcompleter.py'>, 'QQ': 100500}
  

• Именные параметры функции

     1 >>> def fun(*argp, **argn):
     2 ...     print(argp, argn)
     3 ...
     4 >>> fun(1,2,3,a=4,b=5)
     5 (1, 2, 3) {'a': 4, 'b': 5}
     6 
     7 >>> def fun(a=1, b=2):
     8 ...   print(a,b)
     9 ...
    10 >>> d = dict(a="QQ", b="PP")
    11 >>> fun(**d)
    12 QQ PP
    13 >>> d = {"a":"QQ", "b":"QKRQ"}
    14 >>> fun(**d)
    15 QQ QKRQ
  

• Ещё немного занудства про параметры функций: значения по умолчанию ≠ именные параметры

Модуль collections

• deque

• namedtuple

• Counter

• defaultdict

  • Мелкий изврат: def tree(): return defaultdict(tree) (тут)

• …

Д/З

0. Прочитать

   • про множества TODO

   • про словари в учебнике и в документации

TODO