Структуры данных

Что это такое

Структура данных — это способ разложить значения в памяти так, чтобы нужные операции обходились дёшево. Один и тот же набор записей можно хранить по-разному, и тогда быстрым окажется либо поиск, либо вставка, либо упорядоченный обход, либо ответ на вопрос «дай самое большое», — однако всё сразу дешёвым быть не может. Вопрос о выборе сводится поэтому к тому, какие операции программа выполняет чаще всего.

Почему это важно

Большая часть работы над производительностью, если только она не про сетевые вызовы, упирается в структуру данных, выбранную в начале и больше не пересмотренную. Список, который перебирают внутри цикла, даёт квадратичную сложность, хотя выглядит совершенно безобидно. Библиотеки подсовывают значения по умолчанию — массив, словарь, список, — и в большинстве случаев они верны; именно поэтому неудачный случай так трудно заметить. Форма структуры вдобавок делает код читаемым: когда кто-то берёт кучу, уже одно слово говорит, что делает алгоритм.

Что в этом треке

1. Массивы, списки и хеш-таблицы (01-cs-fundamentals/02-data-structures/01-arrays-lists-and-hash-maps) — структуры непрерывные и ключевые. На них держится большая часть повседневной работы.
2. Деревья, кучи и графы (01-cs-fundamentals/02-data-structures/02-trees-heaps-and-graphs) — иерархические и сетевые формы, а вместе с ними и обход, к которому располагает каждая из них.

Предварительные требования

Нет.

Что читать дальше

• Алгоритмы и Big-O (01-cs-fundamentals/14-algorithms-big-o) — запись о том, что здесь означают «дёшево» и «дорого».
• Информатика (01-cs-fundamentals/01-computer-science) — место этой записи в более широкой основе.
• Конкурентность и асинхронное программирование (01-cs-fundamentals/05-concurrency-async-programming) — вторая половина истории о стоимости, когда работа идёт одновременно.