dict.keys()
Данная статья посвящена внутрянке самого кода views над словарями в CPython; если вы хотите узнать о том, как устроены словари как хэш-таблицы в Python, и какие там оптимизации применены, то рекомендую эту прекрасную статью, а также полезные комменты в начале dictobject.c
Введение
В одном из чатов для питонистов заметил такой комментарий:
a in dictionary # O(1)
a in dictionary.keys() # O(n)
a in dictionary.values() # O(n) и пачка морковок от коллег
где n - это количество занятых элементов в хэш-таблице.
Меня здесь сразу смутила вторая строка. Ведь, естественно, почему бы dict.keys() действовать столь неэффективно, когда это всего лишь view над dict-ами?
При поиске по хэш-таблицам амортизированная сложность — O(1). Значит, и по keys() должна быть такая же, иначе авторы CPython — вредители. https://en.wikipedia.org/wiki/Hash_table
Я вступил в полемику с автором вышеупомянутого комментария, где он упирал на то, что внутри dict_keys и dict_values (структур, которые возвращаются из keys() и values() соответственно), происходит полное копирование все ключей (значений) в отдельный питоянчий список, упирая на вот это место в коде:
Но мой собеседник настаивал. Де-скать, там вью, внутри которого list, а поэтому поиск медленный, а keys() быстрее list(), потому что внутри Питона там оптимизации свои.
Меня это, честно сказать, ошарашило и даже возмутило. Ведь, все мы знаем, что во втором Питоне так и было, но товарищ упирал на то, что в третьем питоне list по-прежнему неявно создаётся, но теперь нам возвращают не сам list, а вьюху над этим листом (sic!).
Надежда
In 2.x, you do not want to call keys, because that generates a list of the keys, instead of a KeysView. You could use iterkeys, but that may generate an iterator or something else that's not O(1). So, just use the dict itself as a sequence.
Even in 3.x, you don't want to call keys, because there's no need to. Iterating a dict, checking its contains, and in general treating it like a sequence is always equivalent to doing the same thing to its keys, so why bother? (And of course building the trivial KeyView, and accessing through it, are going to add a few nanoseconds to your running time and a few keystrokes to your program.)
И тут я первым делом расчехлил свой IPython...
Как мы видим, инструкция `middle in d.keys()` отрабатывает действительно дольше, примерно в 2 раза, чем просто `middle in d`. А поиск по списку той же длины — отрабатывает несколько дольше (ns = 10 ** -9, us = 10 ** -6, ms = 10 ** - 3, то есть, разница на 6 порядков, в миллион раз!).
Если в случае разницы между `in x` и `in d.keys()` ещё можно говорить о каком-то оверхэде, то разница со списками уже явно алгоритмическая!
Кажется, мы уломали всех своей железной логикой, но всё же остаётся непонятным вопрос: а как же тогда так быстро происходит копирование всех ключей в новый список? Или не происходит?.. Но ведь мы же видели код выше, явно создаётся и заполняется новый list.
Попробуем разобраться дальше, пока что всё ещё timeit-ом:
Очень интересно получается: оверхед — именно на создание вьюхи над keys (операция `x.keys()`). Можно даже просто сложить время на `x.keys()` со временем `in k` (dict_keys), и получим примерно время `in x.keys()`.
Но в то же время, просто list создать — это капец как долго, это вот вообще не то же самое, что просто создать dict_keys. В общем, вывод пока такой, что list как-то не создаётся. Но мы же видели код, и он точно от третьего питона, а не от второго (я проверял!).
Заглубляемся
Давайте попытаемся реально разобраться и обратиться к исходникам: поиск на in в `dict_keys` происходит явно в функции dictkeys_cotains (больше некому):
static int
dictkeys_contains(_PyDictViewObject *dv, PyObject *obj)
{
if (dv->dv_dict == NULL)
return 0;
return PyDict_Contains((PyObject *)dv->dv_dict, obj);
}Почему эта функция? Пока что нам достаточно того, что практически все методы dict_keys начинаются с префикса dictkeys_, а внутри Python contains является практически синонимом оператора `in`.
Итак, получается, для contains у dict_keys остаётся ссылка на оригинальный dict, которую он невозбранно эксплуатирует (а также для многих других операций, типа iter(), len(), конвертации dict в set итд, ищите по данному файлу по запросу `dv_dict`). Поиск происходит непосредственно по оригинальному словарю.
Хм, так что же получается, для поиска есть оптимизация, но список всё равно для каких-то целей создаётся? А зачем?
И как тогда так быстро на `d.keys()` строится внутренний list в dict_keys, на много порядков быстрее, чем, если вызывать list(d)? (примерно на 6 порядков):
static PyObject * dict_keys(PyDictObject *mp)
Видимо, потому что keys() создаются не тем методом, а этим:
static PyObject *
dictkeys_new(PyObject *dict, PyObject *Py_UNUSED(ignored))
{
return _PyDictView_New(dict, &PyDictKeys_Type);
}Обратимся к описанию объекта `mapp_methods` (это кусочек, который отвечает за методы словаря). Здесь видно, что питонячья функция `keys()` внутри работает через сишную функцию `dictkeys_new`:
static PyMethodDef mapp_methods[] = {
DICT___CONTAINS___METHODDEF
{"__getitem__", (PyCFunction)(void(*)(void))dict_subscript, METH_O | METH_COEXIST,
getitem__doc__},
{"__sizeof__", (PyCFunction)(void(*)(void))dict_sizeof, METH_NOARGS,
sizeof__doc__},
DICT_GET_METHODDEF
DICT_SETDEFAULT_METHODDEF
DICT_POP_METHODDEF
DICT_POPITEM_METHODDEF
{"keys", dictkeys_new, METH_NOARGS,
keys__doc__},
{"items", dictitems_new, METH_NOARGS,
items__doc__},
{"values", dictvalues_new, METH_NOARGS,
values__doc__},
{"update", (PyCFunction)(void(*)(void))dict_update, METH_VARARGS | METH_KEYWORDS,
update__doc__},
DICT_FROMKEYS_METHODDEF
{"clear", (PyCFunction)dict_clear, METH_NOARGS,
clear__doc__},
{"copy", (PyCFunction)dict_copy, METH_NOARGS,
copy__doc__},
DICT___REVERSED___METHODDEF
{"__class_getitem__", Py_GenericAlias, METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
{NULL, NULL} /* sentinel */
};Здесь перечислены основные методы над диктами. За полным список функций и полей идите в PyDict_Type:
Новые выводы
На самом деле, инициализация dict_keys совсем другая, чем утверждалось изначально, и уж точно без копирования всех ключей, и получается всего лишь прокся на оригинальный dict (в поле dv_dict) (но при этом происходят некоторые неприятные задействования GC):
PyObject *
_PyDictView_New(PyObject *dict, PyTypeObject *type)
{
_PyDictViewObject *dv;
if (dict == NULL) {
PyErr_BadInternalCall();
return NULL;
}
/* Волшебная проверка */ if (!PyDict_Check(dict)) {
/* XXX Get rid of this restriction later */ PyErr_Format(PyExc_TypeError,
"%s() requires a dict argument, not '%s'",
type->tp_name, Py_TYPE(dict)->tp_name);
return NULL;
}
dv = PyObject_GC_New(_PyDictViewObject, type);
if (dv == NULL)
return NULL;
Py_INCREF(dict);
dv->dv_dict = (PyDictObject *)dict;
_PyObject_GC_TRACK(dv);
return (PyObject *)dv;
}Видимо, из-за выделения памяти и задействования GC и получается такой оверхэд.
К слову, `PyDict_Check` всего лишь проверяет на то, является ли объект сабклассом класса dict. Есть ещё более сильная проверка, `PyDict_CheckExact`, которая проверяет, что класс является ровно объектом типа dict:
#define PyDict_Check(op) \
PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_DICT_SUBCLASS)
#define PyDict_CheckExact(op) Py_IS_TYPE(op, &PyDict_Type)По итогу имеем, что все вьюхи над диктами внутри себя содержат в основном вот эту очень маленькую штучку, со стандартным набором полей для PyObject + указатель на оригинальный dict: dv_dict:
typedef struct {
PyObject_HEAD
PyDictObject *dv_dict;
} _PyDictViewObject;Помимо этого у данных объектов присутствует некий набор функций. Там хитрая инициализация через `_PyDictView_New` и `PyVarObject_HEAD_INIT` на основе их типа (один из трёх):
PyObject_GC_New(_PyDictViewObject, type)
Так что по факту объект получается несколько побольше и одного из трёх видов. Вот картинки для сравнения:
PyDictItems_Type, PyDictKeys_Type, PyDictValues_Type: они все довольно похожи по инициализации и структуре, и стараются использовать оригинальный dict по максимуму, а отличаются только именем типа и реализацией некоторых методов.
Они все в каком-то смысле "унаследованы" от _PyDictViewObject по набору полей, то есть, содержат стандартный поля питонячьего объекта PyObject + поле dv_dict, ссылка на оригинальный словарь.
Здесь же и видим, что вышеупомянутый `dictkeys_contains()` также присутствует в объекте `dict_keys`, но через `dictkeys_as_sequence`:
Ради смеха
Очевидно, что итерирование и поиск у dict_keys и dict_views будет отличаться, а вот у dict_keys и dict_items может несколько совпадать contains, и по факту в обоих случаях вызывать поиск по оригинальному словарю (сравните методы dictitems_contains и dictkeys_contains:
На самом деле выглядит не очень-то и одинаково!
Но у dictitems_contains совсем другая цель. Она старается вести себя как список тьюплов `(k, v)`, словно бы `list(dict.items())`.
Практически половина кода в нём — это проверки входных данных и распаковка входного тьюпла (до строки 12); а затем —получение из оригинального словаря значения по ключу с проверкой, и проверка на полное равенство значения найденного и входного... В целом, похоже :)
В качестве заключения
Что же касается той штуки, которая приводилась как аргумент в начале статьи (функция dict_keys), то она не используется напрямую dict-ами, по крайней мере, в третьем питоне.
Она используется всякой внутрянкой для создания (копирования) неймспейсов, модулей, скоупов, и других оптимизаций (насколько я порыскал по коду). Опосредованно через PyDictKeys:
PyObject *
PyDict_Keys(PyObject *mp)
{
if (mp == NULL || !PyDict_Check(mp)) {
PyErr_BadInternalCall();
return NULL;
}
return dict_keys((PyDictObject *)mp);
}(за примерами использования см. https://github.com/python/cpython/search?l=C&q=PyDict_keys)
В основном она используется для внутренних структур компилятора/интерпретатора; часто для интроспекции и возврата внутрянки из CPython в Python, для функций а-ля dir(), repr(), и ещё почему-то в библиотеке csv.
Кстати, dir() для всех объектов только так и работает, втч и для модулей, но там своя реализация.