Действительно полезная статья и не только для начинающих и не только для разработчиков игр. Спасибо.
Почему пропустили двусвязный список?
Это вы у автора перевода спрашиваете? Вряд ли автор оригинала хабр читает.
Нда, пойду сделаю отметку о переводе ещё контрастнее.
Не важен контраст! Важен контекст, в начале мы оцениваем статью, наша заинтересованность не высока. По мере чтения статьи наш интерес либо угаснет и тогда мы уйдём с неё и вообще не зададимся вопросом авторства, либо возрастёт настолько что мы пойдём в комментарии или искать другие материалы автора. И что же мы видим дочитав статью?
image
тут нет ни намёка на то что это перевод! Имхо приоритетным размером должна быть превьюшка страницы откуда взят перевод, указан автор оригинала, и вторым приоритетом указывать переводчика. Тогда станет видно кто автор а кто переводчик.
Тут возможно разве что перенести плашку перевода вниз, больше через юзерстили не сделать.
Если судить по контексту, то подпись автора «переводчик-фрилансер» как бы намекает что это перевод, да и все стати данного автора обычно интересные переводы.
Правда я сам прежде чем написать комментарий выше, сначала все же проверил (а вдруг) и… еле нашел эту отметку.
Раньше внизу и было видно, что перевод. Но в каждой компании есть свой отдел двигания кнопок, которому тоже надо чем-то заниматься. Поэтому теперь — не видно.

Одна маленькая ремарка, родом из опыта. Часто бывает так, что позарез нужна отсортированная структура данных с быстрым поиском. При этом, структура создаётся один раз и не изменяется за время своего существования. Например, список лайтмапов, отсортированный по названию или идентификатору. Или просто список объектов игровой вселенной с идентификаторами.


Решение, которое большинство выносит из подобных статей это map<Id, Object>. На самом деле, при разовом заполнении и многократном использовании оптимально: vector<Object>, отсортированный по Id, и доступ по std::lower_bound. Особенно, если примерный размер структуры известен заранее. Двоичный поиск это логарифмическая оценка скорости, а хеш-таблица — линейная. Но, как правило, константа при линейной скорости хеш-таблицы делает её медленнее (чем двоичный поиск) при приложении к малым и средним структурам. То есть, если у вас нет достаточно большого (обычно порядка 2^14) объектов — сортированный вектор лучше unordered_map. Если его не нужно изменять.

>а хеш-таблица — линейная
Наверное хотели сказать константная? (В среднем О(1)).

Там всё несколько сложнее.


В академическом смысле, конечно, O(1), но мы тут о новичках говорим. А новичкам лучше говорить про O(n), и вот почему.


Это чисто практический подход. Не единожды в проектах встречал людей, которые мне советуют unordered_map под предлогом, что он таки O(1), а моё решение O(log(n)). Всегда предлагал тащить бенчмарк. Не проигрывал. Ситуаций, в которых это будет реальный O(1) очень мало.

>Там всё несколько сложнее.
Специально по этому я написал «В среднем» =)

ИМХО, новичкам в любом случае надо рассказывать всю историю, что в среднем О(1), что в худшем О(n), что константа «скрытая» в О(f(n)) может очень серьезно менять всю картину, и что на практике огромное значение может иметь то, как алгоритм размещает данные в памяти (кэш/prefetch/количество разыменований).

К слову сказать, не пытались пройтись профилировщиком, чтобы понять проигрывает ли unordered_map из-за вырождения в О(n), или же из-за каких-нить особенностей реализации? Все таки в случае не очень большого числа элементов ваш алгоритм должен быть довольно cache friendly (как мне кажется)
проигрывать мэп может из-за плохо выбранной хэш функции. при низкой вероятности коллизий доступ должен таки быть почти всегда O(1).
Некоторые языки программирования, например, C++, работают со страницами памяти. Обычно страница занимает 4 килобайта. При использовании операторы добавления и удаления, размещается целая страница памяти, даже если вам нужно использовать только один байт.


Как-то подозрительно.
Это получается в старых дос программах нельзя было использовать более 150 объектов?
В DOS писали на более низкоуровневых языках и использовали другие приёмы программирования.

В DOS писали на C++, и там всё это уже было.

Действительно довольно размытая формулировка, потому как страничная адресация работает независимо от языка, ведь это специфика ОС — подход к организации памяти.
Вообще это специфика аллокатора, отдельного или стандартной библиотеки. Поверх специфики ОС.
Операции в Binary Search Tree в _среднем_ O(log(n)), в худшем случ. O(n)

На практике, думаю, под BST подразумевают сбалансированные или в среднем сбалансированные деревья.

На моем опыте при собеседовании подобного подразумевания не было и было четкое разграничение.

В любом случае, использовать "голое" дерево, как минимум, странно.

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

[cap-mode]Сбалансированные деревья работают асимптотически не медленнее несбалансированных.[/cap-mode]

Спасибо за перевод, тема действительно интересная. Можете подсказать хорошую книгу на эту тему?

Вирт, Кнут…

Классика — Кормен (если не хотите сломать мозг об Кнута).
Еще хорошо глянуть на Курсере отличный курс по алгоритмам Седжвика и Уэйна и их же книжку.
Вы имеете в виду Алгоритмы: построение и анализ или Алгоритмы: Вводный курс?
Сначала вводный курс. Построение и анализ, это уже когда войдете во вкус)
Только полноправные пользователи могут оставлять комментарии.
Войдите, пожалуйста.