Python. Проверить, входит ли элемент в коллекцию
Предположим, вы ведёте реестр монет. В нём записаны монетки всех времён, стран и достоинств. На вашем сайте любой может проверить, есть ли та или иная монета в реестре, и если нет — добавить её.
Как проверить, есть ли монета в реестре?
Список: очень, очень медленно
coins = ["1 aud", "5 ars", "1 byn", "10 ghs"] def has(coin): return coin in coins >>> has("1 byn") True >>> has("20 cny") False Конечно, так делать нехорошо. Операция element in list последовательно проверяет каждый элемент списка, то есть её сложность O(n) . Незаметно на маленьких списках, но если у вас в реестре 1 млн монет, а с сайта приходит по тысяче запросов в секунду — начнёт тормозить:
>>> import random >>> import timeit >>> list_ = [str(random.random()) for _ in range(1_000_000)] >>> elem = str(random.random()) >>> timeit.timeit(lambda: elem in list_, number=1000) 11.2 10 секунд на проверку тысячи элементов, пффф. Решение — использовать множества.
Множество: очень быстро, тяжеловесно
>>> set_ = set(str(random.random()) for _ in range(1_000_000)) >>> elem = str(random.random()) >>> timeit.timeit(lambda: elem in set_, number=1000) 0.00014 Операция element in set выполняется за O(1) . На множестве проверка отработала в несколько десятков тысяч раз быстрее, чем на списке.
А что с памятью? Проверим:
from pympler import asizeof def size_mb(obj): return round(asizeof.asizeof(obj) / 1024**2) >>> size_mb(list_) 77 >>> size_mb(set_) 101 Множество оказалось в 1.3 раза тяжелее списка. Ничего, для миллиона монеток хватит. Но что делать, если в коллекции один миллиард объектов, тоже всё в память запихивать?
Фильтр Блума: быстро, легко, неуверенно
Для множества на 1 млн элементов получилось 140 микросекунд на 1000 проверок, 101 Мб в памяти.
Что если элементов будет 1 млрд? Это уже около 100 Гб, не хотелось бы держать их в памяти. Устроил бы компромиссный вариант, который работает медленнее, но занимает меньше места.
И он существует! Это фильтр Блума — специальная вероятностная структура данных. Она отвечает на вопрос «есть ли элемент в коллекции?» одним из двух вариантов:
- точно нет;
- возможно есть.
Вот как это работает:
>>> from bloom_filter import BloomFilter >>> bloom = BloomFilter(max_elements=1_000_000, error_rate=0.001) >>> for el in set_: . bloom.add(el) >>> size_mb(bloom) 3 Фильтр Блума на 1 млн элементов с вероятностью ложно-положительного ответа 0.1% занимает всего 3 Мб (вместо 100 Мб «честного» множества). А что со скоростью?
>>> timeit.timeit(lambda: elem in bloom, number=1000) 0.015 15 миллисекунд — в 100 раз медленнее, чем проверка по множеству, но всё ещё достаточно быстро (например, в сотни раз быстрее проверки по списку).
Проверим на 1 млрд:
>>> bloom = BloomFilter(max_elements=1_000_000_000, error_rate=0.001) >>> size_mb(bloom) 3428 Три с лишним гигабайта, рост линейный. Чудес не бывает, но выигрыш по памяти в 30 раз при сохранении приемлемой скорости иногда может вам пригодиться.
Подписывайтесь на канал, чтобы не пропустить новые заметки ��
Как проверить наличие словаря во вложеном списке
Ребята изучаю словари. Как правильно написать проверку, чтобы убедиться, есть ли словарь во вложенном списке.
Ниже проверка, которая не работает, она выводит принт ‘полный’, когда есть словарь в списке и когда его нет.
1 2 3 4 5 6 7 8
#rooms = <'floor':[<"name": "Стартовая комната">]> rooms = {'floor':[]} if rooms['floor']==0: print('пустой') else: print('полный')
Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Как проверить наличие значения словаря словаря в словаре словарей?
есть массив parsdata, который содержит результаты парсинга. нужно проверить, спарсилось ли что-то.
Как проверить результат linq на наличие в списке элементов?
using System; using System.Collections; using System.Collections.Generic; using System.Linq;.
Проверить значение словаря на наличие слов
Добрый день! Подскажите, пожалуйста, как можно реализовать проверку значения словаря на наличие.
Проверить наличие эллемента в списке
Всем доброго времени суток. Возникла проблема. Не могу понять почему не работает программа.
Проверить наличие элемента в списке)
Здравствуйте). Я сформировал список,нашел в нем средний арифметический элемент,НО я не знаю как.
1303 / 843 / 409
Регистрация: 12.03.2018
Сообщений: 2,305
Сообщение было отмечено Джей Же как решение
Решение
1 2 3
for x in rooms['floor']: if type(x) == dict: print('yes')
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь
Проверить наличие текста в списке элементов
Есть XPath который указывает на блок элементов на сайте https://www.flagman.kiev.ua/ private.
Проверить наличие в списке определенной строки
Добрый день! Помогите разобраться, есть строка string z="1;2;3;4;5"; Далее я её.
Проверить наименование контрагента на наличие ее в списке групп компаний
Доброго дня. Думала, что знаю Эксель на 3 (по 10-бальной шкале). А-н, нет. Думаю, где-то на.
Линейные списки: проверить наличие в списке двух одинаковых элементов
здравствуйте ребята прошу помогиTе Дан список L, состоящий из записей: первое поле –.
Проверить наличие в списке заданного числа с помощью рекурсивной и нерекурсивной функций
Помогите с кодом к данной задаче Проверить наличие в списке заданного числа с помощью рекурсивной.
Множества и словари в Python
Множество ( set ) — встроенная структура данных языка Python, имеющая следующие свойства:
- множество — это коллекция Множество содержит элементы
- множество неупорядоченно Множество не записывает (не хранит) позиции или порядок добавления его элементов. Таким образом, множество не имеет свойств последовательности (например, массива): у элементов множества нет индексов, невозможно взять срез множества.
- элементы множества уникальны Множество не может содержать два одинаковых элемента.
- элементы множества — хешируемые объекты (hashable objects) В Python множество set реализовано с использованием хеш-таблицы. Это приводит к тому, что элементы множества должны быть неизменяемыми объектами. Например, элементом множества может быть строка, число, кортеж tuple , но не может быть список list , другое множество set .
Эти свойства множеств часто используются, чтобы проверять вхождение элементов, удаление дубликатов из последовательностей, а также для математических операций пересечения, объединения, разности.
Создание и изменение множества
Запустите в терминале Python в интерпретируемом режиме и проработайте примеры ниже.
Пустое множество создаётся с помощью функции set
>>> A = set() >>> type(A) >>> len(A) 0 >>> A set()
Обратите внимание, что размер множества множества можно получить с помощью функции len .
Добавим несколько элементов
>>> A.add(1) >>> A >>> A.add(2) >>> A >>> A.add(2) >>> A
Заметьте, что повторное добавление не имеет никакого эффекта на множество.
Также, из вывода видно, что литералом множества являются фигурные скобки <>, в которых через запятую указаны элементы. Так, ещё один способ создать непустое множество — воспользоваться литералом
>>> B = 1, 2> >>> B
При попытке добавления изменяемого объекта возникнет ошибка
>>> B.add([3,4,5]) Traceback (most recent call last): File "", line 1, in TypeError: unhashable type: 'list'
Здесь произошла попытка добавить массив в множество B.
У операции добавления set.add существует обратная — операция удаления set.remove
>>> B >>> B.remove(1) >>> B >>> B.remove(3) Traceback (most recent call last): File "", line 1, in KeyError: 3
При попытке удаления элемента, не входящего в множество, возникает ошибка KeyError .
Однако, существует метод set.discard , который удаляет элемент из множества, только в том случае, если этот элемент присутствовал в нём.
Математические операции
Множества Python поддерживают привычные математические операции
Проверки
Чтобы проверить вхождение элемента в множество используйте логический оператор in
>>> B = 1, 2> >>> B >>> 3 in B False
Асимптотика x in set — O(1).
Стоит отметить, что оператор in работает и с другими коллекциями. Например, можно проверять вхождение подстроки в строку ‘AA’ in ‘bbAAcc’ или вхождение элемента в массив 5 in [1, 2, 5, 6] . Асимптотики в данном случае нужно уточнять в документации.
>>> A = 1, 2, 3> >>> B = 1, 2, 3> >>> A == B True >>> B.add(4) >>> A >>> B >>> A == B False
Проверка на нестрогое подмножество set.issubset
>>> A >>> B >>> A.issubset(B) True >>> B.issubset(A) False >>> A.issubset(A) True
Проверка на нестрогое надмножество set.issuperset
>>> A >>> B >>> A.issuperset(B) False >>> B.issuperset(A) True >>> B.issuperset(B) True
Операции получения новых множеств
>>> A = 1, 2, 4> >>> B = 1, 2, 3> >>> A.union(B) # union — объединение множеств >>> A.intersection(B) # intersection — пересечение >>> A.difference(B) # difference — разность множеств >>> B.difference(A) >>> A.symmetric_difference(B) # symmetric_difference — симметрическая разность >>> B.symmetric_difference(A)
Сводная таблица по множествам (cheatsheet)
Кроме того, у операций, порождающих новые множества, существует inplace варианты. Для методов это те же названия, только с префиксом _update, а для соответствующих операторов добавляется знак равенства =. Ниже показан вариант для операции разности множеств
>>> A = 1, 2, 3, 4> >>> B = 2, 4> >>> A.difference_update(B) >>> A >>> A = 1, 2, 3, 4> >>> B = 2, 4> >>> A -= B >>> A
Неизменяемые множества
В Python существует неизменяемая версия множества — frozenset . Этот тип объектов поддерживает все операции обычного множества set , за исключением тех, которые его меняют.
Неизменяемые множества являются хешируемыми объектами, поэтому они могут быть элементами множества set . Так можно реализовать, например, множество множеств, где множество set состоит из множеств типа frozenset .
Для создания frozenset используется функция frozenset(iterable) , в качестве аргумента принимающая итерирумый объект.
>>> FS = frozenset(1, 2, 3>) >>> FS frozenset() >>> A = 1, 2, 4> >>> FS & A frozenset() >>> A & FS
В этом примере показано создание frozenset из обычного множества . Обратите внимание на тип возвращаемого объекта для операции пересечения & . Возвращаемый объект имеет тип, соответствующий типу первого аргумента. Такое же поведение будет и с другими операциями над множествами.
Словари Python
Словарь (dictionary) в Python — это ассоциативный массив, реализовать который вы пробовали на прошлом занятии. Ассоциативный массив это структура данных, содержащая пары вида ключ:значение. Ключи в ассоциативном массиве уникальны.
В Python есть встроенный ассоциативный массив — dict . Его реализация основана на хеш-таблицах. Поэтому
- ключом может быть только хешируемый объект
- значением может быть любой объект
Создание и изменение словаря
Пустой словарь можно создать двумя способами:
>>> d1 = dict() >>> d2 = <> >>> d1 <> >>> d2 <> >>> type(d1) >>> type(d2)
Добавить элемент в словарь можно с помощью квадратных скобок:
>>> domains = <> >>> domains[‘ru’] = ‘Russia’ >>> domains[‘com’] = ‘commercial’ >>> domains[‘org’] = ‘organizations’ >>> domains
Из этого примера видно, что литералом словаря являются фигурные скобки, в которых через запятую перечислены пары в формате ключ:значение . Например, словарь domains можно было создать так domains = .
Доступ к элементу осуществляется по ключу:
>>> domains['com'] 'commercial' >>> domains['de'] Traceback (most recent call last): File "", line 1, in KeyError: 'de'
Удалить элемент можно с помощью оператора del . Если ключа в словаре нет, произойдет ошибка KeyError
>>> domains >>> del domains[‘de’] Traceback (most recent call last): File «», line 1, in KeyError: ‘de’ >>> del domains[‘ru’] >>> domains
Кроме того, для добавления, получения и удаления элементов есть методы dict.setdefault , dict.get , dict.pop , которые задействует дополнительный аргумент на случай, если ключа в словаре нет
>>> d1 = <> >>> d1.setdefault(‘a’, 10) 10 >>> d1.setdefault(‘b’, 20) 20 >>> d1 >>> d1.setdefault(‘c’) >>> d1 >>> d1.setdefault(‘a’, 123) 10 >>> d1 >>> d1.get(‘a’) 10 >>> d1.get(‘d’) # вернул None >>> d1.get(‘d’, ‘NoKey’) ‘NoKey’ >>> d1.pop(‘d’) Traceback (most recent call last): File «», line 1, in KeyError: ‘d’ >>> d1.pop(‘d’, 255) 255 >>> d1 >>> d1.pop(‘a’, 255) 10 >>> d1
Примечание о числовых ключах
Ключом может являться и число: int или float . Однако при работе со словарями в Python помните, что два ключа разные, если для них верно k1 != k2 # True .
>>> d = 0: 10> >>> d >>> d[0] = 22 >>> d >>> d[0.0] = 33 >>> d >>> 0.0 != 0 False
Поэтому при возможности избегайте в качестве ключей float -объектов.
Использование DictView: циклы и множественные операции
Если попробовать пройтись в цикле по словарю, то это будет проход по ключам
>>> d = 'a': 10, 'c': 30, 'b': 20> >>> for k in d: . print(k) . a c b
Зачастую необходимо пройтись в цикле по ключам, значениям или парам ключ:значение, содержащиеся в словаре. Для этого существуют методы dict.keys() , dict.values() , dict.items() . Они возвращают специальные DictView объекты, которые можно использовать в циклах:
>>> d = 'a': 10, 'c': 30, 'b': 20> >>> for k in d.keys(): . print(k) . a c b >>> for v in d.values(): . print(v) . 10 30 20 >>> for k, v in d.items(): . print(k, v) . a 10 c 30 b 20
Объекты DictView , содержащие только ключи, ведут себя подобно множествам. Кроме того, если DictView объекты для значений или пар содержат неизменяемые объекты, тогда они тоже ведут себя подобно множествам. Это означает, что привычные для множеств операции пересечения, вхождения и другие также работают с DictView .
>>> d >>> dkeys = d.keys() >>> ‘abc’ in dkeys False >>> ‘c’ in dkeys True >>> ‘a’, ‘b’, ‘c’> == dkeys True >>> dkeys & ‘b’, ‘c’, ‘d’>
Словарь с упорядоченными ключами OrderedDict
Это может понадобится для отправки задач на ejudge.
Если внимательно просмотреть примеры на циклы выше, то видно, что порядок итерирования в циклах совпадает с порядком добавления элементов в словарь.
Однако, такое поведение у стандартных словарей dict гарантируется, начиная с версии 3.7 (лабораторные примеры были сделаны из-под версии 3.7.4). Узнать свою версию Python можно, например, из терминала python3 --version или зайдя в интерпретируемый режим (версия будет написана сверху).
Если для вашей программы важно упорядочивание элементов, но вы не знаете, какой версии интерпретатор будет исполнять ваш скрипт, то вам нужно воспользоваться упорядоченной версией словарей OrderedDict .
Она находится в стандартной библиотеке collections .
Упорядоченный словарь поддерживает все операции, что и обычный словарь.
>>> import collections >>> od = collections.OrderedDict() >>> od OrderedDict() >>> od['a'] = 10 >>> od['c'] = 30 >>> od['b'] = 20 >>> od OrderedDict([('a', 10), ('c', 30), ('b', 20)])
Сайт построен с использованием Pelican. За основу оформления взята тема от Smashing Magazine. Исходные тексты программ, приведённые на этом сайте, распространяются под лицензией GPLv3, все остальные материалы сайта распространяются под лицензией CC-BY.
Изменение данных в словаре — Python: Cловари и множества
Словарь в Python — изменяемый или мутабельный. Но для добавления новой пары «ключ-значение» не нужны отдельные методы, вроде спискового метода .append — достаточно обычного присваивания:
d = <> # пустой словарь d["a"] = 100 print(d) # => d["b"] = 200 d["a"] = 0 print(d) # => Здесь вы можете увидеть, что присваивание значения новому ключу выглядит точно так же, как и присваивание существующему. Именно эту тему мы изучим подробнее в этом уроке
Метод pop
Удаление элементов из словаря можно сделать с помощью метода pop — в этом словарь уже больше похож на список. Только вместо индекса используется ключ:
d = 'a': 1, 'b': 2> d.pop('a') # 1 d # d.pop('BANG') # KeyError: 'BANG' Этот пример показывает, что будет, если попытаться извлечь значение по несуществующему ключу — мы получим исключение.
Однако метод pop можно вызывать с указанием значения по умолчанию. В этом случае при отсутствии ключа в словаре будет возвращено это самое значение, а исключение возбуждено не будет:
d = 'a': 1, 'b': 2> d.pop('BANG', None) d.pop('BANG', 42) # 42 Аналогом спискового pop без аргументов для словаря служит метод popitem . Этот метод извлекает ключ и значение в виде кортежа, а если словарь уже пуст, то возбуждает исключение:
d = 'a': 1> d.popitem() # ('a', 1) d.popitem() # KeyError: 'popitem(): dictionary is empty' В пайтоне, начиная с версии 3.7, гарантирован порядок LIFO — Last In First Out. Это значит, что пары будут извлекаться в порядке обратном добавлению, от самых ранних до самых поздних по времени добавления. При этом мы можем быть уверены в том, что:
- Все пары будут извлечены
- Каждая пара будет извлечена строго один раз
Дополнение одного словаря другим
У списка есть метод extend , который расширяет один список другим. У словаря есть похожий по смыслу метод update . Но при вызове update ассоциированный объект словаря не просто получает пары «ключ-значение» из нового словаря. Происходит именно обновление данных — поэтому метод и называется update . Работает это так:
- Новые ключи дописываются в словарь
- Если какие-то ключи уже существовали до этого, то связанные с ними значения, будут заменены новыми
Так это выглядит в коде:
cart = 'apples': 2, 'oranges': 1> addon = 'oranges': 5, 'lemons': 3> cart.update(addon) cart # В коде выше мы добавили лимоны и обновили количество апельсинов.
Копирование словаря
В случае списков мы можем сложить два списка и получить один из двух вариантов:
- Новый список из двух списков
- Копию одного списка, которую можно дополнить данными из второго
Но словари нельзя складывать, да и срезы словари тоже не поддерживают. Зато у словаря есть метод copy . Он работает как копирование списка с помощью среза [:] — при вызове он возвращает поверхностную копию из словаря. Так же ее называют «неглубокой копией» или shallow copy.
Поверхностная копия воспроизводит только структуру словаря: не копирует значения, а только создает на них новые ссылки. Тем не менее поверхностная копия — это новый словарь, который может изменять свой состав, не влияя на оригинал:
d = 'a': 1, 'b': [42]> c = d.copy() c.update('a': 10, '1k': 1024>) c # c['b'].append(None) c # d # Словарь c получил собственную структуру, при этом его обновление не затронуло оригинальный словарь d . Однако изменение объекта списка по ссылке затронуло и оригинал, потому что при копировании словаря ссылка на список тоже скопировалась.
Очистка словаря
Списки можно очистить с помощью присваивания срезу l[:] = [] . В случае словаря вместо присваивания срезу используется метод clear .
Метод clear() удаляет все элементы из текущего словаря:
d = 'a': 1> Открыть доступ
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно
- 130 курсов, 2000+ часов теории
- 1000 практических заданий в браузере
- 360 000 студентов
Наши выпускники работают в компаниях: