Что лучше использовать словарь или массив или связный список?

Question

[Евгений Усачев]

Честно, не знаю какие теги указать для запроса, заранее извиняюсь. Я понимаю, что важнее всего в коде читаемость, но я решаю алгоритмические задачи на Leetcode и было бы неплохо, если бы они выполнялись быстро. Я часто смотрю чужие решения, но так и не понял, когда надо использовать каждую из структур данных.

Answer 1

[otdameskapizm]

Невозможно на это дать однозначный ответ, так как все зависит от конкретной задачи. Например, условные словари позволяют осуществлять доступ к элементам гораздо быстрее, чем массив, поскольку не нужно ползти по всему массиву, чтобы добраться до элемента, но в то же время, словари "тяжеловеснее". Так что тут уже нужно смотреть на конкретную задачу - условие, входные данные, выходные и все из этого вытекающее

Answer 2

[mayton2019]

Я понимаю, что важнее всего в коде читаемость, но я решаю алгоритмические задачи на Leetcode

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

Answer 3

[res2001]

Надо знать достоинства и недостатки каждого контейнера и решить какие требования к контейнеру предъявляет конкретная задача (какие операции контейнера будут критичными для конкретной задачи).

1. Массив (не отсортированный)
Плюсы: доступ к элементу по индексу - O(1)
Минусы: произвольный поиск - O(n); вставка, удаление - O(n) требуется перевыделение памяти и копирование всего контейнера
2. Список
Плюсы: вставка - если известно место вставки O(1); удаление - если известен удаляемый элемент O(1)
Минусы: доступ по индексу, произвольный поиск - O(n);
3. Словарь
Может быть внутри реализован как дерево или как хеш-таблица. Как реализованы в питоне стандартный объект не знаю.
3.1. Дерево. Обычно используется какой-то вариант сбалансированных двоичных деревьев поиска (красно-черное и т.п.)
Плюсы: произвольный поиск, вставка, удаление - O(log(n))
Минусы: для обеспечения сбалансированности дерева используются дополнительные "внутренние" операции с деревом, что увеличивает время каждой отдельно взятой операции вставки и удаления. Эти операции обычно достаточно "легкие" и константные по времени.
3.2. Хеш-таблица
Плюсы: произвольный поиск, вставка, удаление - O(1);
Минусы: вставка и удаление могут в некоторых случаях приводить к перевыделению памяти и полному копированию и/или к пересчету хешей в зависимости от реализации.

Как видите, нет универсального 100% подходящего контейнера на все случаи жизни. У всех есть свои плюсы и минусы.