Как проверить, находится ли словарь в списке словарей как по ключу, так и по значению словаря, где словари могут быть вложены?

Я хочу проверить, существует ли весь словарь (как ключ, так и значение) в списке словарей. Каждый словарь может быть вложенным словарем словарей и списков.

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

Для диктов я не могу сделать my_dict in set(list_of_dicts), потому что это повышает unhashable type: 'dict'.

Выполнение my_dict in list_of_dicts, похоже, правильно возвращает False, если существует то же имя ключа, но значение другое (это то, что я хочу), но меня беспокоит время выполнения; python оптимизирует это внутри? Что еще я могу делать?

РЕДАКТИРОВАТЬ: предположим, что я буду выполнять МНОГИЕ поиски и использовать Python3.7


python-3.x python dictionary-comprehension
person gunit    schedule 28.01.2019    source источник
comment
scalar in set(list_of_scalars) кажется менее кратким, чем просто scalar in list_of_scalars. Если вы думаете, а не быстрее ли проверка членства для наборов, чем для списков? Это правда, но вы также конвертируете из списка в набор, поэтому вы теряете больше времени, чем получаете. Я не рекомендую my_dict in list_of_dicts, если вы хотите произвольно глубоко рекурсировать, чтобы найти диктовку. Например, {1:2} in [{3: {1:2}}] дает False.   -  person Kevin    schedule 28.01.2019
comment
Диктовки просто состоят из простых типов Python? т.е. (int/list/tuple/dict/str) и если да, то какую версию Python вы используете?   -  person Joran Beasley    schedule 28.01.2019
comment
dicts могут быть вложенными (dicts of dicts and lists). я использую питон3   -  person gunit    schedule 28.01.2019
comment
если вы знаете, откуда берутся диктовки, и вы можете упорядочить диктовки так же, как вы можете злоупотреблять механикой диктовок в 3.6+ и str(needle_dict) in str(list_of_dicts), поскольку в 3.6+ порядок диктов гарантирован   -  person Joran Beasley    schedule 28.01.2019

Ответы (2)


arrow_upward
3
arrow_downward

Чтобы проверить, существует ли скаляр в списке скаляров, я обычно превращаю список в набор и проверяю наличие в наборе, например, скаляр в наборе (list_of_scalars). (Пожалуйста, дайте мне знать, если это уже не лучший способ сделать это)

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

Для диктов я не могу сделать my_dict в наборе (list_of_dicts), потому что это вызывает нехешируемый тип: 'dict'. Но my_dict в list_of_dicts работает нормально, но меня беспокоит время выполнения;

Если вам нужно повторно выполнять этот поиск, то в зависимости от характера того, что вы храните в этих словарях, вы можете пересмотреть использование словарей и вместо этого выбрать объекты. Затем вы можете определить метод __hash__ для своего объекта и сохранить их в наборе, и поиск будет намного проще.

python оптимизирует это внутри? Что еще я могу делать?

Вы можете посмотреть временную сложность операций со структурами данных Python здесь: TimeComplexity. У Python нет возможности оптимизировать общий поиск в общем списке, и он будет использовать поведение линейного поиска ( O(n) ).

person vasia    schedule 28.01.2019

arrow_upward
0
arrow_downward

Чтобы оптимизировать множественный поиск, вы можете создать класс хешируемого словаря и выполнять поиск в наборе хешируемых словарей:

l = [{1:2,3:4}, {5:6,7:8}]
setofdicts = set(map(hashabledict, l))
hashabledict({5:6,7:8}) in setofdicts
#True
person DYZ    schedule 28.01.2019