Python: список против словаря против множества

Question

"Какую структуру данных - Set, List или Dictionary - в Python вы будете использовать для хранения 10 миллионов целых чисел? Операции запроса состоят из определения числа раз, которое число появляется в данном наборе. Какое время будет наихудшим исложность пространства во всех случаях? "

Это типовой вопрос интервью.Какой ответ будет наиболее подходящим?

Answer 1

Добавление к ответу @Джон Старк Начиная с Python wiki , сложность времени для запросов в наборе равна O (n). Это потому, что он использует хеш для получения значения, но с (МНОГО) неудачей, вы можете столкнуться с хешем для каждого ключа. Однако в подавляющем большинстве случаев у вас не будет столкновения. Кроме того, поскольку здесь ключи являются целыми числами, вы уменьшаете коллизию хешей, если диапазон целых чисел ограничен. В python 2 с типом int не может быть коллизий.

Answer 2

Добавьте каждое число как число: 1 в dict, если число не в dict, иначе добавьте 1 к Val этого ключа. Затем найдите конкретное число в качестве Key, Val будет количество раз, которое появляется.

Answer 3

Ключом к этому вопросу является строка, которая гласит:

"определение количества раз, которое число появляется в данном наборе"

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

Разбивка опций:

Set: Набор автоматически восстанавливает значения, добавленные к уже существующему набору. Поэтому было бы невозможно запросить частоту появления числа в сохраненном наборе данных, используя набор, потому что ответ для всех сохраненных чисел будет равен 1.

• Сложность времени для запроса: O (1)
• Пространство для хранения: O (n)

Список: Список может быть повторен, чтобы определить частоту данного числа в списке. Однако это будет операция O (n), и для 10 миллионов целых чисел не будет эффективным.

• Сложность времени для запроса: O (n)
• Пространство для хранения: O (n)

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

• Сложность времени для запроса: O (1)
• Сложность времени для хранения: O (n)
• Пространство для хранения: O (2n) = O (n)