Время Сложность поиска первого элемента в словаре в Python 3.7+

Question

Начиная с Python 3.7, словари сохраняют порядок на основе вставки.

Похоже, вы можете получить первый элемент в словаре, используя next(iter(my_dict))?

Мой вопрос по поводу Большая O временная сложность этой операции?

Можно ли рассматривать next(iter(my_dict)) как операцию с постоянным временем (O (1))? Или как лучше всего получить первый элемент в словаре за постоянное время?

Причина, по которой я спрашиваю, заключается в том, что я надеюсь использовать это для кодирования интервью, где значительный акцент делается на время сложность вашего решения, а не скорость его работы в миллисекундах.

Answer 1

Это, вероятно, лучший способ (сейчас вы получаете первый ключ, next(iter(d.values())) получает ваше значение).

Эта операция (любая итерация через keys, values или items по крайней мере, для комбинированных таблиц повторяет через массив, содержащий словарные записи :

PyDictKeyEntry *entry_ptr = &DK_ENTRIES(k)[i];
while (i < n && entry_ptr->me_value == NULL) {
    entry_ptr++;
    i++;
}

entry_ptr->me_value содержит значение для каждого соответствующего ключа.

Если ваш словарь создан заново, он находит первый вставленный элемент во время первой итерации (массив записей словаря доступен только для добавления, следовательно, сохраняется порядок).

Если ваш словарь был изменен (вы удалили много элементов), в худшем случае это может привести к O (N), чтобы найти первый (среди оставшихся элементов) вставленный элемент (где N общее количество оригинальных предметов). Это происходит из-за того, что словари не изменяют размер при удалении элементов, и, как следствие, entry_ptr->me_value составляет NULL для многих записей.

Обратите внимание, что это CPython Speci c. Я не знаю, как другие реализации Python реализуют это.