Сглупил ли Ричард Хендрикс, или Линейный поиск против бинарного
Думаю, на Хабре есть любители сериала «Кремниевая долина» (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 приковать Акиньшина к батарее и заставить бенчмаркать.
