Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [ 62 ] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

Тестовые данные. Серьезные усилия следует направить на получение хороших данных для первых же тестов. Первоначальный набор тестовых данных должен покрывать широкий диапазон частных случаев; должны быть известны правильные ответы. Нужно включать данные, проверяющие все условия ошибок. Можно такх<е пропустить через программу какие-нибудь «бессмысленные» данные, чтобы посмотреть, правильно ли они обрабатываются.

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

Проверяйте программу на данных, лежащих на границах допустимых диапазонов. Если диапазон для входных данных определяется размером задачи, сделайте отдельную попытку проверить очень большие и очень маленькие задачи. Обратите особое внимание на «нулевые случаи», например пустые строки, сети без вершин или ребер, нулевые матрицы и т. д. Если программой будут пользоваться часто, то мох<;ете быть уверены, что все возмох<ные крайние случаи рано или поздно проявятся. Проверьте их вовремя.

Проверяйте программу на данных, выходящих за пределы приемлемого диапазона входных данных. Остерегайтесь опасной ситуации, когда программа выдает правдоподобные (но неверные) результаты.

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

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

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

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

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



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

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

Проверка эффективности реализации

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

Следует проводить различие между эффективностью реализации или кодирования и вычислительной сложностью. Предположим, что мы разработали алгоритм и теоретический анализ показывает, что он имеет сложность О {п% где п - некоторое число, характеризующее размер задачи. Предположим далее, что детальный анализ реализации этого алгоритма дает точную верхнюю границу 2?г+5«+17 для числа выполняемых операторов. Чего же мы должны ожидать от проверки эффективности реализации? Важно понять, что упрощение кодировки обычно не изменяет основного поведения порядка О (/г*); это существенное свойство алгоритма и связанных с ним структур данных. Однако более эффективное кодирование может существенно уменьшить количество операций. Например,.некоторая перестановка операторов

могла бы понизить точную верхнюю границу до -п*+5п+20. Новая

реализация потребует вчетверо меньше времени, чем первоначальная, хотя сложность по-прежнему будет 0{п?).

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

Существует много методов, которыми можно воспользоваться для повышения эффективности программы. Многие из них используют детальные знания о- конкретном компиляторе или ошерадионвой системе. Ими мы пренебрежем, а только упомянем несколько наиболее широко применяемых машинно-независимых методов. Затем мы обсудим полезную универсальную процедуру проверки, известную под названием профилирования.



Арифметические операции. Арифметические операции сложения и вычитания выполняются быстрее, чем умножение и деление. Возведение в степень - самая медленная операция. Кроме того, целочисленная арифметика обычно быстрее арифметики вещественных чисел. Таким образом, величину быстрее вычислить как Х»Х, чем Х«»2.0, а Х+Х может оказаться быстрее, чем 2.0«Х.

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

П00Т1 = (-В + SORT(B**2-4.6 *А* С))/{2.0 * А) R00T2 = (-В - SQRT(B ** 2-4.0 * А * С))/(2;о * А)

эффективнее воспользоваться записью

DENOM = A+A , DISCRIM.= SQRT(B * В - 4.0 * А * С) ROOT1 =(-B + DISCfilM)/DENOR1 R00T2 = (-В -DISCR!M)/DEIMOiVI

(Мы исключили проверку на мнимый корень.) Экономия времени зависит от конкретного компилятора.

Порядок в логических выражениях. Большинство компиляторов прекращает вычисление логических выражений, как только результат получен. Например, в выражении А .OR. В .OR. С вычисление будет прекращено, как только будет найдено значение TRUE. Некоторое время можно сэкономить, разместив А, В и С так, чтобы А вероятнее всего оказалось истинным, В - следующим по величине вероятности, а С - с наименьшей вероятностью.

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

Одним из методов сокращения затрат времени на циклы является сокращение числа повторений. Это исключает дорогие операции увеличения счетчика цикла и его проверки. Например, рассмотрим следующую программу инициализации:

00 10 1 = 1,1000 А(1) = 0.0

10 CONTINUE

DO 20 J = 1.1000 B(J) = 0.0

go CONTINUE -



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [ 62 ] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0011