Отладка и бинарный поиск - PullRequest
2 голосов
/ 09 мая 2009

«Программирование жемчужин» в столбце 2 («AHA! Алгоритм») рассказывает о том, как бинарный поиск помогает в различных процессах, таких как сортировка, обход дерева. Но в нем упоминается, что двоичный поиск можно использовать в «программной отладке». Может кто-нибудь объяснить, как это делается?

Ответы [ 7 ]

8 голосов
/ 31 августа 2015

Двоичный поиск - это эффективный способ найти элемент в отсортированном списке. Например, если вы ищете определенную страницу в книге (скажем, стр. 147), вы откроете книгу около середины и определите, открыта ли страница до или после искомой страницы. Затем вы выберете раздел, к которому сузили его, и повторите процесс: разделите его пополам и определите, какая половина содержит страницу 147. Даже лучше, вы можете догадаться, как далеко на странице 147 - не далеко, если книга очень длинный и ближе к концу короткой книги - и используйте это предположение в качестве первой точки деления. Этот вариант бинарного поиска называется интерполяционный поиск .

Таким образом, если у вас есть ошибка и отсортированный список, в котором она может скрываться, то поиск с помощью интерполяции обычно является способом ее устранения. Другие ответы объясняют типичные случаи ошибки, скрытой где-то в диапазоне строк или коммитов исходного кода. Но техника может применяться в других ситуациях:

  • поиск по журналу

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

    В этом случае практически нет другого выбора, кроме как открыть журналы где-то посередине и посмотреть, существует проблема или нет. Затем вырежьте раздел, в котором вы знаете, что ошибка скрывается, и снова найдите ее. В конце концов, вы сможете обнаружить первый момент появления вашей ошибки, что значительно облегчит поиск виновника.

  • входной поиск

    На днях я заметил неясную «ошибку» с длинным текстом . Самый быстрый способ отследить точную границу между текстом, который работает, и текстом, который сломал систему, был разрезать текст пополам, пока я не нашел разделительную линию. (Оказывается Я идиот , но я справился лучше Считая бананы .)

  • концептуальные этапы процесса

    Большинство людей даже не знают, что они большую часть времени используют бинарный (или, лучше, интерполяционный) поиск; это действительно естественный способ решить проблему. Размышляя о длинной последовательности шагов, которая включает в себя потенциальную ошибку, часто разумно сначала проверить вывод одного из промежуточных шагов, чтобы избежать проверки всего кода только для того, чтобы найти проблему на последнем шаге.

7 голосов
/ 09 мая 2009

Если вы не знаете, какая строка в программе из 100 строк содержит ошибки, вы попытаетесь запустить первые 50 строк и пропустить остальные. Если проблема обнаружится, вы знаете, что этот первый сегмент содержит ошибку. Затем вы попытаетесь разделить это и запустить первые 25 строк и посмотреть, есть ли проблема и так далее, пока вы не нашли достаточно короткий фрагмент, чтобы на него смотреть.

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

6 голосов
/ 10 мая 2009

Другая возможность состоит в том, что у вас есть ошибка, и вы знаете, что ее не было в февральском выпуске, но это было в апрельском выпуске (или, скорее, в апрельском выпуске кандидат - вы бы никогда не отправляйте сообщение об ошибке своим пользователям, верно?).

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

Это очень хорошо работает с Subversion , потому что он имеет номера ревизий в репозитории. Если ваш февральский выпуск был 533-й версией, а ваш апрельский выпуск был 701-й версией, то вы обновляетесь до 617-й версии, тестируете его и идете оттуда. (На самом деле, я обычно округляю до 600, поэтому мне не нужно делать много математики в моей голове.) Как только я начинаю сужать это, я начинаю смотреть на комментарии коммита и делать обоснованные предположения («Я действительно не думаю, что этот коммит сломал бы его "), поэтому мне обычно не нужно делать все проверки журнала 2 (n).

Я никогда не использовал Git , но они продвинулись на один шаг дальше со встроенной командой " bisect ". Вы даете ему начальную точку (когда было известно, что она работает?) И конечную точку (когда вы заметили, что она сломана?), И она автоматически получит код для половины пути в бинарном поиске. Затем, после того как вы собрали и протестировали, вы сообщаете ему, прошел ли этот оборот или нет; затем он получает код для следующего промежуточного пункта. Вы можете даже сказать ему, чтобы он запускал команду для каждой версии и использовал код завершения команды, чтобы определить, является ли эта проверка успешной или неудачной, и в этот момент она может работать в полностью автоматическом режиме.

4 голосов
/ 10 мая 2009

Двоичный поиск может помочь в отладке следующими способами:

  1. Предположим, контроль должен достичь определенной точки, а вы подозреваете, что это не так. Поместите операторы печати в первую и последнюю строки кода. Предположим, вы видите результат первого, но не второго утверждения. Поместите заявление печати в середине и попробуйте снова. Таким образом, вы используете бинарный поиск по пространству строк кода, чтобы сосредоточиться на ошибке.
  2. Предположим, вы используете систему контроля версий. Версия 10 прошла все тесты. Версия 70, готовящаяся к выпуску, не проходит некоторые тесты. Проверьте версию 40 и запустите тесты на ней. Если все работает нормально, попробуйте версию 55. Если сбой версии 40, попробуйте версию 25. Таким образом, вы используете бинарный поиск по пространству версий программы, чтобы сосредоточиться на первой версии, где в программе появилась ошибка.
1 голос
/ 09 мая 2009

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

0 голосов
/ 31 августа 2015

Полный алгоритм называется Delta Debugging и был разработан Андреасом Целлером, профессором информатики и автором книги Почему программы не работают .

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

Полный алгоритм не так сложен для понимания, на самом деле очень прост. Однако иногда трудно воспроизвести ошибку и применить решение, была ли проблема воспроизведена.

Помимо книги, существует бесплатный онлайн-курс по Udacity . Если вы предпочитаете короткую версию, прочитайте его IEEE paper

0 голосов
/ 09 августа 2015

Вы можете закомментировать код, добавить комментарий к журналу или просто установить точку останова

отлично подходит для кода без ошибок, но с неисправной функцией, и вы полны неуверенности в себе

Сначала установите привкус точки останова в середине кода, если все хорошо, то вы знаете, что проблема не в этом

затем установите его на уровне 75% кодовой точки - если проблема возникает здесь, то вы знаете, что она находится в коде между 50% и 75%

Итак, затем вы установите его на 57%

Опять же, если проблема есть, вы снова делите ее пополам

Обычно вы можете найти проблему за несколько минут, а не тратить интеллектуальные часы на повторный анализ вашего кода

Тогда вам решать, как это исправить.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...