Лекция 4. Метод половинного деления: где искать

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

1. Бить в середину

Вернёмся к локализации. Мы представляли систему как цепочку узлов и проверяли на границах, где хорошее становится плохим. Самый простой способ — идти по очереди: проверить после первого узла, после второго, третьего… Рано или поздно наткнёшься на границу. Но это медленно: если поломка в конце длинной цепочки, придётся сделать почти столько проверок, сколько узлов. Метод половинного деления предлагает радикально лучший ход: не начинать с краю, а сразу проверить в середине.

Логика такая. Проверили середину. Если там ещё хорошо — значит, поломка где-то в правой половине, и всю левую можно разом выбросить. Если уже плохо — поломка в левой половине, выбрасываем правую. Одной проверкой мы отсекли половину системы. Теперь берём оставшуюся половину и снова бьём в её середину — отсекаем половину от неё. И так далее: каждая проверка уполовинивает зону поиска, пока не останется один узел. Вот и весь метод. Его ещё называют бинарным поиском, «разделяй и властвуй», а образно — «поиском вола за забором». Гениальность его в контринтуитивности: инстинкт велит проверять по порядку, с начала, а метод говорит — нет, всегда меть в середину неизвестности. Разберёмся, почему середина даёт столько.

2. Почему это так быстро

Секрет скорости в том, что каждая проверка в середине несёт максимум информации — она делит неизвестность ровно пополам. Проверка с краю в худшем случае вычёркивает всего один узел; проверка в середине — половину всех. Отсюда почти невероятная эффективность, которую видно на схеме с числами.

Смотрите, что получается. Чтобы перебрать поломку подряд в системе из тысячи узлов, нужно в среднем пятьсот проверок. А делением пополам — всего десять: тысяча, пятьсот, двести пятьдесят, сто двадцать пять и так далее до одного, ровно десять шагов. В миллионе узлов подряд — полмиллиона проверок, а пополам — двадцать. Разница не в разы, а в пропасть. И вот что важнее всего: с ростом системы эта эффективность почти не падает. При поиске подряд каждый лишний узел добавляет работу; при делении пополам, чтобы прибавилась хотя бы одна проверка, систему надо удвоить. Удвоили — плюс один шаг. Ещё удвоили — ещё плюс один. Поэтому метод почти не замечает размера: он одинаково быстр и на маленькой схеме, и на гигантской. Это свойство — расти не пропорционально размеру, а лишь по числу удвоений — в математике зовут логарифмическим, и оно лежит в основе множества самых быстрых способов что-либо искать. Вам не нужна математика, чтобы этим пользоваться: достаточно запомнить вывод — всегда бей в середину, и любая, даже огромная, система сдастся за считаные проверки.

3. Волчий забор

У метода есть чудесный наглядный образ, придуманный инженерами, — «алгоритм волчьего забора». Представьте длинный луг, вдоль которого идёт провод, и где-то на лугу спрятался волк (это наша поломка). Как найти волка быстрее всего? Не идти вдоль луга шаг за шагом, вглядываясь, а построить забор ровно посередине луга и прислушаться: с какой стороны воет волк? С правой — значит, он в правой половине, и всю левую можно забыть. Строим следующий забор посередине правой половины — и снова слушаем. Каждый забор вдвое сокращает участок, где может быть волк, и за несколько заборов мы прижимаем его к крохотному пятачку.

Этот образ хорош тем, что переносится на что угодно. «Забор» — это любая проверка, делящая систему надвое: замер тока посередине провода, вопрос к середине списка подозреваемых, контрольная точка в середине процесса. «Волк» — причина, которую мы ищем. А «вой» — тот самый признак, по которому мы отличаем исправную половину от сбойной. Вся хитрость — научиться в своей задаче ставить такие «заборы»: находить точку, которая делит проблему примерно пополам и в которой можно проверить, с какой стороны беда. Где вы умеете ставить забор посередине, там половинное деление превращает долгий перебор в несколько уверенных шагов. Осталось понять, где именно проводить эту линию раздела.

4. Где именно резать

Ключевой практический вопрос метода: как выбрать точку деления? Тут есть два соображения, и иногда они тянут в разные стороны. Первое: делить надо пополам по количеству неизвестности, а не по физической длине. Половина — это не «середина провода в сантиметрах», а точка, по обе стороны которой примерно поровну возможных мест поломки. Если узлы распределены неравномерно, геометрическая середина обманет: режьте там, где по обе стороны остаётся примерно равное число подозреваемых. Тогда каждая проверка и вправду уполовинивает поиск.

Второе соображение: резать надо там, где проверить легко. Идеальная посередине точка бесполезна, если добраться до неё и что-то в ней измерить страшно трудно. Иногда выгоднее чуть отступить от точной середины к месту, где проверка дёшева и быстра, — потеряешь малость в делении, выиграешь в удобстве. Хороший диагност балансирует: ищет точку, которая и делит близко к пополам, и удобна для проверки. Ещё одна тонкость — куда бить первым делом. Если у вас есть подозрение, что поломка вероятнее в какой-то части, начните деление так, чтобы быстрее проверить именно её: метод прекрасно сочетается с догадками. Но если подозрений нет, чистое деление пополам — лучшая стратегия вслепую: оно гарантированно быстро загонит причину в угол, откуда бы она ни пряталась. Главное правило: не поддавайтесь искушению начать с начала — всегда спрашивайте себя, где здесь середина и как её проверить.

5. Деление во времени и в истории

Половинное деление работает не только в пространстве системы, но и во времени — и это открывает мощные применения. Частый случай: раньше всё работало, а теперь сломалось. Значит, где-то между «тогда» и «сейчас» есть момент или изменение, которое всё испортило. И этот интервал времени можно делить пополам точно так же, как провод. Работало на прошлой неделе, не работает сегодня — а в среду работало? Работало — значит, поломка появилась между средой и сегодня, делим этот отрезок дальше. Так, вопросами «а тогда работало?», мы за несколько шагов сужаем целую неделю до конкретного дня, а то и часа, когда всё сломалось, — а зная момент, легко вспомнить, что тогда изменилось.

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

6. Границы приёма

Метод могуч, но честно очертим, где он работает, а где буксует, чтобы не применять его вслепую. Первое условие: должна быть возможность проверить «середину» — определить, с какой стороны беда, не доходя до края. Если промежуточную точку проверить нельзя (нечего замерить, результат виден только в самом конце), делить не выйдет, и приходится искать другие ходы. Второе: половинки должны быть более-менее независимы, а поломка — одна. Если неисправностей несколько и они путают картину, деление сбивается: середина показывает «плохо» из-за одной причины, а вы гоняетесь за другой. В таких случаях сначала стоит развести проблемы по одной, а уж потом делить.

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

7. Как применять

Соберём в практику. Столкнувшись с задачей локализации — где в системе, в процессе, в последовательности спрятана причина, — не ищите подряд с начала. Действуйте так. Первое: очертите всю зону поиска, все подозреваемые места (или весь интервал времени, весь список версий). Второе: найдите её середину — точку, которая делит зону примерно пополам по числу вариантов и которую можно проверить. Третье: проверьте середину и по результату отбросьте ту половину, где причины точно нет. Четвёртое: повторяйте с оставшейся половиной, пока не останется один кандидат. Несколько таких шагов — и вы у цели, каким бы огромным ни был исходный список.

И, как всегда, приём работает шире техники. Ищете, на каком этапе длинного процесса теряется время, — проверьте середину, а не гоняйте весь процесс с начала. Разбираетесь, когда в отношениях всё пошло не так, — делите время пополам: полгода назад уже было напряжение? Выясняете, какой из многих факторов виноват, — отключите половину и посмотрите. Разбитый на пополам поиск — универсальный способ быстро найти иголку в стоге сена, будь то неисправная деталь, роковая правка, потерянный час или спорный пункт. Приучите себя к одному вопросу перед любым долгим перебором: а где здесь середина и как её проверить? Он экономит бездну времени. В следующей лекции спустимся с уровня «где сломалось» на уровень «почему» — разберём, как докапываться до корневой причины методом «пяти почему» и с помощью дерева причин.

Итоги

• Метод половинного деления (бинарный поиск): не проверять узлы подряд с начала, а бить в середину — каждая проверка отсекает половину зоны поиска.
• Скорость почти волшебная и логарифмическая: тысяча узлов — около десяти проверок, миллион — двадцать. Чтобы прибавилась одна проверка, систему надо удвоить, поэтому размер почти не мешает.
• Образ «волчьего забора»: ставь забор посередине и слушай, с какой стороны воет волк; «забор» — любая проверка, делящая проблему надвое.
• Где резать: пополам по числу вариантов (не по физической длине) и там, где проверить легко; при наличии подозрений начинай с более вероятной части.
• Делить можно и время («а тогда работало?» — сужаем интервал до момента поломки), и историю изменений (найти правку, внёсшую баг), и список настроек (отключить половину).
• Границы приёма: нужна возможность проверить середину; поломка должна быть одна; в системах с обратными связями «стороны» определяют по логике системы. Иначе — сначала развести проблемы.

Вопросы для самопроверки

1. Чем проверка в середине выгоднее проверки с краю? Что она делает с зоной поиска?
2. Почему метод почти не замедляется на больших системах? Что значит «удвой систему — плюс одна проверка»?
3. Объясните образ «волчьего забора». Что в вашей задаче играет роль забора?
4. Как применить половинное деление ко времени и к истории изменений?
5. Возьмите задачу с длинным перебором и опишите, как решить её делением пополам.

Литература

• Дэвид Аганс. «Отладка. 9 незыблемых правил» — правило «разделяй и властвуй» в поиске неисправностей.
• Джон Бентли. «Жемчужины программирования» — сила бинарного поиска и деления пополам.
• Дональд Кнут. «Искусство программирования», том 3 — бинарный поиск как основа быстрых методов.

Это четвёртая лекция курса «Траблшутинг». В следующей спустимся с уровня «где сломалось» на уровень «почему» — разберём, как докапываться до корневой причины методом «пяти почему» и с помощью дерева причин. А сузить свою задачу делением пополам всегда можно вместе с Фреди.