Зачем нужен список если есть словарь?
Если список можно представить в виде словаря, где индекс ключ, а содержимое - значение, то почему бы не юзать словари вместо списка? В том числе если нужно индексироваться то просто ключи проставить как индексы в списке. При этом, словарь быстрее списка. Я погуглил на эту тему и все пишут что список упорядоченная коллекция данных, НО ВЕДЬ словарь ТОЖЕ МОЖНО отсортировать так, как тебе нужно через sorted и упорядочить по своему его, так вот вопрос: можно отказаться от списков и использовать только словари? Они быстрее => оптимальнее + обращаться к ним не менее удобно, чем как к спискам, дайте ответ если кто-то знает в чем тут хитрость
upd: неужели дело только в методах списка, которых нет у словаря? но ведь они все реализуемы и на словаре
Ответы (5 шт):
Почему вы решили, что словарь быстрее?
Для доступа к элементу словарь должен вычислить хэш его ключа и по хэшу, возможно, не за один скачок, получить его позицию.
В списке на основе массива (а под одеялом питоновский список содержит в себе массив) мы просто берём указатель по адресу начало+размер_указателя*индекс. Этот указатель указывает на нужный элемент. (В отличие от массивов во многих языках, списки питона могут содержать разные типы, поэтому прямая упаковка элементов в массив неудобна)
Вот в PHP, насколько я понимаю, массивы как раз на словарях с индексом в качестве ключа.
Этот вопрос относится не столько к python, а к структурам данных.
Есть разны словари, но возьмем, что у словаря время взятия элемента O(1), но это в общем случае + это константа тоже может быть не быстрой(как уже говорили есть вычисление хэш функций и еще коллизии), кроме того в худшем случае это время становится линейным O(n). Но стоит отметить, универсальность словаря, и он правда может заменить многие структуры, но нужно ли это? у каждой есть + и -.
В то время как list(особенность питона, что там можно хранить разные типы данных в одном списке, что делает его безусловно медленнее, чем обычные динамические массивы), но даже так он будет быстрее(зачастую) чем map.
Вообще стоит смотреть на поставленную задачу и отталкиваться от нее.
Во-первых, список быстрее словаря. Проверим при помощи timeit:
Проверяем скорость создания словаря и списка:
def test_list():
["foo"]
def test_dict():
{0: "foo"}
timeit.timeit(test_list, number=10000000), timeit.timeit(test_dict, number=10000000)
Результаты для списка составляют 0.4187 секунд, а для словаря - 0.5405 секунд. Если посмотреть на инструкции, выполняющиеся при создании, то можно увидеть, что для словаря выполняются несколько иные инструкции.
7 0 RESUME 0
8 2 LOAD_CONST 1 (0)
4 LOAD_CONST 2 ('foo')
6 BUILD_MAP 1
8 POP_TOP
10 RETURN_CONST 0 (None)
А для списка:
4 0 RESUME 0
5 2 LOAD_CONST 1 ('foo')
4 BUILD_LIST 1
6 POP_TOP
8 RETURN_CONST 0 (None)
Во-вторых, список и словарь отличаются методами. Например, для того чтобы проитерироваться по значениям словаря сначала произойдёт выполнение следующего набора инструкций:
8 LOAD_ATTR 1 (NULL|self + values)
28 CALL 0
Так или иначе, если задача состоит в том, чтобы перебрать словарь, то словарь будет преобразовывается в итерируемый объект, например, в dict_values.
Поэтому для задач связанных с постоянным перебором последовательностей лучше использовать списки.
Субъективная часть
Мнение. Зачем сомневаться в наличие некой структуры если вы ее не используете? Для определенных задач, существуют определенные структуры данных. Изначально заложен list как структура данных, которую вы можете использовать из коробки, не прибегая к написанию собственного кода для реализации функциональности, которая эта структура предоставляет. Просто наличие этого, расширяет ваши возможности.
Объективная часть
Давайте, начнем с документации к python струтур данных.
В начале можем посмотреть все методы для списков. Следом находим
5.1.1 Использование списка как стэка
5.1.2 Использование списка как очереди
5.1.4. Вложенный List Comprehension
Этого уже достаточно, чтобы перестать сомневаться.
Риторическая часть
А как реализовать матрицу размерностью n*n*n с помощью словаря? здесь исключаем модули типа pandas и numpy для замены list'a
В принципе, ответ уже дан, но всё же акцентирую некоторые вещи.
| Тип коллекции | Доступ по индексу/ключу | Добавление в конец | Что храним |
|---|---|---|---|
| Словарь | O(1)* | O(1)* | value1, value2, ... |
| Список | O(1) | O(1)** | hash1, key1, value1, hash2, key2, value2, ... |
Казалось бы, сложность одинаковая. Но есть тонкости.
| Дополнительные действия | Действия в худшем случае | |
|---|---|---|
| * | нужно вычислить hash ключа |
если возможна коллизия, то сравниваются сами объекты; если коллизий много, то нужно увеличить размер таблицы |
| ** | если массив заполнился, нужно увеличить размер массива |
Итак, получается, что в случае словаря имеем сразу несколько минусов:
- необходимость каждый раз брать хэш объекта
- необходимость сравнивать сами объекты, чтобы разрешить коллизии
- необходимость хранить в дополнение к самому объекту ещё ключ и его хэш
Таким образом, в сценарии, когда нам нужны только доступ по индексу и быстрое добавление в конец коллекции, списки однозначно выигрывают и по скорости и по объёму потребляемой памяти.
Поэтому к словарям имеет смысл переходить только тогда, когда нам недостаточно этих двух главных фич списка: доступа по индексу и добавления в конец коллекции. Тогда имеет смысл рассматривать какие-то другие коллекции, и не обязательно это будет словарь. Словарь хорош, когда у нас есть частый поиск по ключу. Тут ему нет равных. Ну и доступ в произвольное место коллекции (если словарь упорядоченный, как в поздних версиях питона).
P.S. В Питоне все объекты "первого класса", поэтому в коллекциях, конечно, хранятся не сами значения, а ссылки на объекты. Я немного упростил для понимания. Для сравнения коллекций это не столь существенно.