Неожиданное Python поведение словаря

Question

У меня есть этот кусок кода:

import time

d = dict()
for i in range(200000):
    d[i] = "DUMMY"

start_time = time.time()

for i in range(200000):
    for key in d:
        if len(d) > 1 or -1 not in d:
            break
    del d[i]

print("--- {} seconds ---".format(time.time() - start_time))

Почему это занимает ~ 15 секунд для запуска?

Но, если я закомментирую del d[i] или внутренний l oop, он работает за ~ 0,1 секунды.

Answer 1

Проблема, с которой вы столкнулись, связана с итерацией даже одного элемента (например, next(iter(d))) словаря, который когда-то был большим, но сильно сократился. Это может быть почти медленной итерацией по всем элементам словаря, если вам не повезло с вашими значениями ha sh. И этот код очень «неудачлив» (как и следовало ожидать, из-за Python ha sh дизайна).

Причина проблемы в том, что Python не перестраивает таблицу ha sh словаря когда вы удаляете предметы. Таким образом, таблица ha sh для словаря, в котором раньше содержалось 200000 элементов, но у которого теперь осталось только 1, по-прежнему содержит более 200000 пробелов (и, вероятно, больше, поскольку на пике она, вероятно, была не совсем полной). ).

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

Это может быть еще хуже, если учесть, что Вы используете целочисленные ключи, которые (в основном) имеют sh для себя (только -1 хеширует что-то еще). Это означает, что первый ключ в «полном» словаре обычно будет 0, следующий 1 и так далее. Когда вы удаляете значения в порядке возрастания, вы будете очень точно сначала удалять самые ранние ключи в таблице, что сделает поиск максимально хуже.

Answer 2

Это потому, что этот

for key in d:
    if len(d) > 1 or -1 not in d:
        break

сломается на первой итерации, поэтому ваш внутренний l oop в основном не работает.

Добавление del[i] заставляет его делать некоторые реальная работа, которая требует времени.

Обновление: хорошо вышеприведенный, очевидно, способ упрощения c: -)

Следующая версия вашего кода показывает то же самое характеристика c:

import time
import gc
n = 140000

def main(d):
    for i in range(n):
        del d[i]        # A
        for key in d:   # B
            break       # B

import dis
d = dict()
for i in range(n):
    d[i] = "DUMMY"


print dis.dis(main)
start_time = time.time()
main(d)
print("--- {} seconds ---".format(time.time() - start_time))

Использование iterkeys не имеет значения.

Если мы построим график времени выполнения для различных размеров n, мы получим (n на x- ось, в секундах по оси y):

, поэтому явно происходит экспоненциальное изменение.

Удаление линии (A) или линии (B) удаляют экспоненциальный компонент, хотя я не уверен, почему.

Обновление 2: На основании ответа @ Blckknght мы можем восстановить некоторую скорость, нечасто перефразируя элементы :

def main(d):
    for i in range(n):
        del d[i]
        if i % 5000 == 0:
            d = {k:v for k, v in d.items()}
        for key in d:
            break

или это:

def main(d):
    for i in range(n):
        del d[i]
        if i % 6000 == 0:
            d = {k:v for k, v in d.items()}
        try:
            iter(d).next()
        except StopIteration:
            pass

занимает меньше половины времени оригинала при большом n (выпуклость на 130000 соответствует объему r 4 работает ..).

Answer 3

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

Это объясняет, почему вы не получаете снижение производительности при удалении внутреннего l oop (вы не вызываете перестройку списка ключей). Это также объясняет, почему l oop работает быстрее, когда вы удаляете строку del d[i] (вы не помечаете список ключей для перестроения).