Файл: Лекции СД.doc

3. 1.3. Операции над структурами данных

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

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

Для структур данных, объявленных в программе, память выделяется автоматически средствами систем программирования, на этапе компиляции, либо при активизации процедурного блока, в котором объявляются соответствующие переменные. Можно самостоятельно выделять память для структур данных, используя имеющиеся в системе подпрограммы выделения/освобождения памяти. В объектно-ориентированных языках программирования при разработке нового объекта для него должны быть определены процедуры создания и уничтожения, представляемые конструкторами и деструкторами.

Независимо от используемого языка, имеющиеся структуры данных не появляются «из ничего», а явно или неявно объявляются операторами создания структур. В результате всем экземплярам структур в программе выделяется память для их размещения.

Операция уничтожения структур данных противоположна по своему действию операции создания. Некоторые языки, такие как BASIC, FORTRAN не дают возможности уничтожать созданные структуры данных. В языках PL/1, C, PASCAL структуры данных, имеющиеся внутри блока, уничтожаются в процессе выполнения программы при выходе из этого блока (например, удаление локальных переменных подпрограмм). Операция уничтожения помогает эффективно использовать память.

Операция выбора используется для доступа к данным внутри структуры. Способ доступа зависит от типа структуры данных, к которой осуществляется обращение. Реализация метода доступа – один из наиболее важных свойств структур.

Операция обновления позволяет изменить значения данных в структуре данных. Примером операции обновления является операция присваивания, или, более сложная форма – передача параметров.

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

4. 1.4. Порядок алгоритма

Критерием оценки эффективности алгоритма является его порядок. Порядком алгоритма называется функция O(n), позволяющая оценить зависимость времени выполнения алгоритма от объема обрабатываемых данных (n – количество элементов). Говорят, алгоритм принадлежит классу O(f(n)), где f(n) – некоторая функция от n. Такое обозначение читается как «О большое от f(n)» или менее строго «пропорционально f(n)». Например, алгоритм последовательного поиска принадлежит к классу O(n), а бинарный – к классу O(log(n)). Эффективность тем выше, чем меньше время его выполнения зависит от объема данных.

Поскольку для положительных чисел log(n) < n, можно сделать вывод, что бинарный поиск всегда быстрее последовательного. Предположим, экспериментально определено, что некоторый алгоритм принадлежит к классу O(n²+n). Следовательно, можно подобрать константу k, для которой:

Отсюда видно, что умножение математической функции внутри скобок в О-нотации на константу не оказывает влияния на смысл нотации. Например, O(3*f(n)) эквивалентно O(f(n)), поскольку 3 можно вынести как коэффициент пропорциональности. Кроме того, если величина n достаточно велика при тестировании алгоритма, можно утверждать, что влияние члена «n» поглощается «n²». Поэтому алгоритм O(n²+n) эквивалентен O(n²). То же справедливо и для высших степеней, например, влияние «n²» будет поглощено «n³». В свою очередь, влияние log(n) будет поглощаться членом n.

Предположим, некоторый алгоритм выполняет несколько различных задач. Первая задача принадлежит к классу O(n), вторая – к классу O(n²), третья – к классу O(log(n)). Требуется определить быстродействие алгоритма в целом. Ответом будет O(n²), поскольку к этому классу принадлежит доминантная часть алгоритма.

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

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

Константы k1 и k2 сравнимы по величине. Если следовать О-нотации, предпочтительнее будет первый алгоритм, поскольку он принадлежит к классу O(n). Однако, если известно, что в реальных условиях n не будет превышать 100, более эффективным окажется второй алгоритм. Следовательно, алгоритм нужно выбирать не только основываясь на O-нотации, но и исходя из условий его применения и статистических данных о времени его выполнения.

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

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

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

Большинство алгоритмов с точки зрения порядка сводятся к трем основным типам: степенным O(n^a), линейным O(n) и логарифмическим O(log_an). Эффективность степенных алгоритмов считается плохой, линейных – удовлетворительной, логарифмических – хорошей. Аналитическое определение порядка алгоритма сложно, но в большинстве случаев возможно. В реальных задачах имеются ограничения, определяемые как логикой задачи, так и свойствами конкретной вычислительной среды, которые могут помогать или мешать и существенно влиять на эффективность конкретной реализации алгоритма. Поэтому выбор того или иного алгоритма всегда остается за разработчиком.

5. 1.5. Структурность данных и технологии программирования

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

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

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

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

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

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

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

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

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

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

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

Современные языки программирования блочного типа (PASCAL, C) обладают развитыми возможностями построения программ модульной структуры и управления доступом модулей к данным и процедурам. Сконструированные и полностью закрытые типы данных представляют объекты, а процедуры, работающие с их внутренней структурой – методами. Развитие данного подхода связано с объектно-ориентированной методологией, реализованной в виде объектных моделей в различных языках программирования.