Категории

Язык
Область
Интерпретатор

9 сентября 2016 г. 11:50 (ред. 9 сентября 2016 г. 11:52)
Рассмотрим изменения в словарях, которые возможно будут доступны начиная с 3.6.
Вероятно вы знаете, что словари в Питоне играют огромную роль, можно даже назвать их одной из основополагающих структур, без которых интерпретатор даже собрать не получится, не то что запустить. А коли так, то вы понимаете, что любая модификация данной структуры должна: 1. быть чётко обоснована; 2. проводиться с чрезвычайной осторожностью, ведь в противном случае, если в фундаменте будет трещина, то и весь дом может развалиться.

Судя по всему, у нас уже есть обоснование, а работы по поиску возможных трещин в полном разгаре и выпуск 3.6, намеченный на 16 декабря 2016, уже будет содержать модифицированную реализацию словарей.

Давайте в общих чертах разберёмся, что и как может измениться.

Заплатка, вносящая изменения, зарегистрирована в запросе 27350. Её автор — Инада Наоки — реализовал сжатый упорядоченный словарь, базируясь на концепции, введённой в PyPy ещё в январе 2015-го. Идея не нова и в рассылке python-dev о ней в 2012-м говорил Реймонд Хеттинджер, который даже создал прототип на Питоне.

Если переложить структуры двух видов словарей с Си на Питон, максимально упрощая, то получим примерно следующее:

    # my_dict = {'python': 'value1', 'schema': 'value2', 'c++': 'value3'}

dict_classic = {
'items_count': 3,
'items': [
# (hash, key, value)
('--', '--', '--'),
(-9095698888683775416, 'python', 'value1'),
('--', '--', '--'),
('--', '--', '--'),
('--', '--', '--'),
('--', '--', '--'),
(-799031295762617234, 'c++', 'value3'),
(-4226706071475375297, 'schema', 'value2'),
]
}

dict_compact = {
'items_count': 3,
'items_index': [0, 1, 0, 0, 0, 0, 1, 1],
'items': [
(-9095698888683775416, 'python', 'value1'),
(-4226706071475375297, 'schema', 'value2'),
(-799031295762617234, 'c++', 'value3'),
]
}

Здесь dict_classic — текущее представление объекта словаря и используемой им хеш-таблицы (items), а dict_compact — новое предлагаемое. Видно, что items в первом случае содержит пустые слоты и элементы здесь не следуют в том порядке, в каком были заданы изначально (см. my_dict из первой строки). Во втором случае items не только упорядочен, но и компактен. А для упрощения адресации элементов здесь предусмотрен items_index.

Итак новая реализация позволит: 1. снизить количество выделяемой под словари памяти; 2. сохранять порядок элементов, фактически сводя на нет необходимость в отдельном OrderedDict. Это, конечно, неплохо, но что на счёт быстродействия? Судя по опубликованным в упомянутом выше запросе данным, она останется примерно на том же уровне.

В данный момент заплатка шлифуется, что будет дальше — покажет время.

Наблюдайте, участвуйте.