Списки, кортежи, словари и множества

Все темы Python Developer

Подтемы:

• Списки, кортежи, словари и множества
• Хэш-функции

В чем отличие между кортежами и списками?

Основные различия между кортежами и списками:

Кортежи (tuples):

• Кортежи - неизменяемые упорядоченные коллекции объектов.

• Элементы кортежа не могут быть изменены после создания.

• Создаются с использованием круглых скобок: ().

• Используются, когда необходима коллекция, которая не должна изменяться.

Списки (lists):

• Списки - изменяемые упорядоченные коллекции объектов.

• Элементы списка могут быть изменены, добавлены или удалены после создания.

• Создаются с использованием квадратных скобок: [].

• Используются, когда необходима коллекция, которая может быть изменена или модифицирована.

Какие функции предоставляются для работы со списками в Python?

Выделяют основные функции для работы со списками:

1. append(): Добавляет элемент в конец списка.

2. extend(): Расширяет список, добавляя элементы из другого списка.

3. insert(): Вставляет элемент на указанную позицию.

4. remove(): Удаляет первое вхождение элемента с указанным значением.

5. pop(): Удаляет элемент с указанным индексом и возвращает его значение.

6. clear(): Удаляет все элементы из списка.

7. index(): Возвращает индекс первого вхождения элемента с указанным значением.

8. count(): Возвращает количество вхождений элемента с указанным значением.

9. sort(): Сортирует элементы списка.

10. reverse(): Изменяет порядок элементов на обратный.

11. copy(): Создает копию списка.

Какая операция выполняется быстрее: проверка наличия элемента в списке или в множестве?

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

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

Ключ словаря должен быть хешируемым: его хеш не меняется за время жизни, а равные ключи имеют равные хеши. Числа и строки подходят; кортеж подходит, только если хешируемы все его элементы. Неизменяемость сама по себе не гарантирует хешируемость. Экземпляры пользовательских классов по умолчанию хешируемы по идентичности.

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

При инициализации списков и кортежей в памяти компьютера происходит выделение памяти для хранения элементов данных. Вот основные различия между списками и кортежами в плане памяти:

1. Списки (list):

   • Списки являются изменяемыми структурами данных, поэтому они требуют дополнительной памяти для хранения информации о размере списка, его емкости (capacity), а также ссылок на элементы.

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

   • Это делает списки менее эффективными с точки зрения использования памяти, особенно для больших списков.

2. Кортежи (tuple):

   • Кортежи являются неизменяемыми структурами данных, поэтому они требуют меньше памяти, чем списки.

   • Кортеж хранит свой размер и ссылки на элементы, но ему не нужен резерв ёмкости для последующего добавления элементов.

   • Это делает кортежи более компактными и эффективными с точки зрения использования памяти, особенно если требуется хранить данные, которые не будут изменяться.

Где быстрее искать значение по ключу - в словаре или dicts в Python?

Словарь в Python и dict обозначают один встроенный тип. Отдельного встроенного типа dicts нет. Поиск по ключу в dict в среднем занимает O(1), а в худшем случае O(n). Если в вопросе подразумевается сторонняя обёртка, сначала нужно уточнить её название и реализацию.

Как работает defaultdict и чем он отличается от dict.get()?

defaultdict(factory) при обращении mapping[key] к отсутствующему ключу вызывает фабрику без аргументов, записывает результат и возвращает его. Это удобно для счетчиков и группировки. dict.get(key, default) возвращает запасное значение, но словарь не меняет. setdefault записывает default, однако выражение default вычисляется заранее. Важно помнить, что простое чтение defaultdict через квадратные скобки имеет побочный эффект. Выбор структуры подтверждают нужными операциями и ограничениями, а не только асимптотикой одного удачного действия.

Как работает dict comprehension?

Dict comprehension имеет форму {key_expr: value_expr for item in source if condition} и строит пары за один проход. При повторном ключе остается значение из последней обработанной пары, хотя позиция ключа в порядке словаря не переносится заново. Выражение хорошо для короткого отображения или фильтра. Несколько вложенных циклов и сложные условия лучше вынести в обычный цикл с говорящими промежуточными именами. Выбор структуры подтверждают нужными операциями и ограничениями, а не только асимптотикой одного удачного действия.

Когда нужен frozenset вместо set?

frozenset хранит уникальные элементы как set, но после создания не меняется и потому может быть хешируемым. Его можно использовать ключом словаря или элементом другого множества, если все элементы сами хешируемы. Порядок обхода не является контрактом. Он подходит для неизменяемого набора признаков или составного ключа; если набор нужно пополнять и удалять, нужен обычный set. Выбор структуры подтверждают нужными операциями и ограничениями, а не только асимптотикой одного удачного действия.

Чем dict.items() отличается от списка пар?

dict.items() возвращает динамический view пар ключ-значение, связанный с исходным словарем, а не отдельный список. Изменение значения отражается во view; изменение размера словаря во время обхода может вызвать ошибку. View можно итерировать и выполнять некоторые операции множеств, если элементы хешируемы. Для стабильного снимка в конкретный момент явно используют list(d.items()). Выбор структуры подтверждают нужными операциями и ограничениями, а не только асимптотикой одного удачного действия.

Почему опасно менять список во время обхода?

Удаление или вставка в list сдвигает индексы, которыми пользуется итератор, поэтому элементы могут быть пропущены или обработаны неожиданно. Для фильтрации обычно строят новый список comprehension. Если нужно менять исходный список, присваивают результат срезу. Точечное удаление можно выполнять по копии или в обратном порядке индексов, но выбранное поведение должно быть очевидно из кода. Выбор структуры подтверждают нужными операциями и ограничениями, а не только асимптотикой одного удачного действия.

Когда deque лучше list для очереди?

collections.deque дает амортизированное O(1) добавление и удаление с обоих концов, поэтому FIFO-очередь строят через append и popleft. У list удаление с начала требует сдвига элементов. maxlen удобно хранит скользящее окно, автоматически выбрасывая старое. Произвольный доступ к середине deque медленный; для индексации и плотной последовательной обработки лучше list. Выбор структуры подтверждают нужными операциями и ограничениями, а не только асимптотикой одного удачного действия.

Почему tuple с list может измениться после неудачного +=?

В выражении tuple_obj[0] += value Python сначала получает вложенный объект и выполняет его in-place операцию. Для list __iadd__ успевает изменить сам список. Затем интерпретатор пытается записать результат обратно в элемент tuple и получает TypeError, потому что кортеж неизменяем. Ошибка не откатывает уже выполненную мутацию. Поэтому неизменяемость tuple касается его ссылок, а не вложенных объектов. Выбор структуры подтверждают нужными операциями и ограничениями, а не только асимптотикой одного удачного действия.

Когда array.array лучше list?

array.array компактно хранит однородные примитивные числа без отдельного Python-объекта на каждый элемент, тогда как list хранит ссылки. Он полезен для умеренных бинарных буферов и простых операций, имеет typecode и умеет читать или писать bytes. Для векторных вычислений, многомерности и богатых dtype обычно лучше NumPy; для смешанных объектов и частых обычных операций удобнее list. Выбор структуры подтверждают нужными операциями и ограничениями, а не только асимптотикой одного удачного действия.

Как устроена хэш-таблица и почему поиск и вставка обычно занимают O(1), в том числе при расширении?

Хэш-таблица хранит пары ключ–значение. Хэш-функция вычисляет числовой хэш ключа, а таблица использует его для выбора позиции. При коллизии ключи дополнительно сравниваются на равенство.

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

При расширении выделяется большая таблица и заново определяются позиции элементов. Саму хэш-функцию менять не обязательно: меняется отображение хэша в позицию. Например, CPython 3.14 при перестроении dict использует сохранённые хэши, а не вызывает заново пользовательский __hash__ для всех ключей.

При хорошем распределении и ограниченной загрузке поиск занимает ожидаемое O(1). Вставка имеет ожидаемую амортизированную сложность O(1): редкие расширения стоимостью порядка O(n) распределяются по серии вставок, если ёмкость растёт геометрически. Отдельная вставка с расширением не обязана быть O(1).

В худшем случае из-за коллизий поиск и вставка могут занимать O(n). Эти оценки предполагают O(1) для вычисления хэша и сравнения ключей; для длинных или пользовательских ключей их стоимость учитывается отдельно.

Что такое хеширование и где оно применяется?

Хеширование преобразует данные в хэш фиксированного размера для выбранного алгоритма. Одинаковые данные дают одинаковый хэш при одних и тех же настройках, но одинаковый хэш не доказывает равенство данных: возможны коллизии.

В хэш-таблицах оно ускоряет поиск по ключу. Криптографические хэш-функции используются для проверки целостности и в схемах электронной подписи; их требования к стойкости отличаются от требований обычной хэш-таблицы. Хеширование не является шифрованием.

Для хранения паролей нужен специализированный медленный алгоритм с уникальной солью, например Argon2id. Обычный hash() или один быстрый SHA-256 для этого не подходят.