Как вы определяете «крайние» случаи на алгоритмах?

25

В основном, как вы узнаете, какой может быть ваш худший или лучший случай, и какие-либо другие «крайние» случаи, которые у вас могут быть, ДО их наличия и так, как вы готовите свой код для них?

Луис Армандо
источник
2
Альтернатива: когда это возможно, я большой поклонник нечеткого тестирования. Удивительно, как масса случайно сгенерированных входных данных может обнаружить ошибки в функции, которые не были подвергнуты тщательному анализу. Они работают очень хорошо вместе ... и они явно дополняются точной регистрацией ошибок при работе на "истинных" входах :)
Matthieu M.

Ответы:

28

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

Например, алгоритм принимает строку и целое число в качестве входных данных и выполняет некоторую сортировку символов строки.

Здесь мы имеем:

Строка с некоторыми известными частными случаями:

  • Пустой строкой
  • Длинная строка
  • Строка Unicode (специальные символы)
  • Если ограничено определенным набором символов, что происходит, когда некоторые из них не находятся в диапазоне
  • Нечетная / четная строка
  • Null (как аргумент)
  • Не нулевое прекращение

Целое число с известными частными случаями:

  • 0
  • Min / MaxInt
  • Отрицательный Положительный

Алгоритм сортировки, который может выйти из строя в следующих граничных случаях:

  • Пустой ввод
  • 1 элемент ввода
  • Очень длинный ввод (возможно, длина max (тип данных, используемый для индекса))
  • Мусор внутри коллекции, которая будет отсортирована
  • Нулевой ввод
  • Дубликаты элементов
  • Коллекция со всеми равными элементами
  • Ввод нечетной / четной длины

Затем возьмите все эти случаи и создайте длинный список, пытаясь понять, как они перекрываются. Пример:

  • Пустой строковый регистр покрывает пустой случай
  • Пустая строка == пустая коллекция
  • и т.п.

Теперь создайте для них контрольные примеры :)

Краткое резюме : разбейте алгоритм на базовые блоки, для которых вы знаете граничные случаи, а затем пересоберите их, создавая глобальные граничные случаи

Виктор Хурдугачи
источник
5
Еще одна вещь, чтобы добавить. , , анализировать код и искать специальные случаи в коде. Если разработчик обрабатывает от 0 до 13 иначе, чем от 14 и выше - возможно, разработчик использует разные алгоритмы для малых и больших значений по соображениям производительности - у вас есть крайние варианты в 13 и 14. +1 для большого списка.
Этель Эванс
2

Я не думаю, что есть какой-либо алгоритм для определения краевых условий .... просто опыт.

Пример: для параметра байта вы хотели бы проверить числа, такие как 0, 127, 128, 255, 256, -1, все, что может вызвать проблемы.

Стив Уэлленс
источник
2

«Край» имеет два значения, и оба имеют отношение, когда дело доходит до краевых случаев. Край - это либо область, где небольшое изменение на входе приводит к значительному изменению на выходе, либо конец диапазона.

Итак, чтобы определить крайние случаи алгоритма, я сначала посмотрю на входную область. Его граничные значения могут привести к граничным случаям алгоритма.

Во-вторых, я смотрю на выходной домен и оглядываюсь на входные значения, которые могут их создать. Это менее часто проблема с алгоритмами, но она помогает найти проблемы в алгоритмах, которые предназначены для генерации выходных данных, которые охватывают заданную область вывода. Например, генератор случайных чисел должен иметь возможность генерировать все предполагаемые выходные значения.

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

MSalters
источник
0

Это очень общий вопрос, поэтому все, что я могу сделать, это выбросить некоторые общие, смутные идеи :)

Изучить граничные случаи. Ex. если вы анализируете строку, что произойдет, если строка будет пустой или нулевой? Если вы считаете от х до у, что происходит в х и у?
-Код, который может быть упрощен или СУХОЙ. Любая ненужная сложность может добавить к вещам, которые могут пойти не так.

seand
источник
0

Часть навыков использования алгоритмов - знание их слабых сторон и патологических ситуаций. Ответ Виктора дает несколько хороших советов, но в целом я бы посоветовал вам изучить эту тему более подробно, чтобы почувствовать это, я не думаю, что вы можете следовать эмпирическим правилам, чтобы полностью ответить на этот вопрос. Например, см. Cormen или Skiena (в частности, у Skiena есть очень хороший раздел о том, где использовать алгоритмы и что хорошо работает в определенных случаях, я думаю, что Cormen углубляется в теорию).

Стив
источник