Почему у методов мало аргументов?

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

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

Поля класса или функции без аргументов?

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

Если бы синтаксис описания метода допускал отсутствие скобок у функции (метода), в случае, когда список аргументов отсутствует, то клиент класса мог бы и не знать, обращается ли он к полю или к методу. Такой синтаксис принят, например, в языке Eiffel. Преимущество этого подхода в том, что изменение реализации никак не сказывается на клиентах класса. В языке C# это не так. Когда мы хотим получить длину строки, то пишем s.Length, точно зная, что Length - это поле, а не метод класса String. Если бы по каким-либо причинам разработчики класса String решили изменить реализацию и заменить поле Length соответствующей функцией, то ее вызов имел бы вид s.Length().

Пример: две версии класса Account

Проиллюстрируем рассмотренные выше вопросы на примере проектирования классов Account и Account1, описывающих такую абстракцию данных, как банковский счет. Определим на этих данных две основные операции - занесение денег на счет и снятие денег. В первом варианте - классе Account - будем активно использовать поля класса. Помимо двух основных полей credit и debit, хранящих приход и расход счета, введем поле balance, которое задает текущее состояние счета, и два поля, связанных с последней выполняемой операцией. Поле sum будет хранить сумму денег текущей операции, а поле result - результат выполнения операции. Полей у класса много, и как следствие, у методов класса аргументов будет немного. Вот описание нашего класса:

/// <summary>/// Класс Account определяет банковский счет. Простейший/// вариант с возможностью трех операций: положить деньги/// на счет, снять со счета, узнать баланс.Вариант с полями/// </summary>public class Account{ //закрытые поля класса int debit=0, credit=0, balance =0; int sum =0, result=0; /// <summary> /// Зачисление на счет с проверкой /// </summary> /// <param name="sum">зачисляемая сумма</param> public void putMoney(int sum) { this.sum = sum; if (sum >0) { credit += sum; balance = credit - debit; result =1; } else result = -1; Mes(); }//putMoney /// <summary> /// Снятие со счета с проверкой /// </summary> /// <param name="sum"> снимаемая сумма</param> public void getMoney(int sum) { this.sum = sum; if(sum <= balance) { debit += sum; balance = credit - debit; result =2; } else result = -2; Mes(); }//getMoney /// <summary> /// Уведомление о выполнении операции /// </summary> void Mes() { switch (result) { case 1: Console.WriteLine("Операция зачисления денег прошла успешно!"); Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}",sum, balance); break; case 2: Console.WriteLine("Операция снятия денег прошла успешно!"); Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}", sum,balance); break; case -1: Console.WriteLine("Операция зачисления денег не выполнена!"); Console.WriteLine("Сумма должна быть больше нуля!"); Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}", sum,balance); break; case -2: Console.WriteLine("Операция снятия денег не выполнена!"); Console.WriteLine("Сумма должна быть не больше баланса!"); Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}", sum,balance); break; default: Console.WriteLine("Неизвестная операция!"); break; } }}//Account

9. Лекция: Процедуры и функции - методы класса

9.4

Как можно видеть, только у методов getMoney и putMoney имеется один входной аргумент. Это тот аргумент, который нужен по сути дела, поскольку только клиент может решить, какую сумму он хочет снять или положить на счет. Других аргументов у методов класса нет - вся информация передается через поля класса. Уменьшение числа аргументов приводит к повышению эффективности работы с методами, так как исчезают затраты на передачу фактических аргументов. Но за все надо платить. В данном случае, усложняются сами операции работы со вкладом, поскольку нужно в момент выполнения операции обновлять значения многих полей класса. Закрытый метод Mes вызывается после выполнения каждой операции, сообщая о том, как прошла операция, и информируя клиента о текущем состоянии его баланса.

А теперь спроектируем аналогичный класс Account1, отличающийся только тем, что у него будет меньше полей. Вместо поля balance в классе появится соответствующая функция с этим же именем, вместо полей sum и result появятся аргументы у методов, обеспечивающие необходимую передачу информации. Вот как выглядит этот класс:

/// <summary>/// Класс Account1 определяет банковский счет./// Вариант с аргументами и функциями/// </summary>public class Account1{ //закрытые поля класса int debit=0, credit=0; /// <summary> /// Зачисление на счет с проверкой /// </summary> /// <param name="sum">зачисляемая сумма</param> public void putMoney(int sum) { int res =1; if (sum >0)credit += sum; else res = -1; Mes(res,sum); }//putMoney /// <summary> /// Снятие со счета с проверкой /// </summary> /// <param name="sum"> снимаемая сумма</param> public void getMoney(int sum) { int res=2; if(sum <= balance())debit += sum; else res = -2; balance(); Mes(res, sum); }//getMoney/// <summary>/// вычисление баланса/// </summary>/// <returns>текущий баланс</returns> int balance() { return(credit - debit); } /// <summary> /// Уведомление о выполнении операции /// </summary> void Mes(int result, int sum) { switch (result) { case 1: Console.WriteLine("Операция зачисления денег прошла успешно!"); Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}", sum,balance()); break; case 2: Console.WriteLine("Операция снятия денег прошла успешно!"); Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}", sum,balance()); break; case -1: Console.WriteLine("Операция зачисления денег не выполнена!"); Console.WriteLine("Сумма должна быть больше нуля!"); Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}", sum,balance()); break; case -2: Console.WriteLine("Операция снятия денег не выполнена!"); Console.WriteLine("Сумма должна быть не больше баланса!"); Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}", sum,balance()); break; default: Console.WriteLine("Неизвестная операция!"); break; } }}//Account1

Сравнивая этот класс с классом Account, можно видеть, что число полей сократилось с пяти до двух, упростились основные методы getMoney и putMoney. Но, в качестве платы, у класса появился дополнительный метод balance(), многократно вызываемый, и у метода Mes теперь появились два аргумента. Какой класс лучше? Однозначно сказать нельзя, все зависит от контекста, от приоритетов, заданных при создании конкретной системы.

Приведу процедуру класса Testing, тестирующую работу с классами Account и Account1:

public void TestAccounts(){ Account myAccount = new Account(); myAccount.putMoney(6000); myAccount.getMoney(2500); myAccount.putMoney(1000); myAccount.getMoney(4000); myAccount.getMoney(1000); //Аналогичная работа с классом Account1 Console.WriteLine("Новый класс и новый счет!"); Account1 myAccount1 = new Account1(); myAccount1.putMoney(6000); myAccount1.getMoney(2500); myAccount1.putMoney(1000); myAccount1.getMoney(4000); myAccount1.getMoney(1000);}

На рис. 9.1 показаны результаты работы этой процедуры.

Рис. 9.1. Тестирование классов Account и Account1

9. Лекция: Процедуры и функции - методы класса

9.5

Функции с побочным эффектом

Функция называется функцией с побочным эффектом, если помимо результата, вычисляемого функцией и возвращаемого ей в операторе return, она имеет выходные аргументы с ключевыми словами ref и out. В языках C/C++ функции с побочным эффектом применяются сплошь и рядом. Хороший стиль ОО-программирования не рекомендует использование таких функций. Выражения, использующие функции с побочным эффектом, могут потерять свои прекрасные свойства, присущие им в математике. Если f(a) - функция с побочным эффектом, то a+f(a) может быть не равно f(a) +a, так что теряется коммутативность операции сложения.

Примером такой функции является функция f, приведенная выше. Вот тест, демонстрирующий потерю коммутативности сложения при работе с этой функцией:

/// <summary>/// тестирование побочного эффекта/// </summary>public void TestSideEffect(){ int a = 0, b=0, c=0; a =1; b = a + f(ref a); a =1; c = f(ref a)+ a; Console.WriteLine("a={0}, b={1}, c={2}",a,b,c);}

На рис. 9.2 показаны результаты работы этого метода.

Рис. 9.2. Демонстрация вызова функции с побочным эффектом

Обратите внимание на полезность указания ключевого слова ref в момент вызова. Его появление хоть как-то оправдывает некоммутативность сложения.

Методы. Перегрузка

Должно ли быть уникальным имя метода в классе? Нет, этого не требуется. Более того, проектирование методов с одним и тем же именем является частью стиля программирования на С++ и стиля C#. Существование в классе методов с одним и тем же именем называется перегрузкой, а сами одноименные методы называются перегруженными.

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

Перегрузка характерна и для знаков операций. В зависимости от типов аргументов, один и тот же знак может выполнять фактически разные операции. Классическим примером является знак операции сложения +, который играет роль операции сложения не только для арифметических данных разных типов, но и выполняет конкатенацию строк.

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

Перегрузка требует уточнения семантики вызова метода. Когда встречается вызов неперегруженного метода, то имя метода в вызове однозначно определяет, тело какого метода должно выполняться в точке вызова. Когда же метод перегружен, то знания имени недостаточно - оно не уникально. Уникальной характеристикой перегруженных методов является их сигнатура. Перегруженные методы, имея одинаковое имя, должны отличаться либо числом аргументов, либо их типами, либо ключевыми словами (заметьте: с точки зрения сигнатуры, ключевые слова ref и out не отличаются). Уникальность сигнатуры позволяет вызвать требуемый перегруженный метод.

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

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

Насколько полезна перегрузка методов? Здесь нет экономии кода, поскольку каждую реализацию нужно задавать явно; нет выигрыша по времени - напротив, требуются определенные затраты на поиск подходящей реализации, который может приводить к конфликтам, - к счастью, обнаруживаемым на этапе компиляции. В нашем примере вполне разумно иметь четыре метода с разными именами и осознанно вызывать метод, применимый к данным аргументам. Все-таки есть ситуации, где перегрузка полезна, недаром она широко используется при построении библиотеки FCL. Возьмем, например, класс Convert, у которого 16 методов с разными именами, зависящими от целевого типа преобразования. Каждый из этих 16 методов перегружен, и в свою очередь, имеет 16 реализаций в зависимости от типа источника. Согласитесь, что неразумно было бы иметь в классе Convert 256 методов вместо 16-ти перегруженных методов. Впрочем, также неразумно было бы пользоваться одним перегруженным методом, имеющим 256 реализаций. Перегрузка - это инструмент, который следует использовать с осторожностью и обоснованно.

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

/// <summary>/// Тестирование перегруженных методов A()/// </summary>public void TestLoadMethods(){ long u=0; double v =0; A(out u, 7); A(out v, 7.5); Console.WriteLine ("u= {0}, v= {1}", u,v); A(out v,7); Console.WriteLine("v= {0}",v); A(out u, 7,11,13); A(out v, 7.5, Math.Sin(11.5)+Math.Cos(13.5), 15.5); Console.WriteLine ("u= {0}, v= {1}", u,v);}//TestLoadMethods

На рис. 9.3 показаны результаты этого тестирования.

Рис. 9.3. Тестирование перегрузки методов

10. Лекция: Корректность методов. Рекурсия

10.1

Корректность метода. Спецификации. Триады Хоара. Предусловие метода. Постусловие метода. Корректность метода по отношению к предусловию и постусловию. Частичная корректность. Завершаемость. Полная корректность. Инвариант цикла. Вариант цикла. Подходящий инвариант. Корректность циклов. Рекурсия. Прямая и косвенная рекурсия. Стратегия "разделяй и властвуй". Сложность рекурсивных алгоритмов. Задача "Ханойские башни". Быстрая сортировка Хоара.

Корректность методов

Написать метод, задающий ту или иную функциональность, нетрудно. Это может сделать каждый. Значительно сложнее написать метод, корректно решающий поставленную задачу. Корректность метода - это не внутреннее понятие, подлежащее определению в терминах самого метода. Корректность определяется по отношению к внешним спецификациям метода. Если нет спецификаций, то говорить о корректности "некорректно".

Спецификации можно задавать по-разному. Мы определим их здесь через понятия предусловий и постусловий метода, используя символику триад Xoара, введенных Чарльзом Энтони Хоаром - выдающимся программистом и ученым, одну из знаменитых программ которого приведем чуть позже в этой лекции.

Пусть P(x,z) - программа P с входными аргументами x и выходными z. Пусть Q(y) - некоторое логическое условие (предикат) над переменными программы y. Язык для записи предикатов Q(y) формализовать не будем. Отметим только, что он может быть шире языка, на котором записываются условия в программах, и включать, например, кванторы. Предусловием программы P(x,z) будем называть предикат Pre(x), заданный на входах программы. Постусловием программы P(x,z) будем называть предикат Post(x,z), связывающий входы и выходы программы. Для простоты будем полагать, что программа P не изменяет своих входов x в процессе своей работы. Теперь несколько определений:

Определение 1(частичной корректности): Программа P(x,z) корректна (частично, или условно) по отношению к предусловию Pre(x) и постусловию Post(x,z), если из истинности предиката Pre(x) следует, что для программы P(x,z), запущенной на входе x, гарантируется выполнение предиката Post(x,z) при условии завершения программы.

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

[Pre(x)]P(x,z)[Post(x,z)]

Определение 2(полной корректности): Программа P(x,z) корректна (полностью, или тотально) по отношению к предусловию Pre(x) и постусловию Post(x,z), если из истинности предиката Pre(x) следует, что для программы P(x,z), запущенной на входе x, гарантируется ее завершение и выполнение предиката Post(x,z).

Условие полной корректности записывается в виде триады Хоара, связывающей программу с ее предусловием и постусловием:

{Pre(x)}P(x,z){Post(x,z)}

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

Корректная программа говорит своим клиентам: если вы хотите вызвать меня и ждете гарантии выполнения постусловия после моего завершения, то будьте добры гарантировать выполнение предусловия на входе. Задание предусловий и постусловий методов - это такая же важная часть работы программиста, как и написание самого метода. На языке C# пред- и постусловия обычно задаются в теге <summary>, предшествующем методу, и являются частью XML-отчета. К сожалению, технология работы в Visual Studio не предусматривает возможности автоматической проверки предусловия перед вызовом метода и проверки постусловия после его завершения с выбрасыванием исключений в случае их невыполнения. Программисты, для которых требование корректности является важнейшим условием качества их работы, сами встраивают такую проверку в свои программы. Как правило, подобная проверка обязательна на этапе отладки и может быть отключена в готовой системе, в корректности которой программист уже уверен. А вот проверку предусловий важно оставлять и в готовой системе, поскольку истинность предусловий должен гарантировать не разработчик метода, а клиент, вызывающий метод. Клиентам же свойственно ошибаться и вызывать метод в неподходящих условиях.

Формальное доказательство корректности метода - задача ничуть не проще, чем написание корректной программы. Но вот парадокс. Чем сложнее метод, его алгоритм, а следовательно, и само доказательство, тем важнее использовать понятия предусловий и постусловий, понятия инвариантов циклов в процессе разработки метода. Рассмотрение этих понятий параллельно с разработкой метода может существенно облегчить построение корректного метода. Этот подход будет продемонстрирован в нашей лекции при рассмотрении метода QuickSort - быстрой сортировки массива.

10. Лекция: Корректность методов. Рекурсия

10.2

Инварианты и варианты цикла

Циклы, как правило, являются наиболее сложной частью метода - большинство ошибок связано именно с ними. При написании корректно работающих циклов крайне важно понимать и использовать понятия инварианта и варианта цикла. Без этих понятий не обходится и формальное доказательство корректности циклов. Ограничимся рассмотрением цикла в следующей форме:

Init(x,z); while(B)S(x,z);

Здесь B - условие цикла while, S - его тело, а Init - группа предшествующих операторов, задающая инициализацию цикла. Реально ни один цикл не обходится без инициализирующей части. Синтаксически было бы правильно, чтобы Init являлся бы формальной частью оператора цикла. В операторе for эта частично сделано - инициализация счетчиков является частью цикла.

Определение 3(инварианта цикла): предикат Inv(x, z) называется инвариантом цикла while, если истинна следующая триада Хоара:

{Inv(x, z)& B}S(x,z){Inv(x,z)}

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

Для любого цикла можно написать сколь угодно много инвариантов. Любое тождественное условие (2*2 =4) является инвариантом любого цикла. Поэтому среди инвариантов выделяются так называемые подходящие инварианты цикла. Они называются подходящими, поскольку позволяют доказать корректность цикла по отношению к его пред- и постусловиям. Как доказать корректность цикла? Рассмотрим соответствующую триаду:

{Pre(x)} Init(x,z); while(B)S(x,z);{Post(x,z)}

Доказательство разбивается на три этапа. Вначале доказываем истинность триады:

(*) {Pre(x)} Init(x,z){RealInv(x,z)}

Содержательно это означает, что предикат RealInv становится истинным после выполнения инициализирующей части. Далее доказывается, что RealInv является инвариантом цикла:

(**) {RealInv(x, z)& B} S(x,z){RealInv(x,z)}

На последнем шаге доказывается, что наш инвариант обеспечивает решение задачи после завершения цикла:

(***) ~B & RealInv(x, z) -> Post(x,z)

Это означает, что из истинности инварианта и условия завершения цикла следует требуемое постусловие.

Определение 4 (подходящего инварианта): предикат RealInv, удовлетворяющий условиям (*), (**), (***) называется подходящим инвариантом цикла.

С циклом связано еще одно важное понятие - варианта цикла, используемое для доказательства завершаемости цикла.

Определение 5(варианта цикла): целочисленное неотрицательное выражение Var(x, z) называется вариантом цикла, если выполняется следующая триада:

{(Var(x,z)= n) & B} S(x,z){(Var(x,z)= m) & (m < n)}

Содержательно это означает, что каждое выполнение тела цикла приводит к уменьшению значения его варианта. После конечного числа шагов вариант достигает своей нижней границы, и цикл завершается. Простейшим примером варианта цикла является выражение n-i для цикла:

for(i=1; i<=n; i++) S(x, z);

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

10. Лекция: Корректность методов. Рекурсия

10.3

Рекурсия

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

Определение 6(рекурсивного метода): метод P (процедура или функция) называется рекурсивным, если при выполнении тела метода происходит вызов метода P.

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

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

public long factorial(int n){ if (n<=1) return(1); else return(n*factorial(n-1));}//factorial

Функция factorial является примером прямого рекурсивного определения - в ее теле она сама себя вызывает. Здесь, как и положено, есть нерекурсивная ветвь, завершающая вычисления, когда n становится равным единице. Это пример так называемой "хвостовой" рекурсии, когда в теле встречается ровно один рекурсивный вызов, стоящий в конце соответствующего выражения. Хвостовую рекурсию намного проще записать в виде обычного цикла. Вот циклическое определение той же функции:

public long fact(int n){ long res =1; for(int i = 2; i <=n; i++) res*=i; return(res);}//fact

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

public void TestTailRec(){ Hanoi han = new Hanoi(5); long time1, time2; long f=0; time1 = getTimeInMilliseconds(); for(int i = 1; i <1000000; i++)f =han.fact(15); time2 =getTimeInMilliseconds(); Console.WriteLine(" f= {0}, " + "Время работы циклической процедуры: {1}",f,time2 -time1); time1 = getTimeInMilliseconds(); for(int i = 1; i <1000000; i++)f =han.factorial(15); time2 =getTimeInMilliseconds(); Console.WriteLine(" f= {0}, " + "Время работы рекурсивной процедуры: {1}",f,time2 -time1);}

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

Проводить сравнение эффективности работы различных вариантов - это частый прием, используемый при разработке программ. И я им буду пользоваться неоднократно. Встроенный тип DateTime обеспечивает необходимую поддержку для получения текущего времени. Он совершенно необходим, когда приходится работать с датами. Я не буду подробно описывать его многочисленные статические и динамические методы и свойства. Ограничусь лишь приведением функции, которую я написал для получения текущего времени, измеряемого в миллисекундах. Статический метод Now класса DateTime возвращает объект этого класса, соответствующий дате и времени в момент создания объекта. Многочисленные свойства этого объекта позволяют извлечь требуемые характеристики. Приведу текст функции getTimeInMilliseconds:

long getTimeInMilliseconds(){ DateTime time = DateTime.Now; return(((time.Hour*60 + time.Minute)*60 + time.Second)*1000 + time.Millisecond);}

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

Рис. 10.1. Сравнение времени работы циклической и рекурсивной функций

Вовсе не обязательно, что рекурсивные методы будут работать медленнее нерекурсивных. Классическим примером являются методы сортировки. Известно, что время работы нерекурсивной пузырьковой сортировки имеет порядок c*n2, где c - некоторая константа. Для рекурсивной процедуры сортировки слиянием время работы - q*n*log(n), где q - константа. Понятно, что для больших n сортировка слиянием работает быстрее, независимо от соотношения значений констант. Сортировка слиянием - хороший пример применения рекурсивных методов. Она демонстрирует известный прием, называемый "разделяй и властвуй". Его суть в том, что исходная задача разбивается на подзадачи меньшей размерности, допускающие решение тем же алгоритмом. Решения отдельных подзадач затем объединяются, давая решение исходной задачи. В задаче сортировки исходный массив размерности n можно разбить на два массива размерности n/2, для каждого из которых рекурсивно вызывается метод сортировки слиянием. Полученные отсортированные массивы сливаются в единый массив с сохранением упорядоченности.

На примере сортировки слиянием покажем, как можно оценить время работы рекурсивной процедуры. Обозначим через T(n) время работы процедуры на массиве размерности n. Учитывая, что слияние можно выполнить за линейное время, справедливо следующее соотношение:

T(n) = 2T(n/2) + cn

Предположим для простоты, что n задается степенью числа 2, то есть n = 2k. Тогда наше соотношение имеет вид:

T(2k) = 2T(2k-1) + c2k

Полагая, что T(1) =c, путем несложных преобразований, используя индукцию, можно получить окончательный результат:

T(2k) = c*k*2k = c*n*log(n)

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

10. Лекция: Корректность методов. Рекурсия

10.5

Быстрая сортировка Хоара

Продолжая тему рекурсии, познакомимся с реализацией на C# еще одного известного рекурсивного алгоритма, применяемого при сортировке массивов. Описанный ранее рекурсивный алгоритм сортировки слиянием имеет один существенный недостаток - для слияния двух упорядоченных массивов за линейное время необходима дополнительная память. Разработанный Ч. Хоаром метод сортировки, получивший название быстрого метода сортировки - QuickSort, не требует дополнительной памяти. Хотя этот метод и не является самым быстрым во всех случаях, но на практике он обеспечивает хорошие результаты. Нужно отметить, что именно этот метод сортировки встроен в класс System.Array.

Идея алгоритма быстрой сортировки состоит в том, чтобы выбрать в исходном массиве некоторый элемент M, затем в начальной части массива собрать все элементы, меньшие M. Так появляются две подзадачи размерности - k и n-k, к которым рекурсивно применяется алгоритм. Если в качестве элемента M выбирать медиану сортируемой части массива, то обе подзадачи имели бы одинаковый размер и алгоритм быстрой сортировки был бы оптимальным по времени работы. Но расчет медианы требует своих затрат времени и усложняет алгоритм. Поэтому обычно элемент M выбирается случайным образом. В этом случае быстрая сортировка оптимальна лишь в среднем, а для плохих вариантов (когда в качестве M всякий раз выбирается минимальный элемент) имеет порядок n2.

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

/// <summary>/// Вызывает рекурсивную процедуру QSort,/// передавая ей границы сортируемого массива./// Сортируемый массив tower1 задается/// соответствующим полем класса.public void QuickSort(){ QSort(0,size-1);}

Вот чистый текст рекурсивной процедуры быстрой сортировки Хоара:

void QSort(int start, int finish){ if(start != finish) { int ind = rnd.Next(start,finish); int item = tower1[ind]; int ind1 = start, ind2 = finish; int temp; while (ind1 <=ind2) { while((ind1 <=ind2)&& (tower1[ind1] < item)) ind1++; while ((ind1 <=ind2)&&(tower1[ind2] >= item)) ind2--; if (ind1 < ind2) { temp = tower1[ind1]; tower1[ind1] = tower1[ind2]; tower1[ind2] = temp; ind1++; ind2--; } } if (ind1 == start) { temp = tower1[start]; tower1[start] = item; tower1[ind] = temp; QSort(start+1,finish); } else { QSort(start,ind1-1); QSort(ind2+1, finish); } }}// QuickSort

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

/// <summary>/// Небольшая по размеру процедура содержит три/// вложенных цикла while, два оператора if и рекурсивные/// вызовы. Для таких процедур задание инвариантов и/// обоснование корректности облегчает отладку./// </summary>/// <param name="start">начальный индекс сортируемой части/// массива tower</param>/// <param name="finish">конечный индекс сортируемой части/// массива tower</param>/// Предусловие: (start <= finish)/// Постусловие: массив tower отсортирован по возрастаниюvoid QSort(int start, int finish){ if(start != finish) //если (start = finish), то процедура ничего не делает, //но постусловие выполняется, поскольку массив из одного //элемента отсортирован по определению. Докажем истинность //постусловия для массива с числом элементов >1. { int ind = rnd.Next(start,finish); int item = tower1[ind]; int ind1 = start, ind2 = finish; int temp; /// Введем три непересекающихся множества: /// S1: {tower1(i), start <= i =< ind1-1} /// S2: {tower1(i), ind1 <= i =< ind2} /// S1: {tower1(i), ind2+1 <= i =< finish} /// Введем следующие логические условия, /// играющие роль инвариантов циклов нашей программы: /// P1: объединение S1, S2, S3 = tower1 /// P2: (S1(i) < item) Для всех элементов S1 /// P3: (S3(i) >= item) Для всех элементов S3 /// P4: item - случайно выбранный элемент tower1 /// Нетрудно видеть, что все условия становятся /// истинными после завершения инициализатора цикла. /// Для пустых множеств S1 и S3 условия P2 и P3 /// считаются истинными по определению. /// Inv = P1 & P2 & P3 & P4 while (ind1 <=ind2) { while((ind1 <=ind2)&& (tower1[ind1] < item)) ind1++; //(Inv == true) & ~B1 (B1 - условие цикла while) while ((ind1 <=ind2)&&(tower1[ind2] >= item)) ind2--; //(Inv == true) & ~B2 (B2 - условие цикла while) if (ind1 < ind2) //Из Inv & ~B1 & ~B2 & B3 следует истинность: //((tower1[ind1] >= item)&&(tower1[ind2]<item))==true. //Это условие гарантирует, что последующий обмен //элементов обеспечит выполнение инварианта Inv { temp = tower1[ind1]; tower1[ind1] = tower1[ind2]; tower1[ind2] = temp; ind1++; ind2--; } //(Inv ==true) } //из условия окончания цикла следует: (S2 - пустое множество) if (ind1 == start) //В этой точке S1 и S2 - это пустые множества, -> //(S3 = tower1) // Нетрудно доказать, что отсюда следует истинность: //(item = min) // Как следствие, можно минимальный элемент сделать первым, // а к оставшемуся множеству применить рекурсивный вызов. { temp = tower1[start]; tower1[start] = item; tower1[ind] = temp; QSort(start+1,finish); } else // Здесь оба множества S1 и S3 не пусты. // К ним применим рекурсивный вызов. { QSort(start,ind1-1); QSort(ind2+1, finish); } //Индукция по размеру массива и истинность инварианта //доказывает истинность постусловия в общем случае. }}// QuickSort

Приведу некоторые пояснения к этому доказательству. Задание предусловия и постусловия процедуры QSort достаточно очевидно - сортируемый массив должен быть не пустым, а после работы метода должен быть отсортированным. Важной частью обоснования является четкое введение трех множеств - S1, S2, S3 - и условий, накладываемых на их элементы. Эти условия и становятся частью инварианта, сохраняющегося при работе различных циклов нашего метода. Вначале множества S1 и S3 пусты, в ходе вычислений пустым становится множество S2. Так происходит формирование подзадач, к которым рекурсивно применяется алгоритм. Особым представляется случай, когда множество S1 тоже пусто. Н<