Иголка в стоге сена в информатике

Медленный путь: смотреть всё подряд

Если ты ничего не знаешь о том, где иголка, единственный вариант — проверять каждый кусок сена, пока не найдёшь её. В информатике это называется линейным поиском. В среднем ты проверяешь половину всего, прежде чем добьёшься успеха, а в худшем случае всё. Это всегда работает, но время растёт пропорционально размеру кучи.

Сортировка меняет всё

Теперь представь, что сено разложено по порядку, как слова в словаре. Более хитрый метод, двоичный поиск, открывает в середине, решает, в какой половине ответ, и отбрасывает другую. Повторяй, и миллион элементов просматривается примерно за 20 шагов. Загвоздка в том, что куча должна быть упорядочена заранее, а стог сена никогда таким не бывает.

Индексы: схитрить подготовкой

Базы данных и поисковые системы обходят проблему, выполняя тяжёлую работу заранее. Они строят индекс, как указатель в конце книги, который говорит, на какой странице слово. Поиск становится быстрым, потому что время потрачено раньше. Для настоящего стога сена индекса нет, и именно поэтому существует это выражение.

Следование за сигналом

Металлоискатель — другое дело. Он не говорит, где иголка, но говорит, приближаешься ли ты. Представь число, которое растёт по мере приближения. Тогда можно применить простое правило: сделай шаг, посмотри, усилился ли сигнал, и продолжай в направлении, которое его улучшает. Программисты называют вариант этого подъёмом на холм (hill climbing), и он стоит за многими практическими оптимизациями.

В игре сигнал вычисляется по расстоянию до ближайшего куска металла относительно дальности металлоискателя. Писки учащаются, когда это число приближается к 1, поэтому подъём на холм делает за тебя твоё ухо. Подробнее в Как работает металлоискатель.

Когда сигналы подводят

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

Стог как данные

Стог в игре сам является структурой данных: сеткой 88 на 40 на 88 ячеек, в каждой из которых хранится число, обозначающее плотность сена. Копать — значит менять числа, а чанки по 16 ячеек удерживают объём работы небольшим. Как это устроено, рассказано в Как устроен стог сена.