Dictionary в Python. По мотивам Objects/dictnotes.txt

Dictionary в Python. По мотивам Objects/dictnotes.txt
Автор: Кирилл Лашкевич (Viber)

1. Dictionary в Python
По мотивам Objects/dictnotes.txt Cyril @notorca Lashkevich piątek, 30 sierpnia 13

2. Как создать словарь {}
dict()
PyObject* PyDict_New() piątek, 30 sierpnia 13

3. Сколько словарей в Hello
World? $ python -c "print('Hello world')"
| wc -l piątek, 30 sierpnia 13

4. Сколько словарей в Hello
World? $ python -c "print('Hello world')"
| wc -l
1642 piątek, 30 sierpnia 13

5. Именованные параметры
функицй 1 запись, 1 чтение
1-3 элемента
Часто встречается в обычных
программах на Python piątek, 30 sierpnia 13

6. Поиск метода в классе 1 запись, много чтений
8-16 элементов
При наследовании много неудачных
чтений с последующим поиском в
базовом классе piątek, 30 sierpnia 13

7. Атрибуты и глобальные
пременные Много записей и чтений
4-10 элементов piątek, 30 sierpnia 13

8. Builtins Частые чтение, почти не бывает
записи
~150 строковых ключей (3.3)
По некоторым ключам чтения гораздо
чаще чем по другим piątek, 30 sierpnia 13

9. Удаление повторов,
подсчет элементов Одинократное чтение по каждому из
ключей
Произвольное количество элементов
Многократный доступ по одному ключу
подряд piątek, 30 sierpnia 13

10. Удаление дубликатов dict.fromkeys(seqn).keys()Все операции записи при
конструировании
piątek, 30 sierpnia 13

11. Подсчет элементов в
последовательности for e in seqn:
d[e] = d.get(e,0) + 12 последовательных доступа по
одинаковому ключу
piątek, 30 sierpnia 13

12. Создание индекса из
словаря списков setdefault совмещает 2 поиска в 1м for pnum, page in enumerate(pages):
for w in page:
d.setdefault(w, []).append(pnum)
piątek, 30 sierpnia 13

13. Проверка принадлежности Словари произвольных размеров
Создаются 1 раз и затем мало
изменяются
Много вызовов has_key() и
__contains__() piątek, 30 sierpnia 13

14. Динамические отображения Чередующиеся добавления, удаления,
чтение и перезапись элементов piątek, 30 sierpnia 13

15. Реализация (2.7) Последовательная область памяти с
доступом по индксу typedef struct {
Py_hash_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictKeyEntry;
piątek, 30 sierpnia 13

16. Пустой dict с размером по умолчанию (8
элементов)
>>> d = {}
piątek, 30 sierpnia 13

17. Хеширование ключа Ключ преобразуется в индекс с
помощъю функции hash()
hash() возвращает 32/64bit значение
Для индекса берется n младших бит piątek, 30 sierpnia 13

18. Свойства хеша Для равных значений хеши всегда
равны
Даже если представление значений
разное: 9, 9.0, complex(9,0)
Похожие значения дают сильно
отличающиеся хеши piątek, 30 sierpnia 13

19. >>> d['ftp'] = 21
>>> bits(hash('ftp'))[-8:]
10100001
piątek, 30 sierpnia 13

20. >>> d['ftp'] = 21
>>> bits(hash('ftp'))[-8:]
10100001
piątek, 30 sierpnia 13

21. >>> d['ssh'] = 22
>>> bits(hash('ssh'))[-3:]
101
piątek, 30 sierpnia 13

22. >>> d['ssh'] = 22
>>> bits(hash('ssh'))[-3:]
101
piątek, 30 sierpnia 13

23. >>> d['smtp'] = 25
>>> bits(hash('smtp'))[-3:]
100
piątek, 30 sierpnia 13

24. >>> d['smtp'] = 25
>>> bits(hash('smtp'))[-3:]
100
piątek, 30 sierpnia 13

25. >>> d['time'] = 37
>>> bits(hash('time'))[-3:]
111
piątek, 30 sierpnia 13

26. >>> d['time'] = 37
>>> bits(hash('time'))[-3:]
111
piątek, 30 sierpnia 13

27. >>> d['www'] = 80
>>> bits(hash('www'))[-3:]
010
piątek, 30 sierpnia 13

28. >>> d['www'] = 80
>>> bits(hash('www'))[-3:]
010
piątek, 30 sierpnia 13

29. d = {'ftp': 21, 'ssh': 22,
'smtp': 25, 'time': 37,
'www': 80}
piątek, 30 sierpnia 13

30. Поиск в словаре Вычислить хеш от ключа
Обрезать старшие биты
Взять значение из слота по индексу piątek, 30 sierpnia 13

31. >>> d['smtp']
25
>>> bits(hash('smtp'))[-3:]
100
piątek, 30 sierpnia 13

32. Перебор всех элементов Словари возвращают свои ключи или
значения в порядке отличном от
порядка добавления piątek, 30 sierpnia 13

33. >>> print d
{'ftp': 21, 'www': 80, 'smtp':
25, 'ssh': 22, 'time': 37}
piątek, 30 sierpnia 13

34. >>> d.keys()
['ftp', 'www', 'smtp', 'ssh',
'time']
piątek, 30 sierpnia 13

35. >>> d.values()
[21, 80, 25, 22, 37]
piątek, 30 sierpnia 13

36. Коллизии Разные ключи пытаются доступиться
по одинаковому индексу
Находим первое свободное место piątek, 30 sierpnia 13

37. >>> d = {}
piątek, 30 sierpnia 13

38. >>> d['smtp'] = 21
piątek, 30 sierpnia 13

39. >>> d['smtp'] = 21
piątek, 30 sierpnia 13

40. >>> d['dict'] = 2628
piątek, 30 sierpnia 13

41. >>> d['dict'] = 2628
piątek, 30 sierpnia 13

42. >>> d['svn'] = 3690
piątek, 30 sierpnia 13

43. >>> d['svn'] = 3690
piątek, 30 sierpnia 13

44. >>> d['ircd'] = 6667
piątek, 30 sierpnia 13

45. >>> d['ircd'] = 6667
piątek, 30 sierpnia 13

46. >>> d['zope'] = 9673
piątek, 30 sierpnia 13

47. >>> d['zope'] = 9673
# 2 из 5ти элементов на своих
ожидаемых местах
piątek, 30 sierpnia 13

48. Коллизии и очередность Поскольку из за коллизий элементы
могут находится не по своим
"естественным" индексам порядок
элементов зависит от порядка
добавления piątek, 30 sierpnia 13

49. Поиск первой свободной
ячейки Последовательный поиск плох для int
ключей pertrurb = hash
while (<слот занят>) {
slot = (5*slot) + 1 + perturb;
perturb >>= 5;
}
piątek, 30 sierpnia 13

50. >>> d['svn']
3690
piątek, 30 sierpnia 13

51. >>> d['ircd']
6667
piątek, 30 sierpnia 13

52. >>> d['nsca']
KeyError: 'nsca'
piątek, 30 sierpnia 13

53. >>> d['netstat']
KeyError: 'netstat'
piątek, 30 sierpnia 13

54. Не все поиски одинаковы Некоторые находят результат сразу
Некоторым нужны несколько итераций piątek, 30 sierpnia 13

55. threes = {3: 1, 3+8: 2, 3+16: 3,
3+24: 4, 3+32: 5}
piątek, 30 sierpnia 13

56. Удаление элементов Нелзя просто так взять, и пометить
ячейку как пустую
Необходимо вставить специальный
"dummy" элемент piątek, 30 sierpnia 13

57. del d['smtp']
piątek, 30 sierpnia 13

58. del d['smtp']
d['ircd'] ???
piątek, 30 sierpnia 13

59. del d['smtp']
#Заменяем на "dummy" слот
#Может быть использован снова
piątek, 30 sierpnia 13

60. del d['smtp']
#Заменяем на "dummy" слот
#Может быть использован снова
piątek, 30 sierpnia 13

61. >>> del d['svn'], d['dict'],
d['zope']
>>> d['ircd']
piątek, 30 sierpnia 13

62. Увеличение размера
таблицы Таблица заполнена максимум на 2/3
2.7: < 50k size × 4
> 50k size × 2
3.3: size × 2 piątek, 30 sierpnia 13

63. >>> d = {}
piątek, 30 sierpnia 13

64. d = dict.fromkeys(words[:5])
# 40% коллизий
# Заполнен на ⅔, resize
piątek, 30 sierpnia 13

65. d['abash'] = None
# размер ×4 до 32
# 0% коллизий
piątek, 30 sierpnia 13

66. d = dict.fromkeys(words[:21])
# 29% коллизий
# Заполнен на ⅔
piątek, 30 sierpnia 13

67. d['abode'] = None
# размер ×4 до 128
# 9% коллизий
piątek, 30 sierpnia 13

68. d = dict.fromkeys(words[:85])
# 33% коллизий
# Заполнен на ⅔
piątek, 30 sierpnia 13

69. Время доступа к элементам Растет по мере заполнения словаря
Затем резко умешьшается после
изменения размера
Среднее время доступа ОК piątek, 30 sierpnia 13

70. Поиски vs размер
piątek, 30 sierpnia 13

71. Время vs размер
piątek, 30 sierpnia 13

72. Удаление элементов Не уменьшает размер таблицы
Таблица может уменьшиться только
при добавлении элементов piątek, 30 sierpnia 13

73. Порядок элементов Во время изменения размера порядок
элементов может полностью
поменяться
Добавление элементов во время
итерации запрещено
RuntimeError: dictionary changed size during iteration piątek, 30 sierpnia 13

74. Свой __hash__() Хорошо перемешать биты
Равные хеши для равных элементов
__eq__() должен быть
Быстро вычисляется piątek, 30 sierpnia 13

75. Пример __hash__() class Point(object):
def __init__(self, x, y):
self.x, self.y = x, y
def __eq__(self, p):
return self.x==p.x and self.y==p.y
def __hash__(self):
return hash(self.x) ^ hash(self.y)
piątek, 30 sierpnia 13

76. oCERT #2011-003 Хэш для str, bytes и datetime
смешивается с "солью" уникальной
для каждого процесса Python
pre 3.3: -R option
3.3: by default piątek, 30 sierpnia 13

77. Python 3: Split-table словари.
Общая таблица с ключами для разных
таблиц со значениями
piątek, 30 sierpnia 13

78. Спасибо http://blip.tv/pycon-us-
videos-2009-2010-2011/pycon-2010-
the-mighty-dictionary-55-3352147
Python source code piątek, 30 sierpnia 13