Программирование. Принципы и практика использования C++ Исправленное издание

Используйте в качестве критерия сравнения (сортировки) оператор “меньше” (<). Можете выбрать любую структуру данных, любые способы вызова функций и способ возвращения результата, но обязательно напишите эту программу самостоятельно. Это редкий случай, когда использование функции, написанной кем-то другим, является контрпродуктивным, даже если эта функция написана хорошо. В частности, не используйте алгоритмы из стандартной библиотеки (binary_search или equal_range, которые в любой другой ситуации были бы наилучшим выбором. Можете затратить на разработку этой программы сколько угодно времени.

Итак, вы написали функцию для бинарного поиска. Если нет, то вернитесь к предыдущему абзацу. Почему вы уверены, что ваша функция поиска корректна? Изложите свои аргументы, обосновывающие корректность программы.

  Вы уверены в своих аргументах? Нет ли слабых мест в вашей аргументации? Это была тривиальная программа, реализующая очень простой и хорошо известный алгоритм. Исходный текст вашего компилятора занимает около 200 Кбайт памяти, исходный текст вашей операционной системы — от 10 до 50 Мбайт, а код, обеспечивающий безопасность полета самолета, на котором вы отправитесь отдыхать во время ваших следующих каникул или на конференцию, составляет от 500 Кбайт до 2 Мбайт. Это вас утешает? Как применить методы, которые вы использовали для проверки функции бинарного поиска, к реальному программному обеспечению, имеющему гораздо большие размеры.

Любопытно, что, несмотря на всю сложность, большую часть времени большая часть программного обеспечения работает правильно. К этому числу критически важных требований программы мы не относим игровые программы на персональных компьютерах. Следует подчеркнуть, что программное обеспечение с особыми требованиями к безопасности практически всегда работает корректно. Мы не будем упоминать в этой связи программное обеспечение бортовых компьютеров авиалайнеров или автомобилей из-за того, что за последнее десятилетие были зарегистрированы сбои в их работе. Рассказы о банковском программном обеспечении, вышедшем из строя из-за чека на 0,00 доллара, в настоящее время устарели; такие вещи больше не происходят. И все же программное обеспечение пишут такие же люди, как вы. Вы знаете, что делаете ошибки; но если мы можем делать ошибки, то почему следует думать, что “они” их не делают?

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

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

26.1.1. Предостережение

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

26.2. Доказательства

  Постойте! Почему бы просто не доказать, что наши программы корректны, и не возиться с тестами? Как лаконично указал Эдсгер Дейкстра (Edsger Dijkstra): “Тестирование может выявить наличие ошибок, а не их отсутствие”. Это приводит к очевидному желанию доказать корректность программ так, как математики доказывают теоремы.