defaultdict против инициализации элемента dict

Я пытаюсь оптимизировать производительность скрипта, который ищет похожие слова в лексиконе для каждого заданного слова.

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

word_dict = {}
get = word_dict.get
for letter_n_gram in word:
    for entry in lexicon[n_gram]:
        word_dict[entry] = get(entry, 0) + 1

Эта реализация работает, но скрипт мог бы работать быстрее, заменив dict на collections.defaultdict.

word_dd = defaultdict(int)
for letter_n_gram in word:
    for entry in lexicon[n_gram]:
        word_dd[entry] += 1

Никакой другой код не был изменен.

У меня сложилось впечатление, что оба фрагмента кода (самое главное добавление очков) должны работать одинаково, т.е. если ключ существует, увеличьте его значение на 1, если он не существует, создайте ключ и установите значение равным 1.

Однако после запуска нового кода некоторые ключи имели значения 0, что я считаю логически невозможным.

Является ли моя логика или знание функциональности defaultdict ошибочными? Если нет, то как любое значение в word_dd может быть установлено равным 0?

редактировать: я также очень уверен, что никакая другая часть скрипта не искажает эти результаты, поскольку я проверяю словарь сразу после показанного кода, используя:

for item in word_dd.iteritems():
    if item[1] == 0:
        print "Found zero value element"
        break

python dictionary defaultdict
person Deutherius    schedule 13.04.2014    source источник
comment
Какие ключи имели значение 0? Вы уверены, что эти ключи уже есть в словаре?   -  person thefourtheye    schedule 13.04.2014
comment
Как вы проверяете значения? Любой доступ к ключу создаст ключ; поэтому word_dd['nonesuch'] не назначает, а создает значение для вас.   -  person Martijn Pieters    schedule 13.04.2014
comment
Проверка значений, добавленных в вопрос   -  person Deutherius    schedule 13.04.2014
comment
Ваше понимание defaultdict, кажется, в порядке: код, который вы разместили, не может оказаться 0 in word_dd.values() истинным. Вы уверены, что между двумя фрагментами кода, которые вы опубликовали, нет кода, включающего word_dd? Кроме того, defaultdict будет работать заметно быстрее, чем dict.get/dict.setdefault, только когда значение по умолчанию дорого для вычисления, а постоянные целые числа определенно не являются. Причина, по которой стоит рассмотреть его здесь, заключается в том, что он делает ваш код проще, а не быстрее.   -  person lvc    schedule 13.04.2014

Ответы (3)


arrow_upward
6
arrow_downward

При доступе к ключу в defaultdict, если его там нет, он будет создан автоматически. Поскольку у нас есть int в качестве фабричной функции по умолчанию, она создает ключ и дает значение по умолчанию 0.

from collections import defaultdict
d = defaultdict(int)
print d["a"]
# 0
print d
# defaultdict(<type 'int'>, {'a': 0})

Итак, прежде чем получить доступ к ключу, вы должны убедиться, что он существует в экземпляре defaultdict, например

print "a" in d
# False
person thefourtheye    schedule 13.04.2014
comment
В этом весь смысл defaultdict оптимизации. В другом случае это устраняет накладные расходы get(entry, 0). - person Two-Bit Alchemist; 13.04.2014
comment
Отредактировал мой вопрос, пожалуйста, повторите - person Deutherius; 13.04.2014
comment
@Deutherius Если 1 еще не было в ddict, он будет создан, и будет использоваться значение по умолчанию 0. Я объяснил это поведение в ответе. Пожалуйста, проверьте. - person thefourtheye; 13.04.2014
comment
У меня сложилось впечатление, что word_ddict.iteritems() вернет итератор по существующим элементам в словаре - item в моем цикле тестирования представляет собой кортеж (ключ, значение), следовательно, 1 является индексом, а не запросом словаря. - person Deutherius; 13.04.2014
comment
@Deutherius О, извини, я неправильно понял это. В любом случае, вы проверяете не значение, а ключ, верно? Они могут иметь нули. Не могли бы вы показать образец фактических данных, чтобы воспроизвести эту проблему? - person thefourtheye; 13.04.2014
comment
@thefourtheye Я полагаю, что проверяю значение, проверка ключа будет выполняться с индексом 0. Кроме того, из-за размера лексикона, который обычно возвращает тысячи записей для каждой буквы n-грамм, было бы непрактично публиковать или вручную просматривать фактические обрабатываемые данные. - person Deutherius; 13.04.2014
comment
@Deutherius, я снова ошибся. Прости за это. Не могли бы вы воспроизвести проблему с образцом набора данных? - person thefourtheye; 13.04.2014

arrow_upward
6
arrow_downward

Любой доступ элемента к ключу материализует значение:

>>> from collections import defaultdict
>>> d = defaultdict(int)
>>> d['foo']
0

Вместо этого используйте сдерживание для проверки существования:

>>> 'bar' in d
False
>>> 'foo' in d
True

Поскольку вы считаете n-граммы, вы, вероятно, захотите также посмотреть на collections.Counter():

from collections import Counter

word_counter = Counter()
for letter_n_gram in word:
    word_counter.update(lexicon[n_gram])

где Counter.update() будет обновлять счетчики для всех записей, возвращаемых выражением lexicon[n_gram].

Как и defaultdict(int), объекты Counter() материализуют значения автоматически, по умолчанию это целое число 0.

person Martijn Pieters    schedule 13.04.2014
comment
Согласно моему последнему ответу на thefourtheye, я не думаю, что тестирую на наличие нулевого значения ошибочно. word_dd.iteritems() не должен, насколько мне известно, создавать какие-либо элементы. Я обязательно посмотрю collections.Counter, спасибо. - person Deutherius; 13.04.2014
comment
@Deutherius: нет, .iteritems() не будет. Код, который вы разместили в своем вопросе, тоже не будет. - person Martijn Pieters; 13.04.2014
comment
@Deutherius: единственный способ, которым вы можете иметь значения 0 в своем словаре, — это либо доступ к ключу (так что dictionary[key] в любом месте, где ключ еще не определен в словаре), либо прямое назначение 0 (через присваивание , расширенное присвоение или .update()). - person Martijn Pieters; 13.04.2014

arrow_upward
0
arrow_downward

Увы, я нашел ошибку в своем коде.

Поскольку в моем входном наборе есть много последовательных n-грамм слов с одним и тем же проверенным словом, я создаю словарь похожих слов только один раз для каждого уникального проверенного слова.

Затем этот словарь используется для других целей, при этом ключи проверяются несколько раз. Это, конечно, может создавать элементы с нулевым значением, если словарь collections.defaultdict и фабрика по умолчанию не установлена ​​на None.

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

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

Я хотел бы извиниться перед всеми за ошибочное и неполное построение моего вопроса - никто другой не мог найти ошибку.

person Deutherius    schedule 13.04.2014