Хабрахабр

Сглупил ли Ричард Хендрикс, или Линейный поиск против бинарного

На этой неделе там впервые за все шесть сезонов крупно показали код — разумеется, сразу хочется обсудить его здесь. Думаю, на Хабре есть любители сериала «Кремниевая долина» (Silicon Valley).

Там к уже отсортированным данным применён линейный поиск — так что задача будет выполнена, но выглядит это очень неэффективно. Желая унизить главного героя Ричарда Хендрикса, его бывший начальник показывает на совещании фрагмент его старого кода.

Однако среди зрителей сериала у его решения внезапно нашлись защитники, и теперь мне интересно, что об их позиции думает Хабр. Сам Ричард не спорит с тем, что код плохой.

Известный нам фрагмент кода Ричарда выглядит так:

int index = 0;
while (!element.equals(sortedList.get(index)) && sortedList.size() > ++index);
return index < sortedList.size() ? index : -1;

Как правило, на сортированных данных предпочитают бинарный поиск, который каждый раз делит множество пополам, отбрасывая неподошедшую половину целиком (потому что с ростом объёма данных количество итераций у линейного возрастает куда быстрее, чем у бинарного). Здесь линейный поиск обращается поочерёдно к каждому элементу какого-то уже отсортированного списка, пока не доберётся до нужного. Но в сабреддите /r/SiliconValleyHBO появился следующий комментарий:

При гигантских датасетах (думаю, порог на миллионах элементов) бинарный поиск быстрее. «Хочу немного позанудствовать и укажу, что "ошибка" Ричарда в использовании линейного поиска вместо бинарного по сортированным данным на самом деле в очень многих случаях оказывается более производительной. Линейный поиск требует больше итераций, но каждая из них безумно быстрее, чем итерация бинарного поиска. Но в целом, если ваш датасет не гигантский, линейный поиск будет лучше кэшироваться процессором, лучше подходит для branch predictor, а ещё ваш алгоритм может быть векторизован. Это контринтуитивно и противоречит всему, чему вас учили в вузе, но это так.

Вот этот доклад очень интересный и показывает некоторые поразительные результаты реальных замеров производительности».

Мол, создатель сериала Майк Джадж работал в Долине ещё в 80-х, когда все эти L1-кэши и branch prediction ещё особо не заявили о себе, так что поведение CPU было куда ближе к идеальной модели — вот в сериале такой пример и приведён. И другие участники треда поддержали комментатора: да, это в теории все итерации равноценны, а на реальном железе с реальными оптимизациями всё совсем иначе.

Конечно, мешает, что в сериале дан не весь контекст: например, мы понятия не имеем, по какому объёму данных он итерировался. Для меня, как и говорится в комментарии, это всё звучит контринтуитивно, но стало интересно разобраться, мог ли Ричард быть прав. Поставим вопрос так: даже если для большинства задач в Hooli бинарный поиск явно будет лучше, вероятен ли вариант, что для своих условий Ричард принял правильное решение, и другие персонажи напрасно над ним смеются, не зная контекста? С одной стороны, Ричард тогда работал на интернет-гиганта Hooli, где наверняка приходится иметь дело с миллионами записей, но с другой, это был его первый рабочий день, и его могли не бросать сразу на миллионы.

Как и обещали, он оказался интересным (ещё бы, это доклад Андрея Александреску), но посмотрев часть и прокликав остальное, я не увидел там сравнительных замеров бинарного и линейного поиска (возможно, плохо смотрел). Чтобы понять, открыл доклад, на который ссылались на Reddit.

Открыл текстовую версию его доклада, которую мы сделали для Хабра, и поискал по слову «линейный». Зато вспомнил, что на нашей конференции DotNext тот же Александреску тоже говорил о производительности. Оказалось, в числе прочего там как раз приведён пример любопытного сценария, в котором этот поиск окажется куда эффективнее бинарного (поиск совпадающих элементов двух множеств в том случае, когда эти множества идентичны) — но это очень конкретный случай, по такому не сделать общий вывод «линейный поиск недооценён».

Нашлись и случаи, где пытались побенчмаркать, но тоже не выглядящие для меня очень убедительными. Погуглил, что современные интернеты говорят по этому поводу — но в основном нашёл ответы на Stack Overflow, где просто пишут «используйте бинарный, итераций меньше».

Тут, конечно, напрашивается вариант «надо побенчмаркать лично, чтобы увидеть всё самому на реальном железе».

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

Поэтому, если вы разбираетесь в теме — расскажите, пожалуйста, в комментариях, как всё на самом деле. К счастью, на Хабре есть люди, понимающие куда больше меня (например, тот же Андрей DreamWalker Акиньшин, который про бенчмаркинг целую книгу написал). Насколько вероятно, что Ричард сделал всё правильно, даже если потом он сам не готов это отстаивать? До какого размера данных линейный подход всё ещё может быть хорошим выбором?

А если сведущих комментаторов не найдётся — придётся мне на следующем DotNext приковать Акиньшина к батарее и заставить бенчмаркать.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть