«Плохие программисты беспокоятся о коде. Хорошие программисты беспокоятся о структурах данных и их взаимосвязях», — Линус Торвальдс
Споры о планировщике
Наша команда вела спор о структурах данных. Нам нужен был планировщик задач операционной системы реального времени, способный:
Вставлять новые задачи с приоритетом (O(log n))
Запрашивать задачу с наибольшим приоритетом (O(1))
Удалять задачу с наибольшим приоритетом (O(log n))
Кто-то предложил: «Давайте используем отсортированный массив». Но вставка будет занимать O(n) — придётся сдвигать элементы.
Кто-то ещё сказал: «Возьмём связанный список». Однако поиск наибольшего выполняется за O(n) — необходимо сканировать весь список.
Третий вспомнил о двоичном дереве поиска. Но из Главы 9 мы уже знаем, что BST ужасно ведут себя с кэшем.
Споры продолжались, пока кто-то не упомянул двоичные кучи. Покончить с разногласиями позволили результаты бенчмарка