Эффективный поиск словаря?

Ответ 1

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

Заменить на:

if key in data_dict:

Ответ 2

data_dict.keys() возвращает несортированный список ключей в словаре. Таким образом, каждый раз, когда вы проверяете, есть ли данный ключ в словаре, вы выполняете линейный поиск по списку ключей (операция O (n)). Чем дольше ваш список, тем больше времени требуется для поиска заданного ключа.

Сравните это с data_dict[keyStr]. Это выполняет хэш-поиск, который является операцией O (1). Он не зависит (напрямую) от количества ключей в словаре; даже когда вы добавляете больше ключей, время, чтобы проверить, находится ли данный ключ в словаре, остается постоянным.

Ответ 3

Вы также можете просто использовать

if key in data_dict:

вместо

 if key in data_dict.keys():

Как уже упоминалось, первый представляет собой прямой поиск хеша - предполагаемое смещение вычисляется напрямую, а затем проверяется - оно примерно равно O (1), тогда как проверка ключей - это линейный поиск, который является O (n).

In [258]: data_dict = dict([(x, x) for x in range(100000)])

In [259]: %timeit 999999 in data_dict.keys()
100 loops, best of 3: 3.47 ms per loop

In [260]: %timeit 999999 in data_dict
10000000 loops, best of 3: 49.3 ns per loop

Ответ 4

Это не отвечает на вопрос, а позволяет избежать этого. Попробуйте использовать collections.defaultdict. Вам не понадобятся if/else или try/except.

from collections import defaultdict

data_dict = defaultdict(list)
for keyStr, load_val in data:
    data_dict[keyStr].append(load_val)

Ответ 5

Как отмечали некоторые другие, проблема заключается в том, что key in data_dict.keys() использует неупорядоченный list, возвращенный методом keys() (в Python 2.x), который принимает линейное время O (n) для поиска, что означает, что время работы увеличивается линейно со значением словаря, плюс генерирование список ключей будет занимать больше времени и больше по мере увеличения размера.

С другой стороны, key in data_dict требует в среднем постоянное время O (1) для выполнения поиска независимо от размера словаря, потому что внутри он выполняет hash table look-up. Кроме того, эта хэш-таблица уже существует со своей части внутреннего представления словарей и поэтому не должна быть сгенерирована перед ее использованием.

Python не делает этого автоматически, потому что оператор in знает только тип двух своих операндов, а не их источников, поэтому он не может автоматически оптимизировать первый случай, когда все, что он видит, - это ключ и список.

Однако в этом случае проблему скорости поиска можно вообще избежать, сохранив данные в специализированной версии словаря, называемой defaultdict найден во встроенном модуле collections. Вот как выглядит ваш код, если вы его использовали:

from collections import defaultdict

input_data = defaultdict(float)  # (guessing factory type)
...
data_dict[keyStr] = input_data[keyStr] + load_val

Если для input_data[keyStr] не существует существующей записи, она будет автоматически сгенерирована со значением по умолчанию (0.0 для float в этом примере). Как вы можете видеть, код короче и, скорее всего, быстрее, без необходимости каких-либо тестов if или обработки исключений.

Ответ 6

Это потому, что data_dict.keys() возвращает список, содержащий ключи в словаре (по крайней мере, в Python 2.x). Который, чтобы найти, находится ли ключ в списке, требует линейного поиска.

В то время как попытка доступа к элементу dict напрямую использует превосходные свойства словарей, поэтому доступ почти мгновен.

Ответ 7

В прежние времена мы использовали setdefault:

data_dict.setdefault(keyStr, []).append(load_val)

Ответ 8

Есть что-то похожее на функцию try, которая должна вам помочь: dict.get(key, default)

data_dict[keyStr] = data_dict.get(keyStr, '') + load_val

Ответ 9

В качестве дополнительного анализа я провел простой тест производительности, чтобы увидеть, как метод try/исключением, упомянутый в вопросе, сравнивается с предлагаемым решением использования "если ключ в data_dict" вместо "если ключ в data_dict.keys()" (я используя Python 3.7):

    import timeit

    k = '84782005' # this keys exists in the dictionary
    def t1():
        if k in data_dict:
            pass
    def t2():
        if k in data_dict.keys():
            pass
    def t3():
        try:
            a = data_dict[k]
        except:
            pass

    print(timeit.timeit(t1,number= 100000))
    print(timeit.timeit(t2,number= 100000))
    print(timeit.timeit(t3,number= 100000))

    >> 0.01741484600097465
    >> 0.025949209000827977
    >> 0.017266065000512754

Для ключа, который уже существует в словаре, время поиска, по-видимому, одинаково для попытки/исключения и предлагаемого решения. Однако, если ключ не существует:

    k = '8' # this keys does NOT exist in the dictionary
    def t1():
        if k in data_dict:
            pass
    def t2():
        if k in data_dict.keys():
            pass
    def t3():
        try:
            a = data_dict[k]
        except:
            pass

    print(timeit.timeit(t1,number= 100000))
    print(timeit.timeit(t2,number= 100000))
    print(timeit.timeit(t3,number= 100000))

    >> 0.014406295998924179
    >> 0.0236777299996902
    >> 0.035819852999338764

Кажется, что исключение занимает намного больше времени, чем даже использование .keys()! Итак, я второе решение, предложенное Марком.