Платформы разработки и прикладные языки программирования

Негосударственное образовательное учреждение высшего профессионального образования Московский технологический институт «ВТУ» М.Г. Ляпин Учебно-методическое пособие по дисциплине «Платформы разработки и прикладные языки программирования» Москва, 2012 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Оглавление Введение в предмет ............................................................................................................... 4 Глава 1. Введение в алгоритмы и семантические конструкции языков (с использованием Python) ........................................................................................................... 5 1.1 Переменные, базовые типы данных, выражения, базовые операторы ................. 10 1.2 Логические выражения.............................................................................................. 16 1.3 Циклы и операторы циклов ....................................................................................... 19 1.4 Системы счисления, побитовые операции, классические задачи программирования .............................................................................................................. 23 1.5 Массивы, сортировка массива, поиск элемента, матрицы ..................................... 25 1.6 Строки ........................................................................................................................ 31 1.7 Функции и аргументы, прототипы функций .............................................................. 35 1.8 Динамическое программирование ............................................................................... 38 Глава 2. Введение в структуры данных (с использованием Python) .......................... 40 2.1 Списки (коллекции).................................................................................................... 40 2.2 Хеш-таблица, стек, очередь ..................................................................................... 43 2.3 Связные списки, деревья, графы ............................................................................. 46 Глава 3. Объектно-ориентированный подход ................................................................. 54 3.1. Наследование .............................................................................................................. 54 3.2. Инкапсуляция ............................................................................................................... 57 3.3. Полиморфизм............................................................................................................... 58 3.4. Модули в Python ........................................................................................................... 60 3.5. Классы и модули для работы с файлами ................................................................... 62 Глава 4. Особенности языков и технологий программирования ................................. 66 4.1. Особенности программирования и платформ разработки настольных и серверных приложений (рассмотрение C/С++, Java, C#, .NET).......................................................... 70 4.2. Основы и особенности веб-разработки. HTML, XML, Flash, PHP.............................. 81 Глава 5. Актуальные технологии и методики разработки ПО ....................................... 87 5.1. Облачные и параллельные вычисления .................................................................... 87 5.2. Обеспечение и контроль качества ПО ........................................................................ 91 5.3. Средства коллективной разработки приложений....................................................... 94 Глава 6. Автоматизация выполняемых повседневных задач при помощи технологий программирования (макросы, скрипты, визуальные средства программирования) ................................................................................................................ 104 6.1. Скриптовые языки ...................................................................................................... 104 6.2. Инструментарий Python для автоматизации ............................................................ 107 6.3. Визуальные средства программирования ................................................................ 110 Список рекомендуемой литературы и дополнительная литература ......................... 114 2 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Список использованных источников.............................................................................. 116 3 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Введение в предмет Академик А.П. Ершов сказал: «Программист должен обладать способностью первоклассного математика к абстракции и логическому мышлению в сочетании с эдисоновским талантом сооружать все, что угодно, из нуля и единиц. Он должен сочетать аккуратность бухгалтера с проницательностью разведчика, фантазию автора детективных романов с трезвой практичностью экономиста, сочетать в себе лёгкость и полет таланта Моцарта с усидчивостью и скрупулёзностью Сальери… А, кроме того, программист должен иметь вкус к коллективной работе, понимать интересы пользователя и много другое...» [11]. Дисциплина «Платформы разработки и прикладные языки программирования» включает набор базовых понятий, знаний и навыков программирования, необходимых для создания простейших прикладных программ и для перехода к углубленному изучению языков программирования. Кроме того дисциплина освещает платформы, актуальные технологии и методики разработки программного обеспечения. Дисциплина охватывает вопросы, которые позволяют специалисту в области информационных технологий самостоятельно реализовывать скрипты для автоматизации повседневной работы и ориентироваться в многообразии подходов к разработке программного обеспечения. Для изучения основ программирования используется язык высокого уровня Python, который прост в освоении и используется в решении практических задач, в том числе в таких компаниях как Microsoft, IBM, Google, HP и многих других. Спектр решаемых задач довольно широк: от написания простейших скриптов до создания сложных веб-сервисов. Для успешного освоения дисциплины необходимо понимать основы архитектуры электронной вычислительной машины (ЭВМ) и принципы функционирования операционных систем. 4 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Глава 1. Введение в алгоритмы и семантические конструкции языков (с использованием Python) Одной из целей данной дисциплины является изучение основ программирования, поэтому язык программирования Python выступает лишь инструментом для достижения этой цели, как язык, позволяющий эффективно изучить и понять основные алгоритмические структуры и парадигмы программирования. Детально с особенностями языка программирования Python вы можете ознакомиться самостоятельно, используя дополнительную литературу, список которой приведён в конце книги. Язык программирования Python (Пайтон, Питон) был создан голландским программистом Гвидо ван Россумом и получил своё название в честь комедийной телепередачи «Летающий цирк Монти Пайтона». Python – это свободный интерпретируемый язык программирования высокого уровня с динамической типизацией. В Python поддерживаются парадигмы структурного и объектно-ориентированного программирования. Кроме того созданы реализации Python для всех основных платформ. Python — это свободный интерпретируемый объектно- ориентированный расширяемый встраиваемый язык программирования очень высокого уровня [28]. Постепенно мы раскроем смысл всего этого определения. Для того чтобы приступить к изучению программирования и Python на практике, достаточно понимать первое предложение. В этом нам помогут базовые определения, приведённые далее. Программирование – это процесс разработки и реализации компьютерных программ с использованием языков программирования. Под разработкой понимается определение структуры программы и алгоритмов, которые решают поставленную задачу. Реализация программы подразумевает написание программного кода на некотором языке программирования. Государственный стандарт определяет программирование, как научную и практическую деятельность по созданию программ [7]. Программа — данные, предназначенные для управления конкретными компонентами системы обработки информации в целях реализации определённого алгоритма [7]. 5 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Обычно в понятие программы включают не только данные, но и набор команд, которые позволяют использовать вычислительные устройства для получения определённого результата. Совокупность программ системы обработки информации и программных документов, необходимых для эксплуатации этих программ, образует программное обеспечение. Целью работы любой программы является реализация определённых алгоритмов, необходимых для достижения результата. Строго определения алгоритма нет, однако словесное описание и свойства алгоритма можно найти у отечественных учёных-математиков А. Колмогорова, А. Маркова и американского ученого, теоретика программирования Д. Кнута, а также в государственном стандарте [8]. Алгоритм – конечный набор предписаний для получения решения задачи посредством конечного количества операций (ГОСТ 34.003-90 [8]). Алгоритм – это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи (Колмогоров [16]). Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату (Марков [19]). Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность (Кнут [15]). Дональд Кнут в своей фундаментальной работе «Искусство программирования» [15] определяет пять важных свойств алгоритма: Конечность. Алгоритм всегда должен заканчиваться после выполнения конечного числа шагов. Определенность. Каждый шаг алгоритма должен быть точно определен. Наличие входных данных. Алгоритм имеет некоторое число входных данных, задающихся до начала его работы или определяющихся динамически во время его выполнения. Наличие выходных данных. Алгоритм имеет одно или несколько выходных данных, имеющих определенную связь с входными данными. 6 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Эффективность. Алгоритм обычно считается эффективным, если его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени. Схематичное изображение места алгоритма в вычислительном процессе, иллюстрирующее понятие алгоритма, представлено на рисунке 1.1. Рисунок 1.1. Схема, иллюстрирующая понятие алгоритма и его место в процессе решения поставленной задачи. Принято различать естественные и формальные языки – знаковые системы, используемые для записи и передачи информации. К естественным языкам относят разговорную и письменную речь, особенностью которых является отсутствие однозначного понимания одних и тех же синтаксических конструкций. Например, одно и то же слово может иметь несколько значений. Формальные языки, напротив, позволяют однозначно записывать и понимать передаваемую информацию, используя определённый алфавит, чёткие правила, обеспечивая непротиворечивое, точное и компактное отображение свойств и отношений изучаемой предметной области. ЭВМ не может воспринимать задачи, записанные на естественном языке без приведения их к формализованному виду. Это связано с тем, что вычислительное устройство способно воспринимать только числовые команды, описывающие код операций и адреса ячейки памяти, в которой хранятся данные, используемые в вычислениях. Такой язык команд называют машинным языком или машинным кодом. Вертикальные стрелки на рисунке 1.1 изображают перевод задачи с естественного языка на формальный язык алгоритмов, а затем перевод алгоритма на формальный язык, понятный ЭВМ – машинный язык. Машинный язык – формальный язык для описания программ решения задачи, содержание и правила которого реализуются аппаратными средствами конкретной ЭВМ. Программа, составленная на машинном языке, содержит вполне определённые команды для выполнения каждой операции. В машинном 7 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. языке команды представляются цифровыми кодами (в большинстве ЭВМ двоичными) [5]. Иначе говоря, только машинный код воспринимается вычислительными устройствами, как инструкция для выполнения операций, однако программировать на таком языке достаточно непросто. Для удобства записи алгоритмов были созданы различные языки программирования. Язык программирования – формальный язык для описания данных (информации) и алгоритма (программы) их обработки на ЭВМ [5]. Строго говоря, машинный язык тоже является языком программирования. Более подробно классификация языков программирования будет рассмотрена в третьей главе. Принято различать языки программирования низкого уровня и языки программирования высокого уровня. Создатель языка программирования С++ Бьёрн Страуструп определяет различие низкоуровневых и высокоуровневых языков программирования, исходя из задач: «Язык программирования решает две взаимосвязанные задачи: позволяет программисту записать подлежащие выполнению действия и формирует понятия, которыми программист оперирует, размышляя о своей задаче. Первой цели идеально отвечает язык, который очень «близок машине». Тогда со всеми ее основными «сущностями» можно просто и эффективно работать на этом языке, причем делая это очевидным для программиста способом. Второй цели идеально отвечает язык, который настолько «близок к поставленной задаче», что на нем непосредственно и точно выражаются понятия, используемые в решении задачи» [31]. Таким образом, языки программирования, близкие к машинному языку, называются низкоуровневыми, а, чем ближе язык программирования к естественному языку, на котором описана задача, тем более высокого уровня этот язык. К языкам низкого уровня обычно относят ассемблер, который позволяет записывать числовые команды процессора с помощью специальных ключевых слов. Как уже говорилось выше, ЭВМ понимает только те команды, которые написаны на машинном языке, поэтому возникла необходимость в переводе (трансляции) программного кода, написанного на языке программирования, в машинный код. Трансляция – преобразование программы, представленной на одном языке программирования, в программу на другом языке и в определенном смысле равносильную первой. 8 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Транслятор – программа или техническое средство, выполняющие трансляцию программы (ГОСТ 19781-90 [7]). Выделяют две разновидности трансляторов в машинный код: компиляторы и интерпретаторы. Транслятор, который преобразует программы в машинный язык, принимаемый и исполняемый непосредственно процессором, называется компилятором [26]. Следует отметить, что компиляторы обычно переводят код программы на машинный язык целиком. С одной стороны, такой подход к трансляции ускоряет работу программы, с другой – увеличивает время на трансляцию и усложняет нахождение ошибок в исполняемой программе. Интерпретатор – вид транслятора, осуществляющего пооператорную (покомандную) обработку и выполнение исходной программы или запроса (в отличие от компилятора, транслирующего всю программу без её выполнения) [22]. Очевидно, что использование интерпретатора замедляет работу программы во время её исполнения, однако, обнаружить ошибку при таком подходе значительно легче, поскольку мы будем точно знать, какой именно оператор привёл к ошибке исполнения программы. Существуют трансляторы смешанного типа, которые позволяют сначала получать промежуточный код низкого уровня (байт-код) с помощью компилятора. Затем полученный код на промежуточном языке исполняется интерпретатором, который обычно называют виртуальной машинной. Такой подход даёт преимущества в скорости и эффективности, по сравнению с чистой интерпретацией, и имеет место во многих современных языках программирования: Java, языках платформы .NET, Python и других. В традиционной модели выполнения программ на языке Python, которая представлена на рисунке 1.2 [18], исходный текст, который вводится программистом, транслируется в байт-код, который затем исполняется виртуальной машиной Python. Исходный текст автоматически компилируется и затем интерпретируется байт-код. 9 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Рисунок 1.2 Традиционная модель выполнения программ на языке Python. Основные определения, рассмотренные выше, помогают лучше понимать, что такое «высокоуровневый интерпретируемый язык программирования» Python, и это позволит иметь представление о том, что происходит с кодом, который вы напишите и выполните с помощью интерпретатора Python. Нераскрытым остался только вопрос о динамической типизации, который будет рассмотрен далее в пункте 1.1. Для написания программного кода используется обычный текстовый редактор без автоматического форматирования текста или специальная интегрированная среда разработки (integrated development environment, IDE), которая обеспечивает редактор кода, подсветку синтаксиса, удобный вызов компилятора (интерпретатора), средства отладки и другие инструменты, значительно упрощающие написание кода и сборку итоговых файлов. В установочный пакет Python уже включена свободная среда разработки IDLE, которую мы и будем использовать для изучения основ программирования. Последнюю версию Python можно скачать с официального сайта языка, который находится по адресу: http://python.org. 1.1 Переменные, базовые типы данных, выражения, базовые операто- ры Интерпретатор Python может работать в двух режимах: в интерактивном режиме и в режиме выполнения скрипта. Интерактивный режим предназначен для построчного выполнения введённых команд. Интерактивный режим для ввода команды предлагает строку приглашения, которая начинается символом «>>>» или «…» при продолжении ввода. Обычно изучение интерактивного режима начинают с использования Python в качестве калькулятора. По нажатию клавиши Enter выводится результат введённого выражения. Сразу отметим, что синтаксис различных версий Python отличается, поэтому в дальнейшем все примеры мы будем рассматривать для версии 3. >>> 2+2 10 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. 4 Данные, используемые в программе, хранятся в ячейках памяти. Интерпретатор переводит введённую команду «2+2» на машинный код и тут же выполняет его. Машинный код для каждого введённого числа выделяет память и помещает значения в выделенные ячейки, затем осуществляет операцию сложения путём вызова соответствующей команды процессора, указывая в качестве параметров адреса, в которых хранятся числа. Зачастую возникает необходимость повторно использовать значения данных, хранимых в памяти. Для решения этой задачи существует механизм связывания адреса ячейки памяти с некоторым именем. Переменная в программировании – имя или идентификатор, с которым связано определённое значение, к которому можно обратиться, используя это имя. Обычно переменной называют именованную область памяти, в которой хранится значение используемых данных. В различных языках программирования переменная может представлять собой либо именованную ячейку памяти, либо ссылку на ячейку памяти, причём для данных различных типов переменная может определяться по-разному. От того, как связана переменная с данными в памяти, часто зависит стиль программирования. В Python переменная представляет собой ссылку на ячейку памяти, а имя переменной может включать любые буквы, цифры и знак подчёркивания и не может начинаться с цифры. Следует отметить, что в Python, как и в других языках программирования, есть зарезервированные слова, которые так же не могут быть именами переменных. Данные, с которыми работает программа, могут иметь различные типы, которые определяют, какие значения могут принимать эти данные, какие операции можно производить над данными и каким образом хранить в памяти и обращаться к ним. Тип данных – характеристика набора данных, которая определяет: диапазон возможных значений данных из набора; допустимые операции, которые можно выполнять над этими значениями; способ хранения этих значений в памяти. Различают: простые типы данных: целые, действительные числа и др.; составные типы данных: массивы, файлы и др. [6]. Для однозначного определения типа данных для переменных на каждом шаге алгоритма программная среда выполняет контроль типов. Если контроль типов осуществляется на этапе компиляции, то говорят о статической типизации, а если на этапе выполнения – о 11 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. динамической типизации. При статической типизации тип переменной определяется один раз и не может быть изменён без явного приведения к другому типу с помощью специальных команд. При динамической типизации тип переменной определяется на каждом шаге и может быть неявно изменён. Это даёт большую гибкость при использовании переменных в коде, однако увеличивает вероятность возникновения ошибок во время выполнения программы, если не использовать специальных методик программирования. В Python применяется динамическая типизация. Такой подход к типизации приводит к тому, что переменные всех типов в Python являются ссылками на ячейку памяти. Это справедливо даже для базовых типов данных. Базовыми типами данных во многих языках программирования считаются числовые типы (целые и дробные числа), строковые типы (символы и строки) и логический (булев) тип. В Python базовыми типами являются следующие: int (целые числа), long (большие целые числа), float (вещественные числа или числа с плавающей запятой), str (строки), bool (логический тип). Кроме того Python поддерживает комплексные числа. Во многих языках программирования выделяют символьный тип данных (character), однако в Python символ – это строка, состоящая из одного символа. От типа переменной зависит, сколько памяти будет выделено для хранения значения переменной. В разных версиях Python эти значения могут различаться, например, в 3 версии тип long объединён с типом int. Следует понимать, что все числа хранятся в двоичном коде, то есть в виде единиц и нулей, поэтому не все десятичные числа могут иметь сопоставимое представление в такой записи, что ведёт к неизбежным ошибкам при выполнении вычислений. >>> 0.1+0.1+0.1-0.3 5.551115123125783e-17 Подробное описание, почему это происходит и как избежать ошибок в этом случае, можно найти в официальной документации Python: http://docs.python.org. Многие примеры в первой главе взяты с этого сайта. В Python определены следующие операции с числами: + (сложение), – (вычитание), * (умножение), / (деление), // (целочисленное деление), % (остаток от деления), ** (возведение в степень). Комментарии в Python обозначаются знаком #. >>> # Это комментарий ... 2+2 12 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. 4 >>> 4 >>> 5.0 >>> 1.6 >>> ... 2 >>> -3 >>> 8 2+2 # а вот комментарий на одной строке с кодом (50-5*6)/4 8/5 # При делении целых чисел дробные части не теряются # При целочисленном делении в результате отброшена дробная часть: 7//3 7//-3 2**3 # возведение в степень Операторами называют специальные символы (или последовательности символов), обозначающие некоторые операции. Например, «+» – это оператор сложения. Объекты, с которыми производятся операции, называются операндами. Оператор присваивания обозначается символом «=». Он используется для присваивания переменной какого-либо значения: >>> width = 20 >>> height = 5*9 >>> width * height 900 Те элементарные команды, которые мы выполняем в каждой строчке, называются выражениями. Выражение – это последовательность синтаксических единиц, описывающая элементарное действие на языке программирования [39]. Например, width = 20 является выражением, в котором описывается оператор присваивания. Строки в Python записываются в одинарных, двойных или тройных кавычках: >>> "Строка с 'одинарными' кавычками внутри" "Строка с 'одинарными' кавычками внутри" В данном случае одинарные кавычки не являются разделителями строки, поскольку они являются частью строки, выделенной двойными кавычками. 13 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. К строкам применяются не только операции, но и функции. Понятие функции будет подробно раскрыто в пункте 1.7. Пока достаточно понимать, что функция по заданным параметрам в скобках возвращает некоторое значение. Функция len(s) возвращает длину строки s, оператор + складывает две строки, оператор * повторяет строку заданное число раз. >>> word = 'Pyth' + 'on' >>> word 'Python' >>> '<' + word*3 + '>' '' >>> len(word) 6 Поскольку строка является последовательностью символов, то подстроку данной строки можно получать с помощью срезов (slice) и операции взятия индекса для выделения подстроки длиной 1 символ. >>> word[0] 'P' >>> word[2:4] 'th' >>> word[:2] # Первые два символа 'Py' >>> word[2:] # Всё, исключая первые два символа 'thon' >>> word[-2] # Второй символ с конца строки 'о' >>> word[1:5:2] # Подстрока с символами от 1 до 4 с шагом 2. 'yh' Строка – это неизменяемая последовательность в Python, поэтому нижеприведённый код выдаст ошибку. >>> word[2]='p' # Ошибка Error! Python поддерживает числа и строки произвольной длины (длина ограничена лишь физическим объёмом доступной памяти). Пример, рассмотренный чуть выше, представляет собой вполне завершённый алгоритм: >>> width = 20 >>> height = 5*9 >>> width * height 14 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. 900 Все алгоритмы строятся по одним и тем же принципам. «Архитектурными элементами» при этом являются алгоритмические структуры, а «строительным материалом» – блоки действий и выражения. Алгоритмическая структура «следование» или линейный алгоритм – предполагает последовательное выполнение действий одно за другим. В общем случае последовательно выполняются блоки действий, которые могут включать в себя другие алгоритмические структуры или состоять из одного или нескольких действий. Рассмотренный пример представляет собой линейный алгоритм. Каждую алгоритмическую структуру мы будем записывать на двух формальных языках: на языке блок-схем и в псевдокоде. На языке блок-схем алгоритм записывается с помощью графических фигур, которые изображают шаг алгоритма, соединённых стрелками, определяющими дальнейшее движение алгоритма. Скруглённый прямоугольник изображает начало и конец алгоритма, прямоугольник изображает блок действий, наклонный параллелограмм – ввод-вывод данных, ромб – условный переход. Существуют и другие элементы блок-схем, которые применяются для изображения более сложных алгоритмических структур. Блок-схема фрагмента линейного алгоритма представлена на рисунке 1.3. Рисунок 1.3. Блок-схема алгоритмической структуры «следование». Псевдокод – компактный язык описания алгоритмов, который содержит ключевые слова, необходимые для понимания смысла, но опускает подробности реализации на конкретном языке программирования. 15 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. В псевдокоде линейный алгоритм представляет собой следующую запись: начало Блок действий Блок действий … Блок действий конец Какие значения может принимать булевский тип данных, операции для переменных этого типа и каково применение выражений в алгоритмических структурах, описано в пункте 1.2. 1.2 Логические выражения Переменные логического (булева) типа данных могут принимать только два значения: истина (True) и ложь (False). Эти значения называют логическими значениями. Логические значения получаются в результате логических операций и вычисления логических выражений. Логическими выражениями называют выражения, результатом которых являются логические значения. В Python применяются следующие основные логические операторы, результат которых есть логическое значение: операторы сравнения (больше (>), меньше (<), равно (==), больше или равно (>=), меньше или равно (<=), не равно (!=)), оператор and (логическое «и»), оператор or (логическое «или»), оператор not (логическое «не» – отрицание), оператор in (проверка принадлежности значения элемента множеству), оператор is (проверка, что две переменные ссылаются на один и тот же объект в памяти). В отличие от большинства популярных языков программирования, в Python реализована поддержка логических выражений вида «a < x < b», что эквивалентно следующему выражению: «(x>a) and (x>> num1 = 34 # Присваиваем значения числовым переменным num1 и num2. >>> num2 = 8.5 >>> num1 > 12 and num2 != 12 # Целые числа можно сравнить с вещественными. True >>> num1 == 34 and num2 >= 8 True # Логическое «и» даёт истину только тогда, когда оба операнда истинны. >>> num1 != 34 and num2 != 12 False >>> num1 != 34 or num2 != 12 16 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. True # Логическое «или» даёт истину, когда хотя бы один операнд – истина. >>> num1 < 1 or num2 > 9.6 False # Логическое «или» даёт ложь только тогда, когда оба операнда ложны. >>> str1 = "a" # Операторы сравнения можно применять к строкам. >>> str2 = "b" >>> str1 < "c" and str2 != "a" True Логические выражения очень часто используются в программировании для задания альтернативных путей выполнения алгоритма. Базовой алгоритмической структурой для задания условных переходов является «ветвление». Алгоритмическая структура «ветвление» или условный оператор – предполагает выполнение одного или нескольких различных блоков действий в зависимости от значения некоторого условия – логического выражения. Запишем условный оператор, который по-другому называют «If-then-else», на языке псевдокода: Если (условие), то блок_действий_1 иначе блок_действий_2 Приведённый псевдокод необходимо понимать следующим образом: если условие истинно, то следует выполнить «блок_действий_1», иначе, если условие ложно, следует выполнить «блок_действий_2». Часть алгоритма, начинающаяся со слова «иначе», необязательна. В случае если она отсутствует, то алгоритм продолжит свою работу дальше. Алгоритмическую структуру без «иначе» часто называют неполным ветвлением. На языке блок схем полное и неполное ветвления представлены на рисунке 1.4. 17 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Рисунок 1.4. Блок-схемы полного и неполного ветвлений. В Python синтаксис условного оператора рассмотрим на примере: if x>0: print('Значение x – положительное число') else: print('Значение x – отрицательное число или ноль') В примере для вывода данных на экран используется функция print. Следует отметить, что в приведённом примере мы не указывали строку приглашение. Это связано с тем, что алгоритм можно писать и запускать без использования интерактивного режима Python. Для этого надо создать файл с расширением «py» (сокращение от Python) или «pyw» в MS Windows (для запуска по двойному щелчку), затем запустить этот файл с помощью интерпретатора Python. В среде IDLE создать программу в режиме написания скрипта можно с помощью пункта меню File > New Window. Запуск алгоритма осуществляется по нажатию клавиши F5. Особенностью языка программирования Python является несколько необычный синтаксис. Для выделения блоков действий не применяется специальных символов, которые обозначают начало и конец блока. Блок действий в Python выделяется посредством отступов от начала строки с помощью пробелов или знака табуляции. Все строки с одинаковым отступом составляют блок действий. Как только появляется строчка с другим отступом, интерпретатор Python понимает, что это уже другой блок. Как можно заметить, в примере условие предоставляет выбор двух альтернатив. Если альтернатив больше, то используется расширенный условный оператор. 18 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. if x>0: print('Значение x – положительное число') elif x==0: print('Значение x равно нулю') else: print('Значение x – отрицательное число') Ключевое слово elif (сокращение от «else if») используется для расширения условного оператора для описания более двух альтернатив. В других языках программирования для подобного расширения используется алгоритмическая структура «переключатель» или оператор выбора (switch-case). Существенным отличием переключателя от условного оператора является то, что для выбора альтернативы используется не логическое условие, а конкретное значение некоторого выражения. Псевдокод оператора выбора можно представить следующим образом: switch (выражение) case значение_выражения_1: блок_действий_1 break case значение_выражения_2: блок_действий_2 break … default: блок_действий_по_умолчанию Следует понимать, что любой блок действий может включать не только простые выражения, но и другие условные операторы и другие алгоритмические структуры. 1.3 Циклы и операторы циклов Часто в программировании возникает необходимость повторить один и тот же участок кода заданное число раз или в зависимости от выполнения какого-либо условия. Для этого используется алгоритмическая структура «цикл». Существует несколько разновидностей циклов: цикл с предусловием, цикл с постусловием, цикл с параметром. Цикл с предусловием (while-do) – подразумевает повторение блока действий (тела цикла), пока выполняется условие входа в цикл. В псевдокоде цикл с предусловием записывается следующим образом: пока (условие_входа) выполнять тело_цикла 19 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. конец_цикла Цикл с постусловием (do-until) – подразумевает повторение тела цикла до тех пор, пока не будет выполнено условие выхода из цикла. В псевдокоде цикл с постусловием записывается следующим образом: выполнять тело_цикла пока-не (условие_выхода) Ключевое отличие цикла с постусловием в том, что здесь тело цикла обязательно выполняется хотя бы один раз, в отличие от других разновидностей циклов, в которых тело цикла может не выполниться ни разу. Важно осознавать, что в теле циклов с предусловием и с постусловием необходимо предусмотреть изменение значений хотя бы одной переменной из тех, которые присутствуют в логическом выражении – условии входа или выхода из цикла. Это необходимо делать для того, чтобы избежать бесконечного выполнения тела цикла без возможности продолжить алгоритм и завершить программу. Цикл с параметром (for-do, for-in) или со счётчиком – подразумевает повторение тела цикла, пока параметр не примет все значения из некоторого множества, заданного перечислением или совокупностью начального значения, условия входа и правила перебора элементов. В псевдокоде цикл с параметром, если множество задаётся перечислением, записывается следующим образом: Для (параметр из множество_значений) выполнять тело_цикла конец_цикла Если же множество задано начальным значением и условием входа, то правило перебора элементов обычно определяется размером шага от начального значения до конечного во множестве и псевдокод записывается так: Для (параметр = начальное_значение; конечное_значение; шаг) выполнять тело_цикла конец_цикла На языке блок-схем некоторые циклические алгоритмы представлены на рисунке 1.5. 20 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. В Python реализованы цикл с предусловием и цикл с параметром. Рассмотрим синтаксис этих циклов на общеизвестных примерах. Цикл с предусловием реализован в Python с помощью оператора while. # Ряд Фибоначчи: # сумма двух элементов определяет следующий элемент a = 0 b = 1 while b < 10: print(b) с = a # Временная переменная хранения значения переменной a a = b b = c+b # Будет выведена последовательность на экран: 1 1 2 3 5 8 Рисунок 1.5. Блок-схемы циклов с предусловием и с постусловием. Пример цикла с параметром включает последовательность строк. Подробности о последовательностях изложены в пункте 1.5. # Выведем на экран длины нескольких строк: a = ['cat', 'window', 'defenestrate'] for x in a: print(x, len(x)) # Будут выведены строки: cat 3, window 6, defenestrate 12. 21 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. В рассмотренном примере для каждого элемента x в последовательности a выводятся на экран значение элемента – строка – и длина этой строки, полученная с помощью функции len. Если требуется выполнить цикл заданное число раз, то используют разновидность цикла с параметром – цикл с итератором или со счётчиком, который позволяет перебирать элементы от 0 до заданного (n-1), где n – это количество итераций цикла. В Python для задания цикла со счётчиком используют функцию range(n), которая возвращает последовательность от 0 до (n-1). Примером реализации цикла со счетчиком является следующий код: >>> a = ['У', 'Марии', 'есть', 'маленькая', 'овечка'] >>> for i in range(len(a)): ... print(i, a[i]) ... 0 У 1 Марии 2 есть 3 маленькая 4 овечка При рассмотрении цикла с постусловием упоминалось об опасности возникновения бесконечного цикла. Для досрочного выхода из цикла или перехода к следующей итерации в Python, как и в других популярных языках программирования, используются специальные операторы. Оператор break прерывает выполнение самого ближайшего вложенного цикла for или while. Оператор continue продолжает выполнение цикла со следующей итерации. Приведём пример использования оператора continue, для этого немного изменим предыдущий пример: a = ['У', 'Марии', 'есть', 'маленькая', 'овечка'] for i in range(len(a)): if len(a[i])>5: continue else: print(i, a[i]) # Алгоритм выведет следующие строки длиной не больше 5 0 У 1 Марии 22 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. 2 есть В теле цикла с параметром i, который на каждой итерации последовательно принимает значения от 0 до 4 (5 значений), содержится условный оператор, выполняющий переход к следующей итерации, если длина текущей строки больше пяти, или, в противном случае, выводит номер итерации (элемента в последовательности) и значение текущей строки на экран. 1.4 Системы счисления, побитовые операции, классические задачи программирования Числа в языках программирования записываются не только в десятичной системе счисления, но и в двоичной, восьмеричной и шестнадцатеричной системах счисления. Это естественно связано с тем, как хранятся числа в памяти ЭВМ. >>> 14600926 # десятичное число 14600926 >>> 0b110111101100101011011110 # двоичное число 14600926 >>> 0о67545336 # восьмеричное число 14600926 >>> 0xDECADE # шестнадцатеричное число 14600926 Двоичные числа записываются с префиксом 0b, восьмеричные – c префиксом 0o и шестнадцатеричные – с префиксом 0x. Все представления чисел в различных системах счисления, как мы видим в примере, идентичны десятичному представлению числа. Для получения строкового представления чисел в системах счисления, отличных от десятичной, в Python используются функции: bin(i) – двоичная система счисления, oct(i) – восьмеричная система счисления, hex(i) – шестнадцатеричная система счисления. Функция int(s, base) – наоборот, позволяет получить целое число из строки s с основанием системы счисления base. Помимо обычных операций над числами во многих языках программирования используются битовые операторы, которые могут пригодиться, когда вы будете иметь дело, например, с сетевыми пакетами или упакованными двоичными данными [18]. Битовые операторы – операторы, применяемые к двоичным числам и необходимые для выполнения операций компьютерной арифметики. 23 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. К битовым операторам относят | (OR – ИЛИ), ^ (XOR – исключающее ИЛИ), & (AND – И), << (побитовый сдвиг влево), >> (побитовый сдвиг вправо), –i (инвертирование битов числа i). Применение битовых операторов в языках высокого уровня не так актуально, как в более низкоуровневых языках (таких как С), которые работают с памятью и устройствами напрямую через указание адреса. Например, в Python двоичное представление числа и битовые операторы удобно применять для хранения множества флагов (переменных, принимающих лишь два значения – 1 (истина) и 0 (ложь)) в одной числовой переменной, тогда как для вычислений и адресации используются более удобные для программиста методы. Применение битовых операторов рассмотрим на примере: >>> х = 1 # 0001 >>> х << 2 # Сдвиг влево на 2 бита: 0100 4 >>> х | 2 # Побитовое ИЛИ: 0001|0010 == 0011 3 >>> х & 1 # Побитовое И: 0001&0001 == 0001 1 На умении применять битовые операторы основаны некоторые классические задачи программирования. Рассмотрим одну из таких задач на примере. Задача обмена значений двух переменных обычно решается путём использования временной переменной того же типа, которая нужна для того, чтобы временно запомнить значение одной переменной. Пример такого подхода легко продемонстрировать с помощью кода на Python: a = b = tmp a = b = 5 6 = a b tmp Использование битового оператора XOR позволяет решить эту задачу без использо- вания временной переменной. Это достигается путём использования комбинации выражений и свойства операции XOR, результат применения которой к одинаковым значениям даёт значение «ноль». Приведем реализацию алгоритма на Python: a=3 b=4 a = b = a = # 0011 # 0100 a^b # 0011 XOR 0100 = 0111 b^a # 0100 XOR 0111 = 0011 a^b # 0111 XOR 0011 = 0100 24 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Операция XOR часто используется в криптографических алгоритмах. 1.5 Массивы, сортировка массива, поиск элемента, матрицы Массивом в программировании называют именованную упорядоченную совокупность объектов обычно (но необязательно) одного типа. Доступ к элементам массива осуществляется путём указания индекса – номера элемента в совокупности. Различают одномерные массивы и многомерные (двумерные, трехмерные и так далее). Массив называют двумерным, если каждый элемент массива является одномерным массивом. Аналогично можно расширить это определение на любое количество измерений. Доступ к элементам двумерного массива осуществляется путём указания двух индексов. В Python массивы представлены несколькими базовыми составными типами данных, общее название которых – коллекции. Коллекции подразделяются на последовательности, отображения (ассоциативные массивы) и множества. Некоторые из этих типов данных будут рассмотрены в главе 2, а сейчас мы рассмотрим наиболее близкие к понятию массива – последовательности. Последовательность в Python – это упорядоченная коллекция других объектов. Последовательности подразделяются на изменяемые и неизменяемые. К неизменяемым последовательностям относят уже известный нам тип данных – строка – последовательность строк длиной в один символ. Другой неизменяемой последовательностью является кортеж (tuple). Элементом кортежа может быть объект любого типа данных. К изменяемым последовательностям относят список (list). Список в Python — это изменяемая неограниченная последовательность ссылок на объекты одного или разных типов. К последовательностям применяются те же операторы, что и рассмотренные выше применительно к строкам. Рассмотрим основные операторы и функции на примере [28]. >>> a = ['spam', 'eggs', 100, 1234] >>> a # Списки определяются в квадратных скобках через запятую ['spam', 'eggs', 100, 1234] >>> len(a) # К спискам применима функция len 4 >>> a[0] # Оператор взятия индекса 'spam' >>> a[3] 1234 >>> a[-2] 25 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. 100 >>> a[1:-1] # Для последовательностей действует оператор среза ['eggs', 100] >>> a[:2] + ['bacon', 2*2] # Объединение списков ['spam', 'eggs', 'bacon', 4] >>> 3*a[:3] + ['Boe!'] ['spam', 'eggs', 100, 'spam', 'eggs', 100, 'spam', 'eggs', 100, 'Boe!'] >>> a ['spam', 'eggs', 100, 1234] >>> a[2] = a[2] + 23 # Элементы списка можно изменять. >>> a ['spam', 'eggs', 123, 1234] >>> b = [a, 2, 3] # Cписок может включать другие списки [['spam', 'eggs', 123, 1234], 2, 3] >>> b[0].append('extra') # К спискам можно применять методы >>> b [['spam', 'eggs', 123, 1234, 'extra'], 2, 3] >>> a ['spam', 'eggs', 123, 1234, 'extra'] Список a тоже изменился, поскольку список состоит из ссылок на объекты. Удалять элементы или срезы из последовательностей можно с помощью оператора del. >>> del a[4] >>> a ['spam', 'eggs', 123, 1234] Отличия кортежа от списка состоят в том, что кортежи определяются в круглых скобках и элементы кортежа неизменны после определения, то есть невозможно использовать операторы присваивания или функции и методы добавления, изменения и удаления элементов. Применять кортежи следует тогда, когда существенной является неизменяемость последовательности. Кортежи обеспечивают своего рода ограничение целостности, что может оказаться полезным в крупных программах с большим количеством независимых компонентов [18]. Кроме того кортежи необходимы для передачи параметров и возврата значений в некоторых функциях. Все элементы данных в языке Python являются объектами (называемых также экземплярами) определенных типов данных (называемых также классами). Мы будем использовать термины тип данных и класс как взаимозаменяемые. Одно из основных отличий между объектом и простым элементом данных в некоторых других языках программирования (например, встроенные числовые типы в C++ или Java) состоит в том, что объект может обладать методами. В сущности, метод – это обычная функция, кото- 26 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. рая вызывается в контексте конкретного объекта. Например, тип list имеет метод append(), с помощью которого можно добавить новый объект в список [30]. Подробнее понятие объекта и объектно-ориентированный подход в программировании будет рассмотрен в главе 3. Методы, применяемые к объектам-спискам, часто повторяют результат операторов с одним важным отличием – при применении методов не создаётся новых объектов в памяти, а изменяется текущий объект, для которого вызывается метод. Основные методы, применяемые к спискам (в данном случае к списку lst): lst.append(x) – добавляет элемент x к объекту lst; lst.extend(lst2) – добавляет последовательность lst2 в конец списка lst; lst.count(x) – возвращает количество элементов x в списке; lst.index(x) – возвращает позицию первого вхождения элемента x в список; lst.insert(i,x) — вставка элемента или списка x в позицию i списка lst; lst.pop(i) – извлечение элемента, находящегося в позиции i, при этом элемент удаляется из списка (если аргумент не указан, то извлекается последний элемент списка); lst.reverse() – изменение порядка следования элементов списка на обратный; lst.sort() – сортировка списка в лексико-графическом порядке. Одной из наиболее часто выполняемых задач в программировании является сортировка массива по какому-либо признаку или поиск элемента в массиве. Под сортировкой понимают процедуру, в результате которой изменяется исходный порядок следования данных на новый порядок, отвечающий требованию возрастания или убывания значений элементов исходного массива по какому-либо признаку. Для эффективного выполнения этих задач разрабатываются и совершенствуются алгоритмы, некоторые из которых мы рассмотрим на примерах [37]. В Python метод sort() написан на более низкоуровневом языке C, что повышает быстродействие. Алгоритм, применяемый в стандартном методе, называется Timsort. Важным показателем в теории алгоритмов является вычислительная сложность алгоритма, которая обычно записывается с помощью O-символики. Обычно сложность показывает, сколько элементарных операций или итераций необходимо выполнить в циклах в зависимости от количества элементов в массиве или других параметров, для того чтобы получить решение задачи с помощью данного алгоритма. Вычислительная сложность алгоритма пропорционально влияет на время его выполнения. Вторым параметром, по которому выбирают тот или иной алгоритм для решения задачи, является объём необходимой памяти. Таким образом, алгоритм выбирают путём сравнения по двум критериям — вычислительная сложность алгоритма и объём памяти, требуемый для хранения данных во время работы алгоритма. 27 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Рассмотрим один из алгоритмов сортировки массива – алгоритм сортировки «методом пузырька» по возрастанию. Псевдокод этого метода выглядит следующим образом: ввод n, A # n – число элементов массива A для (m = n-1; m>0; -1) выполнять для (i = 0; i < m; 1) выполнять если (A[i] > A[i+1]) то X=A[i] A[i]= A[i+1] A[i+1]= X конец_цикла конец_цикла вывод A Алгоритм сортировки «методом пузырька» основывается на попарном сравнении двух соседних элементов, при этом, если следующий элемент массива оказывается меньше текущего, то значения элементов обмениваются местами, при этом наибольшее значение оказывается в конце массива («всплывший пузырёк»). При каждом проходе количество итераций в цикле уменьшается на единицу, для того чтобы не осуществлять повторное сравнение уже «всплывших пузырьков». Алгоритм сортировки «методом пузырька» относят к группе алгоритмов сортировки обменом. Сложность алгоритма сортировки «методом пузырька» составляет O(n2), где n – количество элементов, а запись O(n2) можно интерпретировать следующим образом: при увеличении количества элементов в два раза время, необходимое на сортировку, увеличивается в (22 = 4) раз с точностью до некоторой константы. Аналогичная сложность у алгоритма сортировки выбором. Смысл алгоритма сортировки выбором заключается в том, что находится минимальный (или максимальный, если требуется сортировка по убыванию) элемент и вставляется в начало списка. Затем среди оставшихся элементов находится минимальный и вставляется во вторую позицию и так далее. Приведём код алгоритма сортировки выбором на Python: s = [3,2,5,1,6,0,4] l = len(s) # длина списка for k in range(l - 1): min_ix = k # min_ix – индекс минимального значения i = k + 1 # i – индекс начала поиска минимального значения while i < l: # поиск минимального значения if s[i] < s[min_ix]: min_ix = i i = i + 1 tmp = s[k] # вставляем минимальное значение s[k] = s[min_ix] 28 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. s[min_ix] = tmp Существует класс алгоритмов быстрой сортировки, каждый из которых имеет свои преимущества и недостатки. Сложность подобных алгоритмов обычно составляет в среднем O(n log n). К таким алгоритмам относят, в том числе алгоритм Timsort, применяемый в методе sort для последовательностей в Python. Еще один важный класс алгоритмов – алгоритмы поиска элемента в массиве. Выделяют алгоритмы поиска элементов в упорядоченном массиве и в неупорядоченном. В неупорядоченном массиве осуществлять поиск элемента позволяет простейший алгоритм линейного поиска. Этот алгоритм часто используется в других более сложных алгоритмах для нахождения некоторого элемента по известному ключу. Приведём псевдокод алгоритма линейного поиска: ввод N, A # длина массива и массив ввод Key # искомое значение для (i = 0; i < N; 1) выполнять если (A[i] == Key) то вывод A[i] break конец_цикла Если массив упорядочен, то для поиска элемента часто применяют алгоритм двоичного поиска. Принцип работы этого алгоритма состоит в последовательном извлечении значения элемента, индекс которого находится в середине выбранного множества элементов. Затем этот элемент сравнивается с ключом (искомым значением), и, в зависимости от результатов сравнения, выбирается множество элементов справа или слева от середины, после чего алгоритм повторяется для выбранного множества, до тех пор пока значение в середине множества не будет равно искомому значению. Таким образом, область поиска на каждом шаге сокращается приблизительно вдвое. Реализацию алгоритма двоичного поиска в Python рассмотрим на примере: li = [1,4,5,7,8,9] # отсортированная последовательность Key = 8 # искомое значение i = 0 # начальный индекс области поиска j = len(li)-1 # конечный индекс области поиска m = int(j/2) # индекс середины области поиска # функция int() берёт целую часть числа while li[m] != Key and i < j: # цикл по элементам области поиска if x > li[m]: # если искомое значение больше середины, то i = m+1 # изменяем начало области поиска else: j = m-1 # иначе изменяем конец области поиска m = int((i+j)/2) # вычисляем новую середину области поиска 29 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. if i > j: print('Элемент не найден') else: print('Индекс элемента: ', m) Многие вычислительные задачи, которые стоят перед разработчиками программных продуктов, требуют умения легко работать с двумерными массивами данных. В случае числовых данных речь идёт о матрицах — прямоугольных таблицах чисел, имеющих n строк и m столбцов. Матрицы широко применяются в экономических расчётах, а также в других прикладных задачах, применяющих математический аппарат, таких как создание криптоалгоритмов, задачи оптимизации, реализация методов искусственного интеллекта, моделирование процессов, разработка игр и другие. Очевидно, что реализовать матрицы в Python можно с помощью вложенных списков, однако для более удобной работы с матрицами существует специальная библиотека numpy. Для известных примеров обработки матриц мы будем использовать вложенные списки, в случае необходимости, дополнительные модули Python предлагается изучить самостоятельно. Прежде чем написать пример, рассмотрим ещё одну синтаксическую конструкцию, которая достаточно часто встречается в языках программирования – это составной оператор присваивания, смысл которого в следующем: вместо a=a+1 можно записать a+=1, или вместо b=b*c можно записать b*=c, причём вместо знаков + и * можно использовать, как правило, любой односимвольный оператор, в том числе и побитовые операторы. Еще одной часто встречаемой синтаксической конструкцией при работе с циклами является оператор приращения (инкремент), который позволяет вместо a=a+1 записать a++ или ++a, и оператор уменьшения (декремент) – a-- или --a. Разница между выражениями a++ и ++a состоит в том, что в первом случае значение операнда а изменяется после его использованием в соответствующем выражении, а во втором случае – перед его использованием. В Python инкремент и декремент не используется. В качестве примера рассмотрим задачу подсчёта суммы, среднего арифметического всех элементов матрицы размерностью 3x3 и нахождения максимальных элементов по строкам. # Создадим матрицу размерностью 3x3 a=[[1, 2, 3], [0, 4, 5], [6, 3, 1]] n = len(a) # Число строк m = len(a[0]) # Число столбцов Sum = 0 # Задаем начальное значение суммы Avg = 0 # Задаем начальное значение среднего арифметического 30 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. max_row = [] # Список для хранения максимальных значений по строкам for i in range(n): max_elem = a[i][0] for j in range(m): Sum+=a[i][j] if (j!=0) and (a[i][j]>max_elem): max_elem = a[i][j] max_row.append(max_elem) Avg = Sum/(n*m) print('Сумма: ', Sum) print('Среднее арифметическое: ', Avg) print('Максимальные значения по строкам: ', max_row) Для решения поставленной задачи используется цикл по стокам, в теле которого есть вложенный цикл, осуществляющий перебор по столбцам. Такой подход чаще всего используется для того, чтобы последовательно перебирать элементы матрицы. Обращение к конкретному элементу матрицы осуществляется путём указания в квадратных скобках сначала индекса строки, а затем – индекса столбца, например, a[3][2] – это элемент матрицы или двумерного массива, расположенный в третьей строке и втором столбце. 1.6 Строки Со строковым типом данных мы уже познакомились в пункте 1.1. Одним из распространенных типов задач программирования является обработка строк, поэтому в языках программирования обычно предусмотрены широкие возможности для решения подобных задач. Значимость таких задач очевидна, если вспомнить, что наиболее удобный для человека формат хранения, ввода и вывода данных – это текст. Кроме того, сам код программы является текстом, который преобразуется транслятором в байт-код и в машинный код путём синтаксического разбора текста исходного кода. Как уже упоминалось ранее, в Python строкой считается последовательность символов, заключённых в одинарные, двойные или тройные кавычки (применяются, когда в строке встречаются двойные и одинарные кавычки и когда необходимо ввести текст на нескольких строчках). Некоторые символы являются специфичными для языка программирования и поэтому не могут применяться в строке в «чистом» виде. Например, невозможно внутри одинарных кавычек поставить другие одинарные кавычки, поскольку первая вложенная кавычка будет восприниматься как конец строки. Для того чтобы избежать подобных ситуаций применяют так называемое экранирование символов. Обычно знак экранирования – это обратный слэш (косая черта «\»), который ставят перед тем символом, который необходимо включить в строку и который должен проигнорировать транслятор. Например, если требуется вклю- 31 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. чить в строку обратный слэш, то в программном коде необходимо указать «\\», где первый символ – знак экранирования следующего за ним. Кроме экранирования обратный слэш применяется для указания специальных символов, например, знак табуляции обозначается как «\t», а знак перевода строки – «\n». Рассмотрим несколько примеров экранирования символов. >>> str = "Строка с экранированными \"двойными\" кавычками" >>> print ('Стоимость\t1000') Стоимость 1000 Важное значение в программировании отводится удобному для человека и понятному для ЭВМ вводу и выводу данных. Зачастую дополнительной задачей при вводе или выводе данных является проверка соответствия данных какому-либо типу или формату. Этот процесс называют валидацией. Валидация позволяет избежать ошибок при работе программы и позволяет получать корректные данные для обработки. Указание формата строки реализуется с помощью механизма форматированного вывода. В Python предусмотрены средства форматированного вывода данных. Для вывода данных используется функция print() с указанием параметров и их типов и формата. Для ввода данных используется функция input(). Программа ждёт ввода данных с клавиатуры. Для указания формата строки используется оператор % с указанием слева от оператора строки с выражениями форматирования, а справа от оператора – последовательности значений, которые будут вставлены в строку. Лучше всего понять принцип форматированного вывода на примерах: >>> 'Это %d %s птичка!' % (1, 'маленькая') # Выражение форматирования Это 1 маленькая птичка! >>> print('Это {0} {1} птичка'.format(1, 'маленькая')) # Метод format даёт такой же результат Выражение форматирования %d указывает на то, что вместо него должно быть целое число, а вместо %s должна быть вставлена строка. Особенно актуальным указание формата становится для вещественных чисел: например, количество цифр после запятой можно указать с помощью следующего выражения %.3f (три цифры после запятой). Аналогичный результат мы получим, используя метод format: >>> '{0:.2f}'.format(3.1415) # 0 – порядковый номер параметра 32 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. '3.14' В Python 3 предпочтительно использование метода format для форматированного вывода. При изучении массивов в пункте 1.5 мы уже упоминали, что любой элемент в Python является объектом некоторого типа данных и, следовательно, может содержать методы – функции, позволяющие осуществлять некоторые действия над этим объектом. Строки также содержат такие методы, которые позволяют выполнять основные действия со строками. Примеры предлагается составить самостоятельно после изучения документации Python. Часто возникающей задачей при обработке текстовой информации является поиск подстроки и разбор (парсинг) строк. В решении подобных задач используются строковые методы или специализированные подключаемые библиотеки. Одним из часто используемых методов является метод split, который позволяет получить последовательность строк из исходной строки с разделителями. Приведём пример использования этого метода: >>> line = 'ааа,bbb,ccc' >>> cols = line.split(',') # разделитель запятая >>> cols ['ааа', 'bbb', 'ccc'] Для выполнения обратной операции используют метод join. При работе с текстовой информацией необходимо понимать, как она храниться в памяти ЭВМ. Очевидно, что текст также храниться в виде цифрового двоичного кода. При необходимости вывода тестовой информации на экран программа должна прочитать этот код из ячейки памяти, преобразовать его по определённым правилам в текстовый символ и только потом вывести на экран. Соответствие между двоичным числом и его символьным представлением устанавливается с помощью кодовых таблиц, которые задают кодировку текста. Кодовые таблицы различаются размером, выделяемым для кодирования одного символа, а также региональными характеристиками – языком и алфавитом используемого языка. Если в тексте используются только латинские символы, а также цифры, знаки препинания и некоторые специальные символы, то для представления символа в двоичном коде достаточно 8 бит или 1 байт. Двоичные числа длиной 8 бит позволяют закодировать 28=256 различных символов. Наиболее распространенная 8-битная кодировка – таблица ASCII кодов (American Standard Code for Information Interchange), которая включает помимо перечис33 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. ленных символов ещё и буквы национального языка, при этом строчные и прописные буквы, естественно, имеют разные двоичные коды. Для кодирования теста на многих языках обычно применяют региональные 8-битные или универсальные 16-битные кодировки. Примером 16-битной кодовой таблицы является Unicode. Наиболее часто используемые кириллические кодировки UTF-8, CP1251, KOI8-R. Для поиска подстроки в тексте и для парсинга с использованием стандартных функций и методов строки зачастую требуются достаточно сложные алгоритмы, которые трудно поддерживать и расширять, поэтому для подобных задач используют декларативный язык регулярных выражений, который позволяет задать то, что мы хотим получить одним выражением. Регулярные выражения позволяют задавать шаблоны искомых подстрок и затем обрабатывать результаты поиска. Синтаксис регулярных выражений включает специальные символы, которые задают некоторое множество символов. Пример с простейшим выражением ((.*) – ноль или более любых символов) позволяет выделять подстроки из строки: >>> import re # подключение модуля re >>> S = 'Bugger all down here on earth!' # Строка текста >>> re.match('(.*) down (.*) on (.*)', S).groups() ('Bugger all', 'here', 'earth!') # Совпавшие подстроки Регулярные выражения позволяют искать подстроки заданного формата, например, извлекать e-mail адреса, номера телефонов и другие данные с формализуемым форматом. Подробно познакомиться с синтаксисом регулярных выражений можно в любом руководстве по использованию регулярных выражений. Для примера можно указать следующее регулярное выражение, извлекающее из текста e-mail адрес: ([a-z0-9_\.\-]{1,20})@([a-z0-9\.\-]{1,20})\.([a-z]{2,4}) Прочитать это выражение можно следующим образом: название почтового ящика содержит от 1 до 20 символов латинского алфавита (строчные буквы), цифры или символы «_», «.» или «-»; затем идёт символ @; домен второго уровня содержит от 1 до 20 символов латинского алфавита (строчные буквы), цифры или символы «.» или «-»; затем идёт символ «.»; домен первого уровня содержит от 2 до 4 символов латинского алфавита. В языке программирования Python дополнительные возможности выделяются в модули (библиотеки), которые можно подключать к вашей программе и использовать типы данных и методы, реализованные в этих модулях. Более того, эти методы могут быть реализо34 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. ваны даже на других языках программирования. Так, например, метод сортировки списка в Python реализован на языке программирования С, поскольку ресурсоёмкие задачи естественно быстрее выполняются на низкоуровневых языках программирования. Для использования регулярных выражений в Python необходимо подключить модуль re. 1.7 Функции и аргументы, прототипы функций Основным элементом структурирования программного кода и уменьшения его избыточности является декомпозиция общей задачи на подпрограммы. Подпрограмма – именованная совокупность действий (инструкций, команд), многократно используемая в программе. Выделяют две разновидности подпрограмм – процедуры и функции. Процедура – подпрограмма, выполняющая последовательность действий с использованием переданных аргументов. Функция – подпрограмма, выполняющая последовательность действий с использованием переданных аргументов и возвращающая значение заданного типа. Благодаря наличию возвращаемого значения, функция может использоваться в качестве операнда в выражениях. В Python существует только один вид подпрограмм – функции, а поведение процедур имитируется функцией, не возвращающей значение (на самом деле возвращается специальный объект None). Общий вид задания подпрограмм в Python следующий: def <имя_функции>(arg1, arg2,... argN): <тело_функции> def – это зарезервированное слово (от английского «define» – определять), инструкция, которая создает объект функции и связывает его с именем. Если функция возвращает значение определённого типа, то тело функции должно содержать инструкцию return <значение>. В качестве примера приведём функцию, которая возвращает числа ряда Фибоначчи, не превышающие заданного числа. def fib(n): result = [] # Создаём пустую последовательность a, b = 0, 1 # Присваиваем начальные значения a и b while b < n: result.append(b) 35 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. a, b = b, a+b # Можно присваивать без использования временной переменной return result # Возврат значения print (fib(100)) # Вызов функции # Вывод на экран: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89] В приведённом примере определяется функция fib(n), а затем осуществляется вызов функции путём указания названия функции и значения передаваемого аргумента, причём возвращаемое значение передаётся в качестве аргумента встроенной функции print(). Мы уже несколько раз использовали понятия «передаваемые аргументы» и «параметры», однако не определяли, в чём различие их значений. В программировании принято выделять фактические и формальные параметры. Фактическими параметрами или передаваемыми аргументами называют переменные или значения, которые указываются при вызове функции. В приведённом примере фактическим параметром является значение 100. Формальными параметрами называют переменные, которые используются в теле функций и которым присваиваются передаваемые при вызове функции значения. В приведённом примере формальным параметром является переменная n, а возвращаемое функцией fib(100) значение является фактическим параметром для функции print(). Следует отметить, что во многих языках программирования важным свойством подпрограмм является возможность задания типов параметров и типа возвращаемого значения, что позволяет ограничить применение подпрограмм только для данных чётко определённых типов. В этом смысле Python является более гибким языком программирования, поскольку не требует ни указания типов параметров, ни указания типа возвращаемого значения. При вызове подпрограммы в языках программирования различают передачу параметра по ссылке и по значению. При передаче параметра по ссылке в подпрограмму передаётся адрес переменной, поэтому все изменения формального параметра приводят к изменению фактического параметра. При передаче параметра по значению в подпрограмму передаётся копия значения фактического параметра, поэтому все изменения формального параметра никак не отражаются на значении фактического. В различных языках программирования вид передачи параметра может зависеть от типа параметра или от указания специальных ключевых слов. В Python, как мы уже знаем, все переменные передаются по ссылке. 36 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Ещё одним важным понятием при использовании функций является область видимости переменных. По области видимости выделяют глобальные и локальные переменные. Глобальные переменные «видны» из любой подпрограммы и подпрограммы могут использовать значения глобальных переменных в вычислениях. Локальные переменные «видны» только внутри той подпрограммы, в которой они впервые объявлены, и доступ к локальным переменным невозможен после завершения выполнения подпрограммы. В различных языках программирования использование и изменение глобальных переменных в подпрограммах реализовано по-разному. Но общим правилом считается минимизация использования глобальных переменных. Менее актуальным использование глобальных переменных становится при использовании объектно-ориентрованного подхода (подробности в главе 3). В Python глобальные переменные могут быть изменены внутри функции только при использовании ключевого слова global. Рассмотрим пример, демонстрирующий различие глобальных и локальных переменных. с = 1 def func1(): с = 100 print (с) def func2(): global с с = 10 print (с) func1() print (с) func2() print (с) # Вывод на экран: 100, 1, 10, 10 Первое значение (100) – это значение локальной переменной функции func1(), а все последующие – значения глобальной переменной с, изменяемой в функции func2(). Прототипом функции называется объявление функции без её определения. Под объявлением функции понимают указание имени функции, переменных и их типов, типа возвращаемого значения. Прототипы функции активно используются в языках программирования C и C++ для уведомления компиляторов о формате использования функции, которая может быть определена ниже в коде. В Python прототипы функций не используются. 37 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. 1.8 Динамическое программирование Термин динамическое программирование пришёл из задач математического моделирования и оптимизации. Идея динамического программирования состоит в разбиении общей задачи на подзадачи и в дальнейшей композиции решений подзадач в решение общей задачи. В программном коде для реализации принципа динамического программирования часто используется рекурсия. Рекурсия в программировании – вызов функции из тела самой этой функции или из тела другой функции, вызываемой из тела данной функции. К классическим задачам динамического программирования относится задача поиска чисел Фибоначчи, которую мы уже рассматривали выше. Одну и ту же задачу можно решить, используя различные алгоритмические структуры и подходы. В данном примере для решения задачи нахождения чисел Фибоначчи применим рекурсию: def F(n): if (n < 2): return 1 else: return F(n - 1) + F(n - 2) print(F(5)) # Выводит шестое число Фибоначчи – 8. В данном алгоритме функция вызывается в теле самой функции, а сама функция реализует рекуррентное соотношение для нахождения чисел Фибоначчи: F(n+2) = F(n)+F(n+1). Другая известная задача динамического программирования – задача о нахождении наибольшей общей подпоследовательности для двух последовательностей. Решение данной задачи находит практическое применение при сравнении файлов и в некоторых других задачах. Длина наибольшей общей подпоследовательности определяется следующим рекуррентным соотношением: , Здесь n1 и n2 – это длины последовательностей. Реализация вычисления длины на языке программирования Python также записывается с помощью рекурсии: def lcs_len(x, y): if len(x) == 0 or len(y) == 0: return 0 # Если последовательность пустая, возвращаем 0 xx = x[:-1] # срез - последовательность без последнего элемента yy = y[:-1] 38 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. if x[-1] == y[-1]: # Если последние элементы последовательностей равны return lcs_len(xx, yy) + 1 else: return max(lcs_len(xx, y), lcs_len(x, yy)) Следует иметь в виду, что приведённые примеры в пункте 1.8 являются учебными и требуют оптимизации для практического применения. В частности, уже известные значения чисел Фибоначчи заново рассчитываются, тогда как уже рассчитанные значения лучше хранить в массиве и использовать их. Кроме того при использовании рекурсий имеет место переполнение стека вызовов – специальной структуры, хранящей и поддерживающей последовательность вызовов функций и возврат в точку вызова. При большом количестве рекурсивных вызовов памяти для хранения этой информации может не хватить, впрочем, рекурсию можно реализовать с помощью обычного цикла while, но с использованием специальной структуры данных – стека, о котором речь пойдёт во второй главе. 39 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Глава 2. Введение в структуры данных (с использованием Python) В первой главе мы уже убедились в том, что для представления и хранения в памяти различных данных в удобном для обработки виде требуются специальные структуры, такие как, например, коллекции (массивы, списки). Во второй главе мы подробнее рассмотрим различные структуры данных и их применение при реализации алгоритмов решения практических задач программирования. Под структурой данных понимается способ хранения и организации данных для их дальнейшего эффективного использования. Зачастую от способа организации данных зависит не только удобство представления объектов и понятный код, но и быстродействие алгоритмов. 2.1 Списки (коллекции) В языке программирования Python предусмотрены стандартные типы данных, которые позволяют хранить взаимосвязанные данные в удобном для обработки виде. Эти структуры данных объединены общим понятием – коллекции. Иерархия коллекций в Python представлена на рисунке ниже. Рисунок 2.1. Коллекции в Python. 40 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. При описании структуры данных обычно указывают способ представления данных, связь между элементами (например, ссылка на следующий элемент), а также методы, которые можно применять к данной структуре данных. В зависимости от конкретной реализации коллекции поддерживаются различные операции. Операция объединения коллекций в том или ином виде присутствует во всех типах коллекций. Массивы – это лишь одна из разновидностей коллекций. Некоторые коллекции, реализованные в Python, а именно – последовательности (списки и кортежи) довольно подробно были описаны в первой главе, поэтому сейчас уделим больше внимания отображениям и множествам. Отображениями называют коллекции пар элементов «ключ-значение», причём доступ к значениям элемента осуществляется не по индексу, а путём указания соответствующего ключа. Отображения по структуре и операциям очень похожи на массивы (последовательности), только в отображениях упорядоченность элементов не является обязательным свойством, поэтому операция взятия индекса и срезы не применимы к отображениям. Реализацией отображений является ассоциативный массив. Ассоциативный массив (словарь) – структура данных, которая представляет собой неупорядоченную коллекцию, состоящую из нуля или более пар «ключ–значение» и поддерживающую операции добавления пары, а также поиска и удаления пары по уникальному ключу. Во многих языках программирования в качестве ключа обычно выступают простые типы данных (целые числа или строки), а значения относятся к одному и тому же типу данных. Значения ключей должны быть уникальными. В Python динамическая типизация позволяет в качестве значений словаря (dict) использовать ссылки на данные любых типов, а в качестве ключей – ссылки на неизменяемые объекты. Пустой словарь задаётся выражением {}. Словари определяются путём задания пар «ключ–значение» через двоеточие. Приведём пример использования словарей: >>> tel = {'МТИ': 88007003304, 'MBS': 88007003303} >>> tel['MBS'] = 88007003305 # Изменение значения по ключу >>> tel {'МТИ': 88007003304, 'MBS': 88007003305} Помимо специфических методов, к словарям, так же как и к последовательностям, можно применять оператор del, который удаляет указанный элемент словаря. 41 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Словари удобно использовать для хранения структурированной информации. Обход словарей в циклах осуществляется по значению ключа. Несмотря на то что словари представляют собой неупорядоченную коллекцию, их можно отсортировать по значению ключа. Рассмотрим эту возможность на примере: author = {"php":"Rasmus Lerdorf",\ "perl":"Larry Wall",\ "tcl":"John Ousterhout",\ "awk":"Brian Kernighan",\ "java":"James Gosling",\ "parrot":"Simon Cozens",\ "python":"Guido van Rossum"} #Либо так: langs = author.keys() # получение списка ключей langs.sort() # сортировка списка ключей for language in langs: print (language," - ",author[language]) #либо так: for key in sorted(author.iterkeys()): # iterkeys возвращает список ключей print ("%s: %s" % (key, author[key])) >>> awk - Brian Kernighan >>> java - James Gosling >>> parrot - Simon Cozens >>> perl - Larry Wall >>> php - Rasmus Lerdorf >>> python - Guido van Rossum >>> tcl - John Ousterhout С помощью словарей в Python можно реализовать различные структуры данных, в частности, возможность задавать значения произвольных типов позволяет реализовать структуры данных, известные как «структура» и «запись», которые встречаются в языках программирования C и Pascal. Запись – структура данных, состоящая из фиксированного числа компонент, называемых полями, каждая из которых может иметь свой тип. Запись является основой для создания структуры данных «связанный список», речь о котором пойдёт в пункте 2.3. Ещё одним стандартным типом данных в Python является множество (set). Множество в Python – это неупорядоченная коллекция, состоящая из нуля или более ссылок на уникальные элементы неизменяемых типов данных. Само множество при этом является изменяемым типом данных. По синтаксису и сути множества напоминают словари, в которых отсутствуют ключи, поэтому доступ к элементам 42 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. по ключу невозможен. Пустое множество задаётся с помощью функции set(), непустой массив можно задавать, как и словари, в фигурных скобках перечислением через запятую. Множества, как и словари, содержат специфичные методы, которые похожи по результату на операции над математическими множествами (объединение, пересечение, разность множеств). Описание этих методов можно легко найти в документации. Рассмотрим практический пример использования множеств. Предположим, что у нас есть кортеж ips, который содержит список IP-адресов, полученный извлечением из файла лога запросов к веб-серверу, причём адреса могут повторяться. for ip in set(ips): process_ip(ip) Использование множества позволяет запустить функцию process_ip только один раз для каждого IP-адреса, поскольку множество формирует из кортежа ips коллекцию неповторяющихся значений. Python поддерживает ещё одну структуру данных, похожую на множества – это неизменяемые или фиксированные множества (frozenset). Из названия очевидно, что фиксированные множества – это множества, которые не изменяются. Соответственно, к фиксированным множествам можно применять только те методы, которые не приводят к модификации множества. 2.2 Хеш-таблица, стек, очередь На основе ассоциативных массивов или словарей строится структура данных, применяемая в случаях, когда требуется быстрый поиск в коллекции значений. Хеш-таблица – это структура данных, реализующая ассоциативный массив и позволяющая получать доступ к данным по уникальному ключу. Ключом хеш-таблицы может быть любой объект, для которого можно вычислить хешкод. Раннее мы упоминали, что в качестве ключа словаря можно использовать ссылки на объекты только неизменяемых типов данных. Иначе объекты этих типов часто называют хешируемыми, поскольку они содержат метод, выполняющий хеширование и возвращающий уникальное числовое значение, одинаковое на всем протяжении существования объекта. Эти значения используются при индексировании словарей, что позволяет значительно увеличить скорость доступа к объектам по уникальному ключу. На рисунке 2.2 показан принцип хеширования ключей, а также ситуация совпадения хешей для разных объектов, которую называют коллизией хеширования. Любая реализация хеш-таблиц должна стремить43 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. ся к устранению подобных коллизий. Исправление подобных коллизий реализуется двумя известными способами: методом хеширования с цепочками и методом хеширования с открытой адресацией. В первом случае объекты представляются в виде ссылок на связанный список (см. пункт 2.3). При совпадении хеш-кодов происходит добавление объекта в конец соответствующего списка. Схема разрешения коллизии методом хеширования с цепочками представлена на рисунке 2.3. Если же речь идёт о хешировании с открытой адресацией, то данные не организуются в списки, однако при совпадении хеш-кодов происходит попытка вычисления хеш-кода другой хеш-функцией, либо линейный поиск незанятых строк в хештаблице. Схема разрешения коллизии методом хеширования с открытой адресацией представлена на рисунке 2.4. Применение хеш-таблиц аналогично применению словарей, рассмотренному в пункте 2.1. Списки в Python поддерживают методы, которые позволяют реализовать ещё две структуры данных – стеки и очереди. Методы append() и pop() позволяют оперировать элементами на концах списка. Рисунок 2.2. Процесс хеширования ключей ассоциативного массива, иллюстрирующий возникновение коллиции. 44 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Рисунок 2.3. Метод хеширования с цепочками. Рисунок 2.4. Метод хеширования с открытой адресацией. Стек (stack) – список, в котором операции вставки и удаления всегда выполняются над последним элементом. Стек еще называют LIFO-списком: lastin-first-out (последним пришел – первым ушел). Очередь (queue) – список, в котором операции вставки и удаления выполняются на разных концах списка. Очереди еще называют FIFO-списками: first-in-first-out (первым пришел – первым ушел). Приведем пример использования списка в качестве стека. Метод pop() без указания параметров приводит к извлечению последнего элемента списка, что и требуется по определению стека. >>> >>> >>> >>> [3, >>> stack = [3, 4, 5] stack.append(6) stack.append(7) stack 4, 5, 6, 7] stack.pop() 45 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. 7 >>> [3, >>> 6 >>> 5 >>> [3, stack 4, 5, 6] stack.pop() stack.pop() stack 4] Аналогичным образом, метод pop(0) с указанием в качестве параметра индекса нача- ла списка 0 позволяет реализовать структуру данных очередь, как показано в примере: >>> queue = ["Eric", "John", "Michael"] >>> queue.append("Terry") # Прибыл Terry >>> queue.append("Graham") # Прибыл Graham >>> queue.pop(0) 'Eric' >>> queue.pop(0) 'John' >>> queue ['Michael', 'Terry', 'Graham'] Стеки и очереди используются в алгоритмах для организации и обработки последовательности некоторых данных. 2.3 Связные списки, деревья, графы Связные списки (Linked Lists) упоминались выше при рассмотрении метода хеширования с цепочками. На рисунке 2.3 представлены фрагменты односвязных списков. Односвязные списки представляют структуру данных, в которой каждый элемент последовательности помимо данных содержит ссылку на следующий элемент. Концевой элемент содержит ссылку на пустой объект (None, Null). Если же концевой элемент содержит ссылку на начальный элемент списка, то такую структуру данных называют циклическим или кольцевым связным списком. Во многих языках программирования отличительной особенностью массива от списка, является то, что массив обычно имеет фиксированный размер и элементы массива расположены в памяти один за другим. Это создаёт определённые проблемы при динамическом изменении массива, добавлении или удалении элементов из середины массива (при этом 46 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. приходится перераспределять память, сдвигать каждый элемент, чтобы в памяти не было «пробелов»), а это довольно медленные операции. Решить эту проблему помогают списки, которые хранят не непрерывный блок данных в памяти, а ссылки на объекты в памяти, образующие элементы списка. Однако использование связных списков в определённой ситуации даёт ещё больший выигрыш в производительности. Реализовать связные списки в Python можно с помощью создания собственных типов данных (классов), используя методологию объектно- ориентированного программирования. Подробно синтаксис и описание особенностей объектно-ориентированного программирования изложены в главе 3. Следующий пример демонстрирует создание класса, описывающего один элемент (узел) односвязного списка. Для понимания примера необходимо знать, что метод __init__ выполняется при создании объекта путём вызова функции-конструктора класса Node(). class Node: def __init__(self, value = None, next = None): self.value = value self.next = next Для того чтобы определить сам список необходимо использовать ещё один класс – LinkedList, определяющий концевые элементы и длину списка. Метод __str__ применяется для вывода содержимого списка на экран. Метод __init__ выполняется при создании объекта (экземпляра класса) путём вызова функции-конструктора класса LinkedList(). class LinkedList: def __init__(self): self.first = None self.last = None self.length = 0 def __str__(self): if self.first != None: current = self.first out = 'LinkedList [\n' +str(current.value) +'\n' while current.next != None: current = current.next out += str(current.value) + '\n' return out + ']' return 'LinkedList []' Если каждый элемент связного списка ссылается не только на следующий узел, но и на предыдущий, то такая структура данных называется двусвязным списком, схема которого приведена на рисунке 2.5. Двусвязные списки так же могут быть циклическими, если концевые элементы имеют соответствующие ссылки. 47 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Рисунок 2.5. Схема двусвязного списка. Если элемент содержит ссылки более чем на два узла, то список называется многосвязным. Преимущество связного списка в том, что не требуется перестраивать последовательность узлов, независимо от того, в какую позицию списка вставляется новый элемент, достаточно лишь поменять ссылки на следующий и (или) предыдущий элементы. Недостаток связных списков – это последовательный доступ (sequential access) к элементам, тогда как для массивов время доступа постоянно и не зависит от размера – random access. Если приложению требуется быстрый поиск элемента по индексу, то лучше воспользоваться массивами или хеш-таблицами. Представленных выше классов, описывающих односвязный список и элемент списка, явно не достаточно, чтобы можно было использовать эту структуру. Естественно, надо также определить методы вставки, удаления, вычисления длины, сортировки и другие Приведём метод добавления нового элемента в конец списка: def add(self, x): self.length+=1 if self.first == None: #self.first и self.last будут указывать на одну область памяти self.last = self.first = Node(x, None) else: #здесь, уже на разные, т.к. произошло присваивание self.last.next = self.last = Node(x, None) Теперь можно использовать данный метод для добавления элементов в конец списка следующим образом: # создание связного списка из 3-х элементов L = LinkedList() L.add(1) L.add(2) L.add(3) Остальные методы для работы со списками можно реализовать и использовать аналогичным способом. Выше, как вы уже, скорее всего, заметили, мы описывали структуры данных, предназначенные для хранения линейных списков или двумерных таблиц данных. На практике ча48 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. сто возникает необходимость в обработке иерархических данных или данных с произвольными связями. В этом случае используют специальные структуры данных, общее название которых – графы. Понятие граф пришло в информатику из одного из разделов прикладной математики, рассматривающего задачи, модель которых представляется в виде узлов, между которыми установлены связи (задача о кёнигсбергских мостах, задача о коммивояжере и другие). Граф – это совокупность непустого множества вершин (узлов) и множества связей между вершинами (рёбер), которые могут обладать определённым весом (взвешенный граф) и направлением (ориентированный граф). Графы в математике могут определяться описанием множеств рёбер и вершин, графически или с помощью матриц инцидентности или смежности, которые показывают наличие или отсутствие связей между вершинами и рёбрами. Графами можно представить любую многосвязную структуру или систему, от транспортной сети до сети передачи данных и от взаимодействия белков в ядре клетки до связей между людьми в Интернете [1]. Частным случаем графа является дерево, структура данных, которая широко применяется в программировании, достаточно вспомнить, что иерархическую структуру файловой системы представляют в виде дерева файлов и каталогов. В общем смысле, дерево – это иерархическая структура, хранящая коллекцию объектов. Дерево (tree) — это непустая коллекция вершин (узлов, node) и ребер, удовлетворяющих следующему ключевому свойству: между любыми двумя узлами существует только один путь, соединяющий их. Очевидно, что при наличии между двумя узлами более одного пути, мы будем иметь дело с графом. Несвязанный набор деревьев называется лесом (forest). Для определения узлов существуют следующие сложившиеся термины: root – узел, расположенный в корне дерева; siblings – узлы, имеющие одного и того же родителя; ancestor или parent – родительский узел; descendant – дочерний узел [41]. Довольно часто в программировании порядок следования дочерних узлов имеет большое значение. В этом случае применяют упорядоченное дерево (ordered tree) — это дерево с определенным корневым узлом, в котором определен порядок следования дочерних узлов для каждого узла [41]. Пример дерева приведён на рисунке 2.6. 49 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Рисунок 2.6. Пример дерева. Можно отметить, что деревья напоминают связные списки, поэтому при работе с деревьями определённую сложность представляет реализация операций динамического изменения дерева, таких как, например, вставка или удаление узлов. Для обхода дерева используются известные алгоритмы, которые можно легко найти в справочной литературе по алгоритмам. Обычно для этих целей используют рекурсивные алгоритмы, однако можно использовать и стек, в который будут записываться узлы по мере их прохождения. Деревья в программном коде можно представлять различными способами. Самым простым является представление дерева в виде массива. Предположим, что вы имеем дерево с вершинами, пронумерованными от 1 до n. Тогда каждый элемент массива A[i] будет содержать ссылку на родительский узел. Корневой узел не имеет родительского узла, поэтому A[root] = 0, где root – это номер корневого узла. Пример данного представления приведён на рисунке 2.7, при этому очевидно, что данный способ не подходит для представления упорядоченного дерева. Еще один возможный вариант представления деревьев, который поддерживает задание упорядоченного дерева – это использование связных списков, содержащих все узлы дерева [41], как показано на рисунке 2.8. 50 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Рисунок 2.7. Представление дерева в виде массива. Рисунок 2.8. Представление дерева в виде связного списка. На рисунке 2.9 представлен вариант дерева, которое можно хранить в обычных списках Python [1]. Рисунок 2.9. Структура дерева для представления в виде списка списков. 51 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Мы можем представить это дерево как список списков: >>> T = [["a", "b"], ["c"], ["d", ["e", "f"]]] >>> T[0][1] 'b' >>> T[2][1][0] 'e' Другой способ позволяет избежать дублирования вершин в списках, для этого, как мы знаем, можно применить структуру set (множество). В примере приведён способ задания графа в виде списка множеств: a, b, c, d, e, f, g, h = range(8) N = [ {b, c, d, e, f}, # a {c, e}, # b {d}, # c {e}, # d {f}, # e {c, g, h}, # f {f, h}, # g {f, g} # h ] Этот код описывает граф, представленный на рисунке 2.10. Рисунок 2.10. Ориентированный граф. Тот же самый граф можно задать с помощью матрицы смежности: a, b, c, d, e, f, g, h = range(8) # a b c d e f g h N = [[0,1,1,1,1,1,0,0], # a [0,0,1,0,1,0,0,0], # b [0,0,0,1,0,0,0,0], # c [0,0,0,0,1,0,0,0], # d [0,0,0,0,0,1,0,0], # e [0,0,1,0,0,0,1,1], # f [0,0,0,0,0,1,0,1], # g [0,0,0,0,0,1,1,0]] # h 52 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Работая как с обычным двухмерным массивом, можно получить информацию о смежных ребрах и степенях вершин. Бинарные (двоичные) деревья являются одним из самых востребованных вариантов данной структуры данных, так как широко используются в поисковых алгоритмах и для решения других вычислительных задач [41]. В двоичных деревьях степень вершин (узлов) не превосходит трёх, то есть узел может иметь один родительский узел и два дочерних. В компьютерных технологиях деревья являются ключевым компонентом для создания алгоритмов хранения, поиска и обработки информации. Любой программист должен уметь работать с подобными структурами данных, тем более для этого используются стандартные и хорошо зарекомендовавшие себя алгоритмы [41]. Графы и деревья находят очень широкое применение при решении практических задач, будь то построение сети или решение задач оптимизации. Для Python существуют библиотеки, упрощающие работу с графами и деревьями, среди них можно отметить NetworkX, python-graph и Graphine. Более сложные структуры данных, в том числе графы, вершины которых обладают набором атрибутов и методов для выполнения действий с этими вершинами, можно реализовать при помощи объектно-ориентированного подхода в программировании. 53 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Глава 3. Объектно-ориентированный подход В предыдущих главах уже упоминался объектно-ориентированный подход в программировании и даже приводились некоторые примеры, демонстрирующие создание объектов новых типов (например, связных списков). Большинство из приведённых ранее примеров относятся к парадигме структурного программирования (декомпозиция задачи происходит путём разделения программы на подпрограммы). Объектно-ориентированная парадигма предлагает использовать объекты для описания программных сущностей, представляющих абстрактное описание сущностей реальной задачи. Подобный подход к программированию оправдан при реализации проектов крупных систем с большим количеством сущностей. На самом деле следует различать понятие типа данных и класса (одного из базовых понятий в объектно-ориентированном программировании (ООП)), хотя зачастую их отождествляют. Определение типа данных уже приведено в первой главе. Класс, в отличие от типа данных, определяет не набор значений и методов, а описывает объект задачи, часто в более абстрактной форме. По сути, класс – это пользовательский тип. Объектно-ориентированный подход к построению программ применяют не только на этапе создания, но и на этапе проектирования структуры программы – в этом случае обычно говорят об объектно-ориентированном (ОО) анализе и проектировании, без которых не обходится создание информационных систем. В данной главе мы будем говорить, в первую очередь, об ООП, поскольку ОО анализ и проектирование являются отдельной достаточно сложной дисциплиной. Объектно-ориентированный подход в программировании основан на использовании классов – специальных структур, описывающих содержимое и тип данных объекта. Сами объекты при этом называют экземплярами класса. Каждый класс содержит атрибуты, которые применяются для хранения состояния экземпляров данного класса в атрибутах данных (членах класса, переменных класса, свойствах) и для выполнения методов (функцийчленов класса, атрибутов-методов), применяемых к экземплярам данного класса. Три базовых свойства ООП – это наследование, инкапсуляция и полиморфизм. О каждом из них поговорим более подробно далее в этой главе. 3.1. Наследование Язык программирования Python изначально проектировался как объектно- ориентированный язык. Рассмотрим синтаксис определения класса – для этого используется ключевое слово class: 54 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. class название (класс1, …): def метод(self, …): тело_метода Если в определении класса после названия присутствуют скобки, а в скобках указаны названия других классов, то от этих классов наследуются все свойства и методы, то есть, используя экземпляр данного класса, можно обращаться к свойствам и методам родительского (базового) класса. Из приведённого синтаксиса понятно, что в Python поддерживается множественное наследование, то есть новый класс может быть образован сразу от нескольких базовых классов. Эту возможность необходимо использовать очень осторожно, поскольку множественное наследование может привести к конфликтам именования переменных и непредвиденным ошибкам. В большинстве случаев достаточно наследования от одного базового класса. Объект может быть составным и включать в себя другие объекты. Данная особенность объектно-ориентированного подхода называется свойством композиции. Зарезервированное слово self является именем переменной – ссылки на сам экземпляр класса. Переменная self обычно передаётся в качестве первого параметра в каждый из методов класса. Во многих языках программирования аналогом переменной self в Python является переменная с зарезервированным именем this. В отличие от других объектно-ориентированных языков в Python атрибуты данных явно можно не объявлять, первое обращение к переменной является объявлением и определением атрибута данных. Более того, определить атрибуты данных можно в любом методе, обратившись к переменной в формате: self.x = 0 – данное выражение определяет переменную-атрибут данных с именем x и присваивает ей значение 0, подобно тому, как мы это делали в главе 2 при определении класса для описания узла связного списка. Экземпляр класса генерируется при вызове, например, таким образом: a = MyClass() # a – экземпляр класса MyClass Часто возникают ситуации, когда необходимо не просто создать объект, а создать объект с некоторыми инициализированными значениями атрибутов данных. В этом случае применяют специальную функцию-метод, которую называют конструктором. В Python конструктор реализует функция __init__. Создадим простой пример класса, описывающего точку с координатами x и y: class Point: def __init__(self, x, y): self.x = x 55 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. self.y = y Тогда создание экземпляра данного класса можно осуществить следующим образом: p = Point(10,12) # создание точки с координатами (10;12) print (p.x, ',' ,p.y) Атрибут данных можно сделать приватным (private) — то есть доступным только «внутри» класса — для этого слева к имени переменной следует добавить два символа подчеркивания: class Point: __x=0 __y=0 def __init__(self, x, y): self.__x = x self.__y = y В этом случае обратиться напрямую к атрибуту с помощью выражения p.__x уже невозможно. Обычно, если требуется, доступ к приватным атрибутам можно получить через специальные функции («геттеры» и «сеттеры»). В этом случае атрибуты данных часто называют свойствами объекта (property). Рассмотрим пример: class Point: __x=0 __y=0 def _get_offset(self): self.__x += 5 return self.__x offset = property(_get_offset) Применять данный класс можно следующим образом: >>> d = Point() >>> d.offset 5 >>> d.offset 10 Разрешение имен атрибутов работает сверху вниз: если атрибут не найден в текущем классе, поиск продолжается в базовом классе, и так далее по рекурсии. Производные классы могут переопределить методы базовых классов — все методы являются в этом смысле 56 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. виртуальными. Вызвать метод базового класса можно с префиксом: Base.method(). В этом выражении Base – имя базового класса. Для того чтобы проверить принадлежность экземпляра заданному классу, применяют функцию isinstance(), например, isinstance(obj, int) возвратит True только в том случае, если переменная obj принадлежит классу int или другому классу, наследующему класс int. Для проверки наследственности класса используется функция issubclass(). Так выражение issubclass(float, int) возвратит False, поскольку класс float не является наследником int. Существует множество встроенных классов в Python, которые образуют иерархию классов. Любой созданный в Python класс будет наследником класса object, который находится в вершине иерархии классов. 3.2. Инкапсуляция Другим важнейшим принципом ООП и абстракции является инкапсуляция. Смысл инкапсуляции состоит в возможности скрыть внутренние особенности работы и атрибуты объекта от внешних объектов. Иначе говоря, данные объекта (экземпляра класса) скрываются от прямого доступа извне, позволяя объекту самому управлять доступом к своим атрибутам. Нам уже известно, что все значения в Python являются объектами, которые предоставляют пользователям общедоступный интерфейс, а методы и данные объекта доступны через его атрибуты. Сокрытие информации о внутреннем устройстве объекта выполняется в Python на уровне соглашения между программистами о том, какие атрибуты относятся к общедоступному интерфейсу класса, а какие — к его внутренней реализации. Одиночное подчеркивание в начале имени атрибута говорит о том, что метод не предназначен для использования вне методов класса (или вне функций и классов модуля), однако, атрибут все-таки доступен по этому имени. Два подчеркивания в начале имени дают несколько большую защиту: атрибут перестает быть доступен по этому имени (смотри пункт 3.1). В других языках программирования существуют специальные модификаторы уровня доступа (public, private, protected), которые позволяют явно указать доступность того или иного атрибута класса из различных частей программного кода. Модификатор public позволяет получить прямой доступ к атрибуту. При наличии модификатора protected атрибуты будут доступны только из самого класса и классов, наследующих данный класс. Модификатор private позволяет получить доступ к атрибуту только из методов самого класса. 57 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Приведём пример, в котором атрибут _x будет доступен через свойство x, описывающее методы объекта при обращении (getx), при присваивании (setx) и при удалении (delx) атрибута. При этом доступ к атрибуту осуществляется привычным образом. class A(object): def __init__(self, x): self._x = x def getx(self): # метод для получения значения return self._x def setx(self, value): # присваивание нового значения self._x = value def delx(self): # удаление атрибута del self._x x = property(getx, setx, delx, "Свойство x") # определяем x как свойство a = A(5) print (a.x) a.x = 5 # Синтаксис доступа к атрибуту при этом прежний Подобный способ доступа к атрибутам через свойства применяется для проверки корректности значений, присваиваемых атрибутам класса. Кроме того подобное поведение позволит безболезненно перейти к новому способу организации данных внутри класса без изменения внешних обращений к этому классу. 3.3. Полиморфизм Слово «полиморфизм» имеет греческую природу и означает «имеющий многие формы». Смысл полиморфизма состоит в том, что разные объекты могут иметь одинаковые по смыслу атрибуты с одинаковым названием, но выполняющие специфичные для данного объекта операции. Простым примером полиморфизма может служить оператор сложения, применяемый для чисел и для строк: 123+456 и 'abc'+'def'. Имея одинаковую смысловую нагрузку, оператор сложения имеет различную реализацию для различных типов данных. Для того чтобы обеспечить полиморфизм в некоторых языках программирования требуется создание так называемых виртуальных методов, которые должны быть переопределены в классах-потомках. В языке программирования Python все методы являются виртуальными. Как уже упоминалось выше, обратиться к доступному методу можно путём явного указания названия класса при вызове. В приведённом примере осуществляется вызов конструктора класса-родителя (суперкласса). 58 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. class Child(Parent): def __init__(self): Parent.__init__(self) В общем случае для получения класса-предка применяется функция super. class Child(Parent): def __init__(self): super(Child, self).__init__(self) Пример использования полиморфизма рассмотрим для двух классов, содержащих функцию с одним названием: class T1: n=10 def total(self,N): self.total = int(self.n) + int(N) class T2: def total(self,s): self.total = len(str(s)) t1 = T1() t2 = T2() t1.total(45) t2.total(45) print (t1.total) # Вывод: 55 print (t2.total) # Вывод: 2 Полиморфизм в объектно-ориентированном программировании дает возможность реализовывать так называемые единые интерфейсы для объектов различных классов. Это означает, что классы-наследники могут по-своему реализовывать методы с одним и тем же названием. В объектно-ориентированных языках программирования выделяют абстрактные классы – базовые классы, которые служат лишь для организации наследования, при этом экземпляр абстрактного класса не может быть создан. Причиной создания абстрактных классов является то, что невозможно дать осмысленное определение виртуальных функций класса, однако конкретные реализации в дочерних классах уже имеют смысл. Часто для реализации полиморфизма используют специальные структуры, которые похожи на абстрактные классы, но при этом все методы должны быть без определения – интерфейсы. В этом случае говорят не о наследовании, а о реализации интерфейса дочерним классом, поскольку все методы интерфейса должны быть реализованы в дочернем классе. Интерфейсы описывают структуру классов-наследников и позволяют использовать в коде любые классы, 59 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. реализующие данный интерфейс, указывая в качестве типа данных экземпляра название интерфейса. Таким образом, полиморфизм позволяет осуществить принцип абстракции кода и использовать переменные-объекты в методах, не зная заранее, какого типа будут эти переменные, но зная, какой интерфейс они реализуют. При этом переопределение методов в дочерних классах позволяет специализировать ранее написанный исходный код, не меняя его в базовых классах. 3.4. Модули в Python Python позволяет поместить классы, функции или данные в отдельный файл и использовать их в других программах. Такой файл называется модулем. Объекты из модуля могут быть импортированы в другие модули. Имя файла образуется путем добавления к имени модуля расширения .py. При импорте модуля интерпретатор ищет файл с указанным именем и расширением .py сначала в текущем каталоге, затем в каталогах, указанных в переменной окружения PYTHONPATH, затем в зависящих от платформы путях по умолчанию, а также в специальных файлах с расширением .pth, которые лежат в стандартных каталогах [41]. Импорт модуля можно осуществить следующим способом: >>> import my_module Мы получаем доступ ко всем функциям, которые в модуле определены: >>> my_module.func1() >>> my_module.func2() ... Для более короткой записи можно создать локальную переменную: >>> f1 = my_module.func1 Второй вариант импорта — взятие непосредственно имени без имени модуля: >>> from my_module import func1, func2 >>> func1() Третий вариант импорта — включение всех имен, определенных в модуле: >>> from my_module import * >>> func1() 60 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Python распространяется с библиотекой стандартных модулей. Библиотека включает в себя более 200 модулей, которые выполняют платформенно-зависимую поддержку таких задач, как: интерфейс к операционной системе, управление объектами, поиск, сеть + интернет, GUI и т.д. Полный список стандартных модулей можно посмотреть на http://docs.python.org/library/. В стандартной библиотеке имеется целый набор модулей для различных сервисов и протоколов интернет. Наиболее употребимыми можно считать urllib.request для получения данных по заданному адресу (URL) и smtplib для отправки сообщений электронной почты [34]: >>> from urllib.request import urlopen >>> for line in urlopen('http://tycho.usno.navy.mil/cgi-bin/timer.pl'): ... if 'EST' in line or 'EDT' in line: # временные зоны ... print(line)
Nov. 25, 09:43:32 PM EST >>> >>> >>> ... ... ... ... ... >>> import smtplib server = smtplib.SMTP('localhost') server.sendmail('[email protected]', '[email protected]', """To: [email protected] From: [email protected] Beware the Ides of March. """) server.quit() Заметьте, что второй пример требует почтового сервера на той же машине. Модуль datetime предлагает классы для работы с датами и временем как в простых, так и сложных случаях. Кроме поддержки календарной арифметики, реализация обращает особенное внимание на эффективность вычисления составных частей для вывода и дальнейших манипуляций. Модуль также предлагает объекты с поддержкой временных зон [34]. # даты можно легко составлять и выводить в требуемом формате >>> from datetime import date >>> now_date = date.today() >>> now_date datetime.date(2009, 2, 3) >>> now_date.strftime("%d.%m.%Y") '03.02.2009' # даты поддерживают календарную арифметику >>> birth_day = date(1964, 7, 31) >>> years_old = now_date - birth_day >>> years_old.days 16258 61 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Пакеты xml.dom и xml.sax предоставляют поддержку парсинга XML — формата для обмена данными. Аналогично, модуль csv поддерживает чтение и запись в распространённом формате баз данных. Вместе эти модули серьёзно облегчают обмен данными между приложениями на Python и другими приложениями [34]. Интернационализация поддерживается благодаря ряду модулей, включая gettext, locale и пакет codecs. Перечислять и описывать все возможные модули нет необходимости, поскольку, обладая знаниями по написанию алгоритмов и применению структурного и объектноориентированного подходов, можно найти, понять и применить в программе любой модуль с помощью документации к этому модулю, которая часто содержит примеры его использования. 3.5. Классы и модули для работы с файлами Ещё одной стандартной возможностью, которую должен поддерживать любой язык программирования – это работа с файловой системой. В языках, основанных на структурном программировании, за работу с файлами и каталогами отвечает набор подпрограмм, а в объектно-ориентированных языках программирования эту функциональность обеспечивает набор стандартных классов. Исчерпывающее описание работы с файлами в Python и примеры представлены в документации к Python и в цикле статей «Программирование на Python» Яковлева С. на сайте поддержки разработчиков компании IBM [40]. Подробности о различных модулях, обеспечивающих работу с файлами и каталогами можно найти в подробном справочнике Д. Бизли [3]. Открыть файл можно с помощью функции open: open(name[, mode[, buffering]]) Функция возвращает файловый объект. Обязателен только первый аргумент. Если остальные параметры отсутствуют, файл будет доступен на чтение. Таблица режимов (mode) функции open: 'r' – чтение, 'w' – запись, 'a' – добавление, 'b' – бинарный режим, '+' – чтение/запись. Режим '+' может быть добавлен к остальным режимам. По умолчанию Python открывает файлы в текстовом режиме. Для открытия файла в бинарном режиме на чтение можно добавить 'rb'. Третий параметр устанавливает размер буферизации при работе с файлом. По умолчанию он выключен, и чтение/запись идет напрямую с диска на диск. Для включения буфера третий параметр должен быть отличным от нуля [40]. # Запись в файл: >>> f = open('my_file', 'w') >>> f.write('Hello, ') >>> f.write('World!') 62 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. >>> f.close() # Чтение: >>> f = open('my_file', 'r') >>> f.read(5) 'Hello' >>> f.read() ', World!' В командной строке можно записать подряд несколько команд, передавая результат работы от одной команды к другой по конвейеру – или по каналу (pipe): cat my_file | python test.py По умолчанию метод read() читает данные последовательно по порядку, от начала и до конца файла. Для произвольного доступа к файлу есть функция seek: seek(offset[, whence]) offset – смещение в байтах относительно начала файла; whence – по умолчанию равен нулю, указывает на то, что смещение берется относительно начала файла. Пример: >>> f = open(r'my_file', 'w') >>> f.write('01234567890123456789') >>> f.seek(5) >>> f.write('Hello, World!') >>> f.close() >>> f = open(r'my_file') >>> f.read() '01234Hello, World!89' Функция tell() возвращает текущую позицию файла. Обычно мы имеем дело с текстовыми файлами. Прочитать одну строку: file.readline() Функция readline() без параметра читает всю строку, наличие параметра указывает функции максимальное число символов строки, которое будет прочитано. Прочитать все строки и вернуть список строк: file.readlines(); записать строки в файл: file.writelines(). Пример. Прочитать файл и записать его содержимое в другой файл: f = open(r'my_file') lines = f.readlines() f.close() lines[0] = "This is a my_file2 \n" # изменяем 1-ю строку f = open(r'my_file2','w') f.writelines(lines) f.close() Для закрытия файла есть метод close(). Обычно файл закрывается сам после того, как вы выходите из программы, но файлы нужно закрывать вручную по нескольким причинам. 63 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Python может буферизировать запись в файл ваших данных, что может привести к неожиданным эффектам и возникновению ошибок [40]. У операционной системы есть ограничение на число одновременно открытых файлов. При доступе к файлу из разных мест одновременно и на чтение, и на запись необходимо синхронизировать файловые операции. Буферизация записи может привести к тому, что запись уже произошла, а данных в файле еще нет. Если вы все же не хотите закрывать файл, то синхронизировать многопользовательский доступ к файлу на чтение/запись можно с помощью функции flush(), которая актуализирует все операции записи на диск. При этом возможна блокировка файла на чтение. Итерация по файлу является базовой операцией и имеет множество вариантов. Использование функции read() для байтового чтения: f = open(filename) while True: char = f.read(1) if not char: break process(char) f.close() Построчное чтение текстовых файлов и функция readline(): f = open(filename) while True: line = f.readline() if not line: break process(line) f.close() Стандартный модуль os имеет интерфейс работы с файловой системой. Каждая программа имеет текущий каталог. Функция os.getcwd возвращает текущий каталог: import os cwd = os.getcwd() print (cwd) Проверить наличие файла в текущем каталоге: os.path.exists('my_file') Вывести список файлов и подкаталогов для данного каталога: os.listdir(path) Следующий пример рекурсивно выводит список всех файлов для данного каталога и подкаталогов: import os def walk(dir): for name in os.listdir(dir): # список файлов и каталогов в dir 64 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. path = os.path.join(dir, name) # Получение полного пути файла/каталога if os.path.isfile(path): # Проверка, что данный путь указывает на файл print (path) else: walk (path) walk('.') В следующем примере мы получим статистическую информацию о текущем каталоге: общий размер каталога в байтах, число файлов, число подкаталогов. Стандартная функция os.walk имеет один обязательный параметр: каталог, для которого необходимо получить информацию. import os, sys def getlocaldata(sms,dr,flst): # Функция для подсчёта for f in flst: fullf = os.path.join(dr,f) if os.path.islink(fullf): continue # Не считаем ярлыки if os.path.isfile(fullf): sms[0] += os.path.getsize(fullf) sms[1] += 1 else: sms[2] += 1 def dtstat(dtroot): sums = [0,0,1] # 0 байтов, 0 файлов, 1 каталог for dirpath, dirnames, filenames in os.walk(dtroot): # Дерево файлов getlocaldata(sums, dirpath, dirnames + filenames) return sums report = dtstat('.') print (report) Данный пример будет работать только в Python 3 версии, в предыдущих версиях функция находилась в модуле os.path и имела другие параметры. В третьей главе мы изучили основы объектно-ориентированного подхода в программировании. Изложенные в первых трёх главах основы программирования на примере Python позволяют понимать принципы алгоритмизации и самостоятельно создавать скрипты для автоматизации. Подробнее вопросы автоматизации повседневных задач рассматриваются в 6 главе. А в следующей главе мы затронем вопросы, связанные с многообразием технологий и инструментария для разработки. 65 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Глава 4. Особенности языков и технологий программирования Изучаемая дисциплина нацелена не только на освоение основ программирования, но также на получение знаний в области существующих платформ разработки. Понятие «платформа разработки» трактуется по-разному при использовании этого словосочетания в различном контексте. Обычно это словосочетание связано с инструментальными средствами разработки и исполнения программного кода. Платформа разработки – совокупность инструментальных средств разработки и исполнения программного кода, а также иное программное обеспечение, обеспечивающее полный цикл создания приложений с использованием различных технологий программирования. Напомним, что программным обеспечением (ПО) называют совокупность программ системы обработки информации и программных документов, необходимых для эксплуатации этих программ. Существуют различные признаки классификации программного обеспечения, но наиболее часто встречаемым признаком является назначение ПО. По этому признаку выделяют системное ПО (предназначено для обеспечения работоспособности и эффективной работы компонентов вычислительной системы), прикладное ПО (предназначено для решения конкретных прикладных задач) и инструментальное ПО (предназначено для разработки программного обеспечения). Как несложно догадаться, к системному ПО относят, например, операционные системы, драйверы, утилиты общего назначения, а также встроенное ПО, обеспечивающее работу различных электронных устройств. Прикладное ПО направлено на обеспечение взаимодействия пользователя и программы, решающей конкретную задачу, например, текстовый или графический редактор, к прикладному ПО также относят специализированные информационные системы. В рамках данной главы нас в первую очередь интересует инструментальное ПО. Инструментальное ПО — программное обеспечение, предназначенное для использования в ходе проектирования, создания, отладки, внедрения и сопровождения программ. Иначе говоря, инструментальное ПО используется при реализации программного продукта на всех этапах разработки, поэтому инструментальное ПО часто называют инструментальными средствами разработки (ИСР) ПО. К ИСР ПО относят: системы проектирования и управления; системы программирования; интегрированные среды разработки (IDE); текстовые редакторы кода; SDK; библиотеки подпрограмм; компиляторы; интерпретаторы; линковщики; парсеры; ассемблеры; отладчи66 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. ки; генераторы документации; средства анализа покрытия кода; средства автоматизированного тестирования; системы управления версиями; и др. Многие из этих средств мы уже рассматривали в главе 1. Некоторые из перечисленных средств будут подробнее рассмотрены далее в 4 и 5 главах. Кратко охарактеризуем каждое из перечисленных средств. На начальных этапах разработки ПО применяют системы автоматизированного проектирования и управления разработкой, которые помогают построить первоначальную логическую модель и провести декомпозицию решаемой задачи для дальнейшей реализации – это один из важнейших этапов, от которого зависит весь цикл разработки. Системы программирования и интегрированные среды разработки (IDE) часто отождествляют, поскольку оба эти понятия обозначают системы, содержащие весь набор ИСР ПО, в том числе иногда с состав систем программирования и IDE включают также средства проектирования и управления. Текстовый редактор кода обеспечивает подсветку и автоматическое форматирование кода на языке программирования, автодополнение кода и другие инструменты, упрощающие программирование и чтение кода. Для реализации того или иного функционала программистам часто требуется использовать стандартные библиотеки подпрограмм или библиотеки сторонних разработчиков, в которых уже реализована вся необходимая для решения задачи логика. Эти библиотеки содержат код подпрограмм или классов, которые можно использовать после подключения к своему проекту так, будто вы сами написали этот код. Готовый набор библиотек, предназначенных для реализации какой-нибудь технологии или для использования кода на конкретной аппаратной платформе, предоставляют программисту в виде комплекта средств разработки (SDK – от англ. Software Development Kit), например, для разработки под операционной системой Android предоставляется Android SDK. Линковщики или компоновщики формируют сборку проекта в исполняемый код из отдельных файлов, классов и библиотек, транслируемых компилятором или интерпретатором в машинный код. Для контроля и исправления ошибок программного кода используются отладчики, а для проверки работоспособности всей программы и отдельных её компонентов, применяют средства автоматического тестирования и анализа покрытия кода тестами. Важное значение при совместной разработке имеют системы управления версиями, предназначенные для контроля и поддержки изменения кода проекта несколькими программистами, а так же средства автоматической генерации документации, которые позволяют быстро разобраться в чужом коде для расширения функционала или исправления ошибок. 67 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Существует множество других ИСР ПО, которые будут рассмотрены более подробно далее. Для того чтобы легче было ориентироваться во всём разнообразии ИСР ПО, попытаемся выделить признаки, по которым можно построить классификацию средств разработки:  по этапам процесса разработки ПО можно выделить инструментальные средства моделирования и проектирования ПО; инструментальные средства реализации (кодирования) ПО; инструментальные средства тестирования и отладки ПО; инструментальные средства документирования ПО; инструментальные средства внедрения и сопровождения ПО;  по типу разрабатываемого ПО выделяют ИСР настольных приложений, ИСР вебприложений, ИСР информационных систем, ИСР экспертных систем, ИСР ПО управления электронным устройством (драйверы, контроллеры), ИСР распределённых приложений и т.д.;  по включенности в другие ИСР можно выделить отдельную независимую программу, платформу, IDE (интегрированную среду разработки), фреймворк, интегрируемое ИСР (плагин, библиотеку, SDK);  по методологии разработки ПО выделяют средства, поддержки управления проектами и программирования с использованием различных методик программирования, которые будут рассмотрены в главе 5, например, существуют ИСР, реализующие удалённую парную разработку ПО (один из методов в гибкой методологии разработки);  по наличию кроссплатформенных решений различают ИСР, предназначенные для разработки для конкретной аппаратной платформы (Windows, iOS), или для различных платформ;  по числу поддерживаемых языков программирования;  по наличию визуальных средств разработки выделяют средства разработки без создания пользовательского интерфейса (например, для разработки ПО, реализующего бизнес-логику веб-сервера) и ИСР, позволяющие интерактивно создавать пользовательский интерфейс с помощью графических средств;  по применению на различных платформах можно выделить ИСР ПО для ОС реального времени, ОС мобильных устройств, ОС настольных компьютеров, серверных ОС и т.п.;  по распределённости выделяют средства для разработки локальных и распределённых сетевых приложений. 68 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Мы попытались выделить основные признаки классификации ИСР ПО, которые недостаточно хорошо освещены в литературе, однако существует классификация, разработанная UDC Consortium – «Универсальный десятичный классификатор» (УДК) [29], который предлагает следующую иерархическую структуру для классификации ИСР ПО:  004.4'22 Средства автоматизированной разработки программного обеспечения (CASE).  004.4'23 Средства поддержки программирования.  o 004.4'232 Редакторы программ. o 004.4'233 Отладочные программы. o 004.4'234 Программы просмотра (browsers). o 004.4'236 Средства визуального программирования. 004.4'24 Средства автоматической разработки программного обеспечения. o 004.4'242 Генераторы прикладных программ. Автоматическое программирование. o  004.4'244 Генераторы систем. 004.4'27 Средства разработки мультимедиа. o 004.4'272 Авторские системы, поддерживающие программирование и структурирование диалоговых сред (Authoring systems). o 004.4'273 Редакторы изображений (Image editors). o 004.4'274 Видеоредакторы (преобразователи аналоговых изображений в цифровые и обратно) (Video editors) o 004.4'275 Программы анимации. Синтез динамических изображений. o 004.4'277 Средства обработки звука.  004.4'277.2 Редакторы звука.  004.4'277.4 Средства создания музыки. В классификаторе УДК совершенно справедливо, помимо перечисленных ранее ИСР ПО, представлены средства автоматической разработки, которые позволяют создавать готовый программный продукт без знания языков программирования с использованием графического интерфейса пользователя; средства разработки мультимедиа, к которым, помимо графических, видео-, аудио- и анимационных редакторов, относят также авторские системы, в которых первостепенное значение имеет содержимое и его представление в виде диалоговой среды. Примером авторских систем может являться среда разработки электронных учебных курсов (подготовка интерактивного лекционного материала, практических работ и средств проведения контрольного тестирования). Далее в этой главе мы будем рассматривать ИСР ПО, языки и технологии программирования, условно разделив их на средства разработки настольных и серверных приложений и средства веб-разработки. Следует понимать, что рассматриваемые платформы и языки 69 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. программирования могут быть универсальными и предназначаться для разработки как настольных, сетевых клиент-серверных приложений, так и веб-приложений. 4.1. Особенности программирования и платформ разработки настольных и серверных приложений (рассмотрение C/С++, Java, C#, .NET) Разработку любой сложной системы следует начинать с проектирования. От этого этапа зачастую зависит успех всей разработки, поэтому для построения структуры ПО используют специальные средства разработки, которые на разных уровнях применяются как системными архитекторами, так и программистами, реализующими программный код. Подобное инструментальное ПО получило название средств автоматизированной поддержки проектирования ПО – CASE-системы. CASE (англ. Computer-Aided Software Engineering) — набор инструментов для проектирования и анализа архитектуры ПО, который обеспечивает этапы жизненного цикла разработки ПО на уровне логической моделирования. Функциями CASE-средств являются анализ, проектирование и программирование. Помимо этих функций CASE обычно используются для автоматизации проектирования интерфейсов, документирования, а также для автоматического генерирования программного кода по построенной модели. Принято выделять уровни CASE-средств, а именно:  СASE-средства верхнего уровня (upper-CASE), обеспечивающие управление проектом на первоначальных этапах (планирование и построение логической модели задачи), а также проектирование структуры разрабатываемой системы, требований к системе;  CASE-средства нижнего уровня (lower-CASE) используются разработчиком для формирования структуры программного кода, его оптимизации (рефакторинга), моделирования взаимодействий абстракций и объектов программного кода. Обычно CASE-средства позволяют реализовывать проектирование в форме построе- ния разнообразных диаграмм, описывающих отношения между объектами, и последующей генерации основного программного кода по построенным диаграммам и наоборот. Типичными CASE-инструментами являются:  инструменты управления конфигурацией;  инструменты проектирования баз данных, обеспечивающие моделирование данных и генерацию схем баз данных;  инструменты моделирования данных;  инструменты анализа и проектирования; 70 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г.  инструменты планирования и управления проектом;  инструменты рефакторинга кода;  инструменты реинжиниринга;  генераторы кода;  инструменты для построения UML-диаграмм. UML (Unified modeling language — унифицированный язык моделирования) – это стандартизированный язык объектного моделирования с помощью графических примитивов. Примерами CASE-средств, часто используемыми программистами, могут служить сле- дующие программные продукты: комплект программ Rational Software компании IBM, Erwin компании CA Technologies, Enterprise Architect компании Sparx Systems. Наиболее универсальными ИСР ПО можно считать программные платформы. Программной платформой называют набор инструментальных средств в виде библиотек API (программного интерфейса приложений), позволяющих быстро создавать ПО, и средств компиляции и выполнения созданных приложений. Программной платформой можно назвать средства разработки корпоративных систем от компании 1С или систему разработки сайтов Drupal, однако мы будем говорить об универсальных программных платформах, предназначенных для создания и выполнения ПО различного назначения. Наиболее распространёнными и популярными на данный момент программными платформами являются платформа .NET от компании Microsoft и платформа Java от компании Sun Microsystems. Помимо этих двух платформ в поле нашего зрения попадёт программная платформа Eclipse, базирующаяся на Java, но предлагающее оригинальную концепцию модульного построения ПО. .NET Framework — программная платформа компании Microsoft, предназначенная для создания программ и веб-приложений. Основой платформы является исполняющая среда Common Language Runtime (CLR), способная выполнять настольные программы, сетевые клиент-серверные приложения и серверные веб-приложения. Основной идеей .NET Framework является поддержка создания программ, написанных на разных языках программирования. Такая гибкость обес- 71 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. печивается за счёт предварительной компиляции кода в промежуточный язык (байт-код, Common Intermediate Language (CIL)), который затем исполняется в среде CLR. Основными языками программирования, используемыми в .NET Framework, являются Visual C++, Visual C# и Visual Basic .NET. Платформа .NET Framework предоставляет набор стандартных технологий и библиотек, которые позволяют реализовывать приложение любого назначения. При всех очевидных преимуществах, платформа .NET обладает существенным недостатком – это привязка к операционным системам Microsoft Windows. Однако следует отметить, что существует независимый проект Mono, который успешно пытается реализовать .NET на Unix-подобных операционных системах. Среды разработки .NET приложений:  Microsoft Visual Studio (C#, Visual Basic .NET, Managed C++, F#),  SharpDevelop,  MonoDevelop. Отличием платформы Java является её кроссплатформенность, то есть возможность выполнять программный код на любых операционных системах. Известно, что Javaприложения исполняются как на мобильных телефонах, так и на серверах. Программная платформа Java — это пакет инструментальных средств от компании Sun Microsystems, которые позволяют разрабатывать и запускать программы, написанные на языке программирования Java и некоторых других языках, способных выполняться в виртуальной машине Java (JVM), реализованной для различного аппаратного обеспечения и различных операционных систем. Выделяют следующие компоненты платформы Java:  Java Card – технология для исполнения Java-приложений на смарт-картах и других подобных устройств c малым объёмом памяти.  Java ME – наборы библиотек для разработки приложений для мобильных устройств, КПК, ресиверов цифрового телевидения и принтеров.  Java SE – для использования на настольных ПК, серверах и другом подобном оборудовании.  Java EE – набор библиотек и технологий для реализации корпоративных приложений, в том числе многопоточных и клиент-серверных. В связи с огромным количеством библиотек и технологий, используемых при разработ- ке на Java, приходится учитывать много факторов, которые могут повлиять на разработку 72 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. программ для различных операционных систем. Особенно острым вопросом является реализация графического интерфейса пользователя для кроссплатформенных решений. Решение данного вопроса предлагает платформа разработки Eclipse. Eclipse Platform — свободная платформа для модульных кроссплатформенных приложений, реализованная на Java, которая предоставляет средства для построения средств разработки ПО и создания кроссплатформенных приложений с графическим пользовательским интерфейсом. Развивается и поддерживается Eclipse Foundation. В основе платформы Eclipse лежит каркас, который расширяется при помощи плагинов. Такой подход позволяет создавать графические приложения, не задумываясь о тонкостях реализации графического интерфейса и особенностях интеграции различных компонентов программы. Eclipse Project — собственно проект Eclipse, включает в себя:  Eclipse Platform — каркас.  Plug-in Development Environment — инструмент расширения Eclipse-платформы посредством Eclipse-плагинов.  Java Development Tools (JDT) — инструмент разработки Java-программ и Eclipseплагинов в частности.  Rich Client Platform — платформа расширенного клиента, минимальный набор плагинов для построения программы с графическим интерфейсом.  SWT (JFace) – библиотеки реализации кроссплатформенного графического интерфейса, которые позволяют создать: o рабочее пространство, o инструменты, o компоновки (перспективы), o редакторы, o представления, o проекты, o плагины, o мастера. Приведём основные определения, позволяющие понять концепцию графического интерфейса Eclipse, из учебного пособия Казарина С. и Клишина А. [14]. 73 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Рабочее пространство (workspace) — это каталог для проектов пользователя, в котором располагаются файлы проекта. Все, что находится внутри этого каталога, считается частью рабочего пространства. Инструментальные средства Eclipse становятся доступны сразу после запуска приложения. Это по существу сама платформа с набором различных функциональных возможностей главного меню, где прежде всего выделяется набор операций по управлению проектом. Фактическая обработка, как правило, осуществляется дополнениями (плагинами). К инструментам (workbench) относится набор соответствующих редакторов и представлений, размещенных в рабочей области Eclipse. Для конкретной задачи определенный набор редакторов и представлений называют перспективой или компоновкой. Компоновка (perspective) — это набор представлений и редакторов, расположенных в том порядке, который вам требуется. В каждой компоновке присутствует свой набор инструментов, некоторые компоновки могут иметь общие наборы инструментов. Редакторы представляют собой программные средства, позволяющие осуществлять операции с файлами (создавать, открывать, редактировать, сохранять и др.). Представления по существу являются дополнениями к редакторам, где выводится информация сопроводительного или дополнительного характера, как правило, о файле, находящемся в редакторе. Проект (project) представляет собой набор файлов приложения и сопутствующих дополнений. При работе с Java используются в основном файлы, имеющие следующие расширения: .java, .jsp, .xml. Дополнением (plug-in) называют приложение, которое дополнительно может быть установлено в Eclipse. Мастер — это программное средство, которое помогает пользователю в настройках и проведении сложной операции. В Eclipse имеется множество различных мастеров, которые делают работу пользователя в системе удобной и эффективной, беря часть рутинных операций на себя. Примером мастера может выступить мастер создания нового класса, который помогает пользователю в таких операциях, как создание нового файла в нужной директории, создание начального кода класса, автоматическая расстановка модификаторов и т.д. Наиболее известными плагинами являются так называемые IDE-плагины, реализующие полноценную интегрированную среду разработки: Java plug-in, C/С++ plug-in, PHP plugin. Базовым и очень удобным инструментом реализации программного обеспечения являются интегрированные среды разработки. 74 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Интегрированная среда разработки (англ. IDE, Integrated development environment или integrated debugging environment) — система программных средств, включающая взаимосвязанные инструменты разработки ПО для удобного и быстрого создания приложений. Мы уже неоднократно упоминали это понятие выше и отмечали, что состав IDE может существенно различаться для сред разработки различного уровня. Например, среда разработки на языке Python – IDLE – содержит лишь базовые элементы, упрощающие программирование. Ещё большее различие можно отметить для IDE различного назначения. Рассмотрим состав IDE для настольных и сетевых приложений и IDE для веб-приложений. IDE для настольных и сетевых приложений обычно включает:  текстовый редактор;  компилятор (интерпретатор);  средства автоматизации сборки;  отладчик;  браузер классов, инспектор объектов и диаграмму иерархии классов;  среды визуальной разработки, которые включают возможность визуального редактирования интерфейса программы. Аналогичный состав ИСР у IDE общего назначения. Примерами таких IDE являются Eclipse, NetBeans, Embarcadero RAD Studio, Qt Creator, Microsoft Visual Studio. IDE для разработки веб-приложений обычно включает:  редакторы гипертекста;  графические редакторы и конверторы изображений;  средства мультимедиа (аудио, анимация, видео);  системы программирования клиентских приложений;  средства программирования серверных приложений. В качестве примеров можно привести среды Apatna, Microsoft Expression Studio. Важное значение при разработке ПО уделяется пользовательским интерфейсам, по- скольку удобство пользования программным продуктом напрямую влияет на успешность разработанного ПО. Именно поэтому зачастую выделяют отдельную специальность – разработчик пользовательского интерфейса. Особенности пользовательского интерфейса определяются на этапе прототипирования. Прототипирование ПО (от англ. prototyping) — создание прототипа (макета) программы с целью представления функциональности программы 75 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. заказчику на ранних этапах процесса разработки ПО, а также для проверки архитектурных и интерфейсных решений. Обычным подходом при разработке прототипа ПО является итерационное выполнение следующих этапов:  определение начальных требований;  разработка макета пользовательского интерфейса системы;  изучение прототипа заказчиком и конечными пользователями, получение обратной связи о необходимых изменениях и дополнениях;  переработка прототипа с учетом полученных замечаний и предложений. К инструментами поддержки прототипирования можно отнести следующие программы: SketchFlow – инструмент прототипирования для Microsoft Expression Blend; Pencil Project; MockFlow; Axure RP. Некоторые из перечисленных программ позволяют не просто создать прототип пользовательского интерфейса, но и добавить интерактивные элементы, имитирующие работу программы, а также позволяют автоматически сформировать первоначальный программный код. При описании ИСР ПО невозможно обойти вниманием ещё один набор библиотек для разработки кроссплатформенных приложений. Qt — кроссплатформенный набор ИСР ПО для реализации приложений на языке программирования C++, а также на некоторых других языках программирования: Python — PyQt, PySide; Ruby — QtRuby; Java — Qt Jambi; PHP — PHP-Qt и другие. Главное преимущество Qt состоит в том, что ПО, написанное с его помощью, можно компилировать отдельно для каждой операционной системы, при этом изменять исходный код не требуется. Таким образом, обеспечивается независимость кода от платформы и максимальная эффективность приложений за счёт компиляции для каждой операционной системы. Для реализации наиболее используемых возможностей и технологий Qt содержит набор классов для реализации графического интерфейса, для работы с сетью, базами данных и XML. До настоящего момента, говоря о ПО, мы не заостряли внимание на архитектурных особенностях построения ПО, как системы взаимосвязанных, но логически обособленных компонентов. Одним из наиболее актуальных подходов для реализации сетевых модульных приложений является сервис-ориентированная архитектура. 76 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Сервис-ориентированная архитектура (англ. SOA, service-oriented architecture) — модульный подход к разработке ПО, основанный на использовании сервисов (служб) со стандартизированными интерфейсами. SOA – это не конкретная технология, а архитектурная концепция, основными принципами которой являются: повторное использование кода; лёгкая масштабируемость программных систем; независимость от платформ и языков разработки программного кода; слабая связность компонентов системы; единообразный программный интерфейс для взаимодействия сервисов друг с другом. Такой подход позволяет строить сложные многокомпонентные системы, образующие единое пространство сервисов. Наиболее известными инструментами для реализации сервис-ориентированного подхода являются следующие программные компоненты: Intel SOA Expressway, JBoss SOA Platform, IBM WebSphere, Software AG webMethods, Oracle/BEA Aqualogic, Microsoft Windows Communication Foundation, SAP NetWeaver, TIBCO, Diasoft. Схема возможной реализации SOA представлена на рисунке 4.1. Рисунок 4.1. Схема реализации сервис-ориентированной архитектуры ПО предприятия. 77 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Помимо знания различных технологий и ИСР следует учитывать особенности самих языков программирования, на которых написан код. Рассмотрим наиболее популярные языки программирования. Язык программирования (ЯП) — формальная знаковая система, при помощи которой записываются компьютерные программы. Прежде чем перейти к рассмотрению конкретных ЯП, приведём классификацию ЯП: ЯП принято различать по следующим основным признакам:  по парадигме: o императивные; o декларативные; o    функциональные;  логические; объектно-ориентированные; по сфере применения: o для настольных приложений; o для клиент-серверных приложений; o для веб-приложений; по типизации переменных: o со статической типизацией; o с динамической типизацией; Со сферами применения и типизацией мы уже достаточно хорошо знакомы, а парадигмы рассмотрим подробнее. Императивное программирование описывает процесс решения задачи в виде инструкций, изменяющих состояние программы. То есть код в императивных языках программирования представляет собой последовательность команд. Как правило, императивное программирование реализуется посредством основных алгоритмических конструкций и подпрограмм. Примерами ЯП, поддерживающими парадигму императивного программирования С/C++, Java, C#, Python. Объектно-ориентированное программирование (ООП) является в некотором смысле расширением императивного подхода. Отличительной особенностью ООП является использование понятий классов и объектов, состояние которых изменяется при решении задачи. Объектно-ориентированный подход подробнее рассмотрен в 3 главе. 78 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Примерами ЯП, поддерживающими парадигму объектно-ориентированного программирования, являются Objective C, C++, Java, C#, Python. Императивному программированию принято противопоставлять декларативное программирование (ДП). Особенность ДП в том, что при использовании данной парадигмы описывается не способ решения задачи, а желаемый результат. Например, с помощью языка XAML можно описать пользовательский интерфейс, а не процедуру его построения. Подмножеством ДП являются функциональное и логическое программирование. Языки функционального программирования представляют решение задачи в виде композиции функций, при этом состояние программы и переходы не задаются в явном виде, в отличие от императивного программирования. Наиболее распространённым языком, реализующим многие элементы функционального программирования, является JavaScript. Следует отметить также языки Lisp, Haskell, Erlang. C# и Python также поддерживают элементы парадигмы функционального программирования. Логическое программирование — парадигма программирования, основанная на автоматическом доказательстве теорем с помощью математической теории множеств. Самый известный язык логического программирования – Prolog, основными понятиями которого являются факты, правила логического вывода и запросы, позволяющие описывать базы знаний, процедуры логического вывода и принятия решений. Как и в других декларативных языках, задача описывается в виде набора исходных условий и правил, а поиск решения осуществляется уже самой системой программирования Prolog без необходимости описания пошагового алгоритма. Рассмотрим наиболее популярные языки программирования, которые активно применяются для разработки настольных и сетевых приложений. C — стандартизированный процедурный язык программирования. Язык C был разработан в начале 1970-х годов сотрудниками Bell Labs Кеном Томпсоном и Денисом Ритчи как наследник языка B. C был создан для использования в операционной системе UNIX, в том числе и для написания ядра системы. Особенности языка C: 79 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г.  большинство возможностей языка вынесено в библиотеки;  использование препроцессора для определения макросов, включения исходных кодов других файлов и условной компиляции;  статическая слабая типизация: у всех данных есть фиксированные типы, но неявные преобразования разрешены;  разрешено определение пользовательских типов и составных типов;  предоставляется низкоуровневый доступ к памяти (через преобразование машинных адресов в типизированные указатели);  процедуры являются частным случаем функции, возвращающей специальный тип void;  файлы можно компилировать отдельно и линковать друг с другом, контролируя видимость функций и данных ключевыми словами static и extern. C++ — компилируемый статически типизированный язык программирования общего назначения. Создан Бьёрном Страуструпом, С++ представляет собой модификацию языка С. Наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования. Нововведения С++ в сравнении с С:  поддержка объектно-ориентированного программирования через классы;  поддержка обобщённого программирования через шаблоны;  дополнения к стандартной библиотеке;  дополнительные типы данных;  исключения;  пространства имён;  встраиваемые функции;  перегрузка операторов;  перегрузка имён функций;  ссылки и операторы управления свободно распределяемой памятью. C# (произносится си-шарп) — язык программирования, сочетающий объектно- ориентированные и контекстно-ориентированные концепции. Разработан в 1998—2001 годах группой инженеров под руководством Андерсa Хейлсбергa в компании Microsoft как основной язык разработки приложений для платформы Microsoft .NET. Компилятор с C# входит в стандартную установку самой .NET. Особенности языка C#:  синтаксис наиболее близок к C++ и Java; 80 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г.  строгая статическая типизация;  поддерживает полиморфизм;  перегрузка операторов;  указатели на функции-члены классов;  атрибуты, события, свойства, исключения;  комментарии в формате XML. Java — объектно-ориентированный язык программирования, разрабатываемый компа- нией Sun Microsystems. Особенности языка:  платформо-независимый язык;  Java предоставляет для широкого использования свои апплеты (applets);  богатый набор классов, которые обеспечивают создание независимых от используемой платформы абстракций для широкого спектра системных интерфейсов;  выполнение байт-кода на виртуальной машине Java;  автоматическое управление памятью;  унифицированный доступ к БД;  параллельное выполнение программ. Многие современные языки развиваются и оказывают взаимное влияние друг на друга, что приводит к сложностям в проведении сравнения языков и их классификации без учёта временного среза. К тому же для решения различных типов задач могут быть применены различные языки программирования в зависимости от большого количества факторов, поэтому все приведённые особенности языков просим считать условными. 4.2. Основы и особенности веб-разработки. HTML, XML, Flash, PHP Отдельным направлением в программировании является веб-программирование. Обособление ИСР веб-приложений в отдельный класс есть результат не только особых технологий сетевых приложений, но и бурного развития глобальной сети Интернет, а, следовательно, и возможности доступа пользователей к программам через браузер, независимо от аппаратной платформы. Как уже было показано выше, ИСР веб-приложений подразумевают принципиально различные инструменты для реализации клиентской и серверной частей приложения. На рисунке 4.2 представлены основные языки и фреймворки для разработки вебприложений. Фреймворком в программировании называют набор программных компонент, облегчающих разработку типового программного проекта. 81 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Рисунок 4.2. Наиболее популярные языки программирования и фреймворки для разработки веб-приложений. В основе любого сайта лежит язык гипертекстовой разметки – HTML. С помощью браузера веб-страница, написанная на HTML, отображается пользователю. Для динамического формирования содержимого веб-страниц необходимо использовать серверные скрипты, которые будут вызываться при обращении по определённому адресу URL. Для вызова серверных методов используются стандартные средства, заложенные в протокол HTTP, а также динамически вызываемые методы языка JavaScript, исполняемого в браузере. Следует отметить, что возможность продвинутых технологий, таких как Flash и SilverLight, позволяют использовать альтернативные методы построения динамических веб-приложений. Помимо перечисленных технологий, популярным серверным фреймворком является Django, позволяющий вести разработку на ЯП Python. Основой большинства веб-приложений служит трёхзвенная архитектура, которая и определяет ключевые особенности веб-приложений. Трёхуровневая архитектура (трёхзвенная) (англ. three-tier или Multitier architecture) предполагает наличие следующих компонентов приложения:  клиентское приложение (обычно говорят «тонкий клиент» или терминал),  сервер приложений,  сервер базы данных. В качестве примера можно привести следующую конфигурацию:  сервер БД представлен MySQL-сервером;  сервер приложений технологиями: ADO.NET, ASP.NET и web-сервером IIS;  роль клиента выполняет любой web-браузер. 82 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. В силу особенностей протокола HTTP, основным форматом обмена данными между клиентом и сервером является текст (строки). Для структурирования передаваемых данных и упрощения отображения их на объекты программного кода на сервере и в дерево гипертекстового документа в браузере используют иерархические текстовые форматы данных XML и JSON. XML (англ. eXtensible Markup Language — расширяемый язык разметки) — язык разметки для хранения и представления иерархически-организованных данных, используя стандартизированные синтаксические правила. XML — текстовый формат, предназначенный для хранения структурированных данных, для обмена информацией между программами, а также для создания на его основе более специализированных языков разметки. XML рекомендован Консорциумом всемирной паутины. JSON (англ. JavaScript Object Notation) — язык разметки и текстовый формат для обмена данными, основанный на JavaScript. Пример данных в форматах XML и JSON представлены на рисунке 4.3. Для обеспечение интерактивной обратной связи с сервером и визуализации элементов управления используют ЯП JavaScript, который исполняется в изолированной среде выполнения браузера. JavaScript — объектно-ориентированный скриптовый язык программирования с элементами функционального программирования и динамической типизацией. Является диалектом языка ECMAScript. 83 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Рисунок 4.3. Данные в форматах XML и JSON. JavaScript обычно используется как встраиваемый язык для программного доступа к объектам приложений. Наиболее часто JavaScript используется в браузерах для выполнения действий над элементами веб-страниц на стороне клиента, например, для динамических запросов к серверу, анимации и создания интерактивного интерфейса пользователя и др. Важное значение имеют технологии обратной связи с сервером. Базовая функциональность заложена в протокол HTTP, однако для придания интерактивности и оптимизации загрузки веб-приложения в браузере используют специальные методы, такие как AJAX. AJAX (Асинхронный JavaScript + XML) – инструмент для построения вебприложений, обменивающихся данными с сервером в фоновом режиме. При этом пользователь получает приложение с динамическим обновлением контента, без перезагрузки всей страницы [23]. Возможность построения веб-сервисов с открытым программным интерфейсом диктует следование определённым принципам построения распределённых веб-приложений. 84 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Representational State Transfer (REST) – это набор архитектурных принципов и стиль проектирования приложений, ориентированный на создание сетевых систем, в основе которых лежат механизмы для описания и обращения к ресурсам [35]. Примером такой системы может служить World Wide Web. Веб-службой REST называется такая веб-служба, которая основана на применении протокола HTTP и принципов REST. Принципы REST:  возможность получения к службе доступа с помощью простого URI,  поддержка в службе типов MIME,  применение различных методов HTTP. На рисунке ниже приведены методы, использованные в веб-службах REST. Удаляем матчи Рисунок 4.4. Пример использования методов веб-службы REST. Современные скорости передачи данных в сети Интернет и постоянно развивающиеся технологии позволяют на базе веб-приложений создавать программы, функциональность которых сопоставима со сложными настольными приложениями. Rich Internet application (RIA, «богатое Интернет-приложение») — приложение, доступ к которому осуществляется через интернет посредством браузера или расширений браузера и виртуальных машин, при этом пользовательский интерфейс предоставляет богатые возможности и функциональность, сопоставимую с настольными приложениями. Приложение RIA:  осуществляет обработку данных преимущественно на стороне сервера;  запускается в браузере, при этом может потребоваться установка дополнительного ПО, расширяющего возможности бразера;  запускается локально в среде безопасности. 85 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. В настоящее время наиболее распространенными платформами являются Adobe Flash, Java и Microsoft Silverlight с уровнем проникновения 95%, 78% и 63% соответственно по состоянию на осень 2011 года. Инструментарий для разработки RIA:  JavaFX;  Action Script;  HTML5+JavaScript;  Adobe Flash Builder;  Adobe Flex / AIR. Сейчас всё большее внимание уделяется переносу бизнес-приложений в сеть Интер- нет или в интранет с возможностью доступа с любых устройств. Некоторые технологии, которые обеспечивают данную возможность и используются для автоматизации распределения ресурсов веб-серверов, будут рассмотрены в главе 5. 86 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Глава 5. Актуальные технологии и методики разработки ПО В данной главе продолжим рассматривать инструменты и современные технологии, связанные с разработкой ПО, а также затронем некоторые вопросы методологий, применяемых в процессе разработки ПО. 5.1. Облачные и параллельные вычисления Основная идея облаков проста — централизованная сервисная организация предоставляет и поддерживает ИТ-сервисы, освобождая пользователей от решения операционных и административных задач [4]. Такие сервисные организации часто делят на категории в зависимости от того, предоставляют они программное обеспечение в виде сервиса, платформу в виде сервиса или инфраструктуру в виде сервиса. Очевидно, что идея доставки сервисов через коммуникационные каналы связи не нова, более того, уже несколько десятков лет подобные модели существуют и применяются: к ним относятся и клиент-серверные приложения, веб-приложения. Отличительной особенностью облачных технологий стало использование для реализации подобной модели высокоскоростных интернет-соединений, которые обеспечивают использование ресурсов распределённых серверов при централизованной системой администрирования. Облака предоставляют ряд преимуществ [17]:  экономия на содержании ИТ-инфраструктуры, которой у компании теперь может и не быть вовсе либо она будет сокращена до минимума;  доступ к облачным приложениям может осуществляться отовсюду, где есть интернет или интранет-сеть, если речь идёт о частном облаке;  облачная модель позволяет переложить необходимость обязательной сертификации программно-аппаратного комплекса к требованиям ФЗ-152 («О защите персональных данных») с потребителя сервисов на их поставщика. Облако (англ. Cloud) или облачные вычисления – это масштабируемая инфраструктура, которая предоставляет вычислительные ресурсы, ресурсы обработки данных и возможности для хранения информации в виде интернетсервиса. В данной формулировке, заимствованной из одного из докладов образовательного ви- део-портала компании Microsoft techdays.ru, ключевыми являются понятия ресурс и сервис. Выделяют глобальные (публичные) облака, доступные всем пользователям через интернет, и частные облака, которые применяются внутри сети организации. 87 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. На данный момент наиболее распространено деление всех облачных решений на три категории (рисунок 5.1): инфраструктура как сервис (Infrastructure as a Service, IaaS), платформа как сервис (Platform as a Service, PaaS) и программа как сервис (Software as a Service, SaaS) [17]. IaaS – сервис, абстрагирующий пользователя от работы с аппаратными ресурсами. В самом простом случае любой владелец центра обработки данных может продавать ресурсы своих физических серверов. Хотя наиболее часто, конечно, эти сервисы предоставляют функциональность ресурсов виртуальных машин. Примеры подобных сервисов: Amazon (EC2), Windows Azure (VM Role), виртуализация от VMware, Parallels и др. PaaS – предоставление услуг платформы в виде сервиса. Яркими примерами таких сервисов могут служить Amazon Cloud Computing и Microsoft Azure, предоставляющие схожую функциональность [17]:  возможность динамического масштабирования и распределения нагрузки;  оплата только за использованные ресурсы;  специализированные API для работы с оптимизированными для нужд масштабируемых приложений баз данных и средств обмена сообщениями;  услуги сети доставки контента (Content Delivery Network, CDN); и т. п. Рисунок 5.1. Уровни абстракции облачных сервисов. SaaS предоставляет прикладные сервисы непосредственно конечным пользователям. Из наиболее ярких примеров таких решений можно назвать Salesforce.com, Microsoft Office 365 и Google Apps. 88 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. При разработке программного обеспечения для облаков следует учитывать ряд особенностей, связанных со спецификой самой технологии [33]. Приложение в облаке — это всегда сервис, удаленно доступный через интернетканалы. Взаимодействие между клиентом и сервисом, расположенным в облаке, должно происходить с учетом возможных задержек и, при необходимости, обеспечивать повтор соединения и возобновление передачи данных, кэширование редко изменяемых данных. Динамичная инфраструктура, обеспечивающая эластичность облака, позволяет горизонтально масштабировать приложения, быстро изменяя количество одновременно работающих экземпляров. Поэтому не рекомендуется хранить состояние приложений в памяти или на локальных дисках, так как каждое следующее обращение к приложению может быть адресовано другому его экземпляру. Grid-вычисления стали предвестником облачных технологий. Концепция grid (грид), предусматривающая утилизацию временно неиспользуемых ресурсов для исполнения какой-либо программы, возникла в 90-х годах как способ получить доступ к высокопроизводительным приложениям, работающим на специализированных суперкомпьютерных узлах. Однако в узлах grid нет ничего особенного помимо их соединения с сетью. Узлы могут быть ноутбуками, серверами центров обработки данных, вычислительным кластером или встроенными микропроцессорами [38]. Определения понятия grid отличаются, однако общее в них – это возможность использования распределённых ресурсов для высокопроизводительных вычислений. В книге «Технологии грид», выпущенной в ИПМ им. М. В. Келдыша РАН, предлагается следующее определение понятия grid [32]: Грид — это концепция и технологии бесшовной интеграции в разных местах телекоммуникационной сети (т.е. распределенных) компьютерных систем для обеспечения эффективного использования ресурсов и решения прикладных задач принципиально нового уровня сложности. Разработка для грид требует специальных инструментальных средств. Globus Toolkit – набор программного обеспечения и служб, созданный партнерством Globus Alliance. Является базисом для построения грид и приложений для него. Решения, построенные на базе Globus Toolkit, работают с использованием сервис-ориентированной архитектуры (SOA). Применение грид может дать новое качество решения следующих классов задач [32]:  массовая обработка потоков данных большого объема;  многопараметрический анализ данных;  моделирование на удаленных суперкомпьютерах; 89 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г.  реалистичная визуализация больших наборов данных;  сложные бизнес-приложения с большими объемами вычислений. Производители грид-систем выделяют несколько уровней грид (рисунок 5.2): грид- кластер (для вычислений в рамках одной вычислительный сети предприятия), корпоративный грид (для вычислений в рамках удалённых подразделений одного предприятия), глобальный грид (для совместного использования вычислительных возможностей нескольких предприятий). Общий принцип работы грид-вычислений можно понять при изучении схемы на рисунке 5.3. В качестве клиентских машин могут выступать не только компьютеры пользователей системы (добровольный грид, сетевой кластер), но и высокопроизводительные серверы (кластер серверов). На схеме становится понятны принципиальные отличия облаков от грид-вычислений: при использовании grid-вычислений пользователи выдают вычислительное задание, а затем оно остается в очереди до тех пор, пока не станут доступны требуемые ресурсы, тогда как облако должно предоставлять требуемые ресурсы сразу; ресурсы облака предоставляются одним провайдером, тогда как в грид-вычисления предлагают объединение ресурсов всей федерации независимых провайдеров. Ко всему прочему, в облаках ресурсы и сервисы находятся на стороне провайдера, а грид-вычисления позволяют распределять ресурсы и сервисы по клиентским машинам. В настоящее время грид-вычисления наиболее востребованы в научных расчётах, в частности для решения задач ЦЕРНа и обработки результатов работы Большого адронного коллайдера. Рисунок 5.2. Уровни грид. 90 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Рисунок 5.3. Принцип работы грид-вычислений. 5.2. Обеспечение и контроль качества ПО Мы уже неоднократно упоминали о том, что в создании программных продуктов принимают участие не только программисты, реализующие код, но и специалисты узких направлений, осуществляющих обеспечение разных этапов жизненного цикла программного обеспечения, таких как проектирование, тестирование, внедрение, сопровождение, управление проектом в целом. Важным этапом в разработке программного продукта является отладка, тестирование и общий контроль качества ПО. Основные определения, представленные по теме качества ПО, получены из международных стандартов ISO и из материалов интернет-ресурса, посвящённого тестированию «Про тестинг» [24]. Качество ПО (Software Quality) – это совокупность характеристик программного обеспечения, относящихся к его способности удовлетворять установленные и предполагаемые потребности. На рисунке 5.4 представлена модель качества ПО из стандарта ISO 9126-1 [2], которая включает параметры обеспечения и контроля качества ПО. Обеспечение качества (Quality Assurance – QA) – это совокупность мероприятий, охватывающих все технологические этапы разработки, выпуска и эксплуатации программного обеспечения (ПО) информационных систем, пред- 91 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. принимаемых на разных стадиях жизненного цикла ПО, для обеспечения качества выпускаемого продукта. В рамках обеспечения качества осуществляется ряд мероприятий, связанных с контролем выполнения процессов производства ПО: бизнес-анализа, проектирования, разработки как кодирования, тестирования (в том числе тест-дизайн, тест-анализ и тестменеджмент), внедрения и эксплуатации. Инструментом обеспечения качества программного продукта на этапах разработки, тестирования и внедрения является контроль качества. Рисунок 5.4. Модель качества ПО (ISO 9126-1). Контроль качества (Quality Control – QC) – это совокупность действий проводимых над объектом тестирования в процессе разработки для получения информации об актуальном состоянии объекта тестирования в разрезах: «готовность продукта к выпуску», «Соответствие зафиксированным требованиям», «Соответствие заявленному уровню качества продукта». 92 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Контроль качества обеспечивается рядом мероприятий, применяемых как непосредственно к программному продукту, так и к бизнес-процессам создания программного продукта, а именно: тестирование, верификация, валидация. Тестирование ПО (Software Testing) – это одна из техник контроля качества, включающая в себя действия по планированию работ (Test Management), проектированию тестов (Test Design), выполнению тестирования (Test Execution) и анализу полученных результатов (Test Analysis). Верификация (verification) – это процесс оценки системы или её компонентов с целью определения удовлетворяют ли результаты текущего этапа разработки условиям, сформированным в начале этого этапа. Т.е. выполняются ли наши цели, сроки, задачи по разработке проекта, определенные в начале текущей фазы. Валидация (validation) – это определение соответствия разрабатываемого ПО ожиданиям и потребностям пользователя, требованиям к системе. Программисты отвечают за отладку ПО (исправление ошибок, возникающих в процессе разработки) и тестирование ПО на уровне программного кода. Выделяют несколько уровней тестирования ПО, которые обеспечивают различную глубину проверки разрабатываемого ПО: модульное, интеграционное и системное тестирование. Модульное тестирование (юнит-тестирование) — тестируется минимально возможный для тестирования компонент, например, отдельный класс или функция. Часто модульное тестирование осуществляется разработчиками ПО. Интеграционное тестирование — тестируются интерфейсы между компонентами, подсистемами. При наличии резерва времени на данной стадии тестирование ведётся итерационно, с постепенным подключением последующих подсистем. Системное тестирование — тестируется интегрированная система на её соответствие требованиям. Обычно для выполнения тестирования ПО применяются инструментальные средства автоматизированного тестирования, которые позволяют контролировать качество ПО в процессе программирования приложений. Причём некоторые средства позволяют тестировать не только программный код настольных приложений, но и пользовательский интерфейс, работоспособность сайтов, нагрузку и эффективность программных продуктов. Можно выделить следующие программы для автоматизированного тестирования: коммерческие SilkTest, QuickTest Pro, WinRunner, TestComplete, Rational Functional Tester, XDE Tester, Rational Robot; и open source-продукты Selenium, Watir, WatiN, HttpUnit, HtmlUnit, JUnit, NUnit. Инструменты модульного тестирования обычно встроены в крупные IDE, например, в Microsoft Visual Studio. 93 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. В некоторых методологиях программирования применяется техника разработки через тестирование (Test-Driving-Development – TDD), которая состоит в написании тестов для ещё не разработанных модулей и функций. Функция считается работоспособной, как только она проходит тест. Такой подход помогает лучше проектировать структуру программных объектов и проводить рефакторинг кода, если возникает в этом необходимость. 5.3. Средства коллективной разработки приложений Разработка программных продуктов включает несколько стадий, которые образуют жизненный цикл ПО. Обычно выделяют следующие стадии: постановка задачи и составление требований, анализ и проектирование, реализация, тестирование и отладка, внедрение, сопровождение. Однако переходы между этими стадиями и управление жизненным циклом разработки в целом осуществляются по-разному, в зависимости от того, какая методология управления разработкой ПО выбрана. Следует понимать, что разработка многокомпонентного программного продукта, а тем более информационной системы, требует участия специалистов разных профилей, причём это могут быть не только программисты, но и управленцы. Для того чтобы координировать действия всех участников проекта и эффективно исполнять все стадии разработки ПО, требуются специальные средства и методики. Software Forge, или «кузница кодов» – это расширяемая webплатформа, интегрирующая лучшие программные средства для совместной разработки программного обеспечения [21]. Самый известный проект такого рода – SourceForge, содержащий крупнейшую в мире коллекцию проектов категории open source. Две ключевые возможности интерфейса «кузницы кодов»: портфель проектов, в котором можно пролистать и найти интересный проект, и просмотр проекта, в котором разработчику предоставлены средства для работы над конкретным проектом. Разработчики, входя в конкретный проект, получают представление о размещении двух его основных информационных блоков: ссылки на инструменты для работы с проектом и информационный блок выбранного инструмента. Полноценные Forge-центры поддерживают весь цикл разработки программного обеспечения: сбор идей, определение проекта, управление проектом, управление конфигурациями, поддержка сборки (интеграции) продуктов и отслеживание ошибок. «Кузница» интегрирует все инструменты для перечисленных процессов в едином интерфейсе и облегчает переходы между ними. Во всех проектах используется один и тот же набор инструментов, так что разработчики могут легко переключаться с проекта на проект. 94 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. «Кузницы кодов» отличаются от CASE-средств тем, что специально спроектированы для открытой совместной работы и обеспечивают удобство поиска проектов, ознакомления с проектом по текстовым материалам и исходным кодам и участие в проекте в качестве добровольца. «Кузницы кодов» обычно выполняют следующие функции:  отслеживание ошибок,  управление конфигурациями,  управление версиями исходных кодов,  работа с задачами,  предоставление очередной версии ПО конечным пользователям,  форумы,  рассылки  wiki для совместной подготовки документации. Примерами Forge-центров могут служить CodePlex, Google code, GForge, SourceForge, git·hub. Некоторые web-сервисы нацелены на предоставление инструментов для управления проектами, совместной работы и постановки задач по проектам, без специализации на разработке ПО, к ним можно отнести Basecamp, TeamLab, Мегаплан. Одной из важных проблем коллективной разработки ПО является совместное редактирование файлов исходного кода, конфигураций и структуры разрабатываемых компонентов ПО, иными словами, совместное написание кода программного проекта. Для решения этой проблемы используются специальные программные средства – системы управления версиями, которые, как мы уже говорили, обычно включаются в состав forge-центров. Система управления версиями (СУВ, от англ. Version Control System, VCS или Revision Control System) — программное обеспечение упрощающее работу с изменяющейся информацией. Система управления версиями позволяет хранить несколько версий одного и того же документа, автоматизировать работу с историей файла (или группы файлов), обеспечить мониторинг изменений, синхронизацию данных и организовать защищенное хранилище проекта. Выделяют централизованные и распределённые СУВ. Отличие распределённых СУВ от централизованных состоит в том, что у каждого разработчика храниться полностью свой личный репозиторий (хранилище данных) всего проекта, который каждый может изменять по своему усмотрению, при этом общий центральный репозиторий тоже существует и на него равняются все разработчики, добавляя в него уже проверенный код. 95 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. СУВ выполняет две основные функции: 1. хранение всех предыдущие версий каждого файла; 2. объединение разных версий кода, то есть программисты могут независимо работать над кодом и затем объединять (merge) свои изменения. Текущая рабочая копия проекта называется ревизией. Операция фиксирования изменений в репозитории называют коммитом (commit). Программист может создать отдельную ветвь (branch) проекта, например, для того, чтобы протестировать альтернативный подход к решению задачи. Работа над версиями проекта может происходить не в хронологическом порядке. Разработка может вестись в нескольких параллельных ветвях (branches), которые могут сливаться (merge) и разделяться в любой момент проектирования. Любой версии документа можно присвоить специальную метку (тег), которая будет описывать набор файлов и их версию. Наиболее известными примерами могут служить централизованные СУВ: CVS (сейчас уже не актуальная в силу ограничений) и Subversion (SVN, наиболее популярная СУВ); и распределённые СУВ: Git и Mercurial. В состав Microsoft Team Foundation Server (программного продукта для совместной разработки) входит своя СУВ Team Foundation Version Control (TFVC). Выбор тех или иных подходов к управлению жизненным циклом проекта по разработке ПО связан с выбором методологии разработки ПО. Методологией разработки программного обеспечения называют набор взаимосвязанных методов, правил, техник, используемых при разработке ПО и отражающих жизненный цикл программного обеспечения. Выделяют несколько различных моделей, применяемых в методологиях разработки ПО: каскадные модели («водопад»), итерационные («водоворот») и спиральные модели, гибкие модели (agile). Каскадная модель (eng. waterfall model) предполагает последовательно расположенные этапы, при этом переход на каждый следующий этап осуществляется только после полного завершения работы над предыдущим, таким образом, этапы не пересекаются по времени. Каскадная модель содержит следующие этапы разработки ПО [25]: Разработка требований (requirements): сбор бизнес-требований заказчика и их преобразование в функциональные требования к программному продукту. 96 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Анализ и дизайн (analysis and design): разработка модели предметной области (domain model), проектирование схемы базы данных, объектной модели, пользовательского интерфейса и т.п. Реализация (implementation): создание продукта по спецификациям, разработанным на предыдущем этапе. Тестирование (testing): включает проверку соответствия функциональности программного продукта потребностям пользователей (validation), а также поиск дефектов в реализации. Развертывание (deployment): обучение пользователей, инсталляция системы, перевод в промышленную эксплуатацию. На рисунке 5.5 представлена схема каскадной модели. Похожий подход к управлению разработкой ПО предлагает методология разработки по ГОСТ, которую обычно применяют при реализации проектов, заказчиками которых являются государственные структуры. При этом надо понимать, что ГОСТы не описывают сам процесс разработки, а только формулируют предъявляемые к нему требования. Рисунок 5.5. Схема каскадной модели управления разработкой ПО. Для разработки ПО по ГОСТ могут использоваться следующие серии стандартов:  ГОСТы 19 серии (Единая система программной документации).  ГОСТы 34 серии (Комплекс стандартов на автоматизированные системы).  ГОСТ 12207 (Информационная технология. Процессы жизненного цикла программных средств). К особенностям данной методологии относят: 97 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г.  несколько строго определенных этапов,  по завершении каждого этапа – строго определённая документация, которая должна полностью соответствовать требованиям указанных стандартов,  каскадный подход,  высокий уровень формализации разработки,  используется в основном для государственных заказчиков. Каскадную модель применяют обычно на небольших проектах, когда не требуется сложная совместная разработка и все требования к разрабатываемому ПО известны и определены. В крупных проектах со множеством исполнителей каскадную модель в чистом виде как правило не применяют, однако имеет место быть гибридная модель, в основе которой лежит каскадная модель. Итерационная модель («водоворот», англ. iteration — повторение) — предполагает непрерывный анализ полученных на текущем этапе результатов и возможность возврата и изменения результатов предыдущих этапов работы. Как видно из определения, итерационная модель разработки ПО включает те же этапы, что и каскадная модель, с той разницей, что итерационная модель предоставляет возможность возврата к предыдущим этапам. Важными особенностями итерационной модели разработки являются следующие [36]:  модель состоит из последовательно расположенных этапов (точно так же, как и «водопад»);  каждый этап имеет обратную связь с предыдущими этапами;  исправление ошибок происходит на каждом из этапов, сразу при выявлении проблемы — это промежуточный контроль;  этапы перекрываются во времени по причине наличия обратной связи: следующий этап не начинается, пока не завершится предыдущий; при первом проходе по модели вниз, как только обнаружена ошибка, осуществляется возврат снизу вверх к предыдущим этапам, которые повлекли ошибку; таким образом, фактически этапы оказываются растянутыми во времени;  результат появляется только в конце разработки, как и в модели «водопад». Последний из приведённых пунктов является одним из главных отличий каскадной и итерационной методологий от рассматриваемых ниже спиральной и гибкой методологий. Ряд источников итерационной или итеративной моделью называют спиральную модель, по- 98 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. этому можно встретить другое название модели «водоворот» – это поэтапная модель с промежуточным контролем. На рисунке 5.6 представлена возможная схема разработки проекта с использованием итерационной методологии. Спиральная модель – очень похожа на итерационную модель. Разработка состоит из итераций, каждая из которых включает все этапы жизненного цикла ПО, при этом после каждой итерации фиксируется результат, который можно представить заказчику. Рисунок 5.6. Схема итерационной модели разработки ПО. Можно выделить следующие особенности спиральной модели разработки:  ПО создается по частям,  создание прототипа,  постепенное наращивание функционала, улучшение и переработка интерфейса, доработки и исправление ошибок,  уточнение требований в процессе разработки,  подходит для больших и очень сложных проектов, а так же для проектов, требования к которым заранее не известны. Итерационная модель разработки также применяется при разработки крупных и слож- ных проектов, при этом требования могут изменяться в процессе разработки ПО. Схема спиральной методологии разработки представлена на рисунке 5.7. 99 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Рисунок 5.7. Схема спиральной модели разработки ПО. Наиболее часто используемыми примерами спиральной методологии являются методологии RUP от компании IBM и MSF от компании Microsoft. RUP (Rational Unified Process) – методология, которая поддерживается компанией IBM Rational Software. В качестве языка моделирования в общей базе знаний используется язык Unified Modelling Language (UML). Язык UML служит для описания объектов и сущностей решаемой задачи с помощь графических диаграмм специального вида. Разработка по методологии RUP вклячает 4 основные фазы: 1. Inception (исследование, начало), 2. Elaboration (уточнение плана, проектирование), 3. Construction (конструирование, построение), 4. Transition (внедрение, развертывание). MSF (Microsoft Consulting Services) – методология, предлагаемая корпорацией Microsoft. MSF описывает управление людьми и рабочими процессами в процессе разработки решения. MSF представляет собой согласованный набор концепций, моделей и правил. Модель процессов включает основные фазы процесса разработки:  Выработка концепции (Envisioning),  Планирование (Planning),  Разработка (Developing),  Стабилизация (Stabilizing), 100 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г.  Внедрение (Deploying). После окончания каждого цикла из всех фаз мы имеет готовый протопит продукта или полностью рабочий на данный момент продукт. Такой же принцип лежит в основе использования гибких методологий разработки. Гибкая методология разработки (англ. Agile) — методология, ориентированная на итеративную разработку и минимальную формализацию процесса [12]. Из-за ориентированности гибких методологий на результат, а не на формальное выполнение проекта, гибкие методологии часто называют методологиями быстрой разработки ПО. Особенности гибких методологий:  ориентированность на людей – как разработчиков, так и заказчиков, то есть и заказчики и исполнители должны быть вовлечены в процесс разработки наиболее комфортным для них образом,  использование устных обсуждений вместо большого количества документации, более того, некоторые гибкие методологии предписывают проведение регулярных (довольно частых) обсуждений текущего состояния проекта,  короткая продолжительностью итерации, которая обычно длится от двух до четырех недель,  результат каждой итерации – “полноценная” работающая версия продукта, в данном случае имеется в виду наличие работоспособного ПО с необходимыми реализованными функциями, которое можно демонстрировать заказчику  ожидание изменений, причём изменения могут быть сделаны на сколь угодно позднем этапе проекта. Гибкие методологии обычно применяются для проектов средней сложности, которые необходимо реализовать в короткий промежуток времени, при этом требования к ПО могут изменяться в любой момент. Над такими проектами обычно работают небольшие команды – до 10 человек. Гибкие методологии можно применять и в реализации сложных и долгосрочных проектов, однако при этом необходимо использовать гибридные методологии, например, совместно со спиральной методологией RUP, которая позволяет документировать все изменения сложного проекта и управлять проектом целиком, используя мощный инструмент представления всех компонентов проекта в виде UML-диаграмм. Наиболее востребованными гибкими методологиями разработки являются экстремальное программирование (XP) и Скрам (Scrum). 101 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Экстремальное программирование (XP) состоит в исполнении 12 основных принципов:  игра в планирование (Planning Game);  переработки кода (refactoring), упрощающие дальнейшую разработку и повышающие удобочитаемость и эффективность кода;  короткие релизы, в среднем от 2 до 4 недель;  метафоры, описывающие разрабатываемые модули проекта;  простой дизайн, позволяющий разрабатывать быстро;  разработка через тестирование (TDD);  коллективное владение кодом, уменьшающее риски, связанные, например, с внезапной болезнью программиста;  парное программирование, которое по статистике не приводит к увеличению времени и затрат на разработку, но значительно повышает качество кода;  продолжающаяся интеграция, предусматривает создание новых актуальных версий продукта несколько раз в день;  40-часовая рабочая неделя;  постоянная вовлеченность заказчика в процесс разработки;  стандарты написания кода, которые обеспечивают, в частности, успешное применение парного программирования и коллективное владение кодом. Следует пояснить, что основная цель игры в планирование — быстро сформировать приблизительный план работы и постоянно обновлять его по мере того, как условия задачи становятся все более четкими. Артефактами игры в планирование является набор бумажных карточек, на которых записаны пожелания заказчика (customer stories), и приблизительный план работы по выпуску следующих одной или нескольких небольших версий продукта. Игра в планирование обычно происходит один раз в начале каждой следующей итерации, при этом определяются ответственности сторон в реализации проекта. Одинаковое понимание задач программного продукта в целом и отдельных модулей и программистами, и заказчиками осуществляется за счёт применения метафор [9]. Успешность применения методологии экстремального программирования зависит от чёткого понимания, каким образом и какую конкретно пользу проекту может принести каждая из техник, применяемых в XP. Scrum — это методология гибкой разработки для небольших команд. Методология Scrum основана на коротких итерациях — спринтах, которые обычно составляют 3–4 недели. После выполнения каждого спринта к программному продукту добав- 102 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. ляются новые функции в соответствии с расставленными заранее приоритетами, определяемыми заказчиком. Scrum выделяет три проектных роли: владелец продукта, скрам-мастер и команда. Члены команды сами выбирают себе задачи из списка задач (backlog), назначенных на итерацию, и согласовывают свои действия на обязательных ежедневных коротких совещаниях (митингах). Такой подход позволяет быстро выявлять возникающие проблемы и проводить разработку в короткие сроки. Весь процесс разработки с использованием методологии Scrum представлен на рисунке 5.8. В целом, выбор той или иной методологии разработки ПО определяется многими факторами, которые надо проанализировать и оценить до начала разработки: это и наличие или отсутствие конкретных документированных требований к разрабатываемому ПО, и сложность ПО, и предполагаемые сроки разработки, и наличие ограничений бюджета разработки. Даже не используя одну из методологий целиком, можно почерпнуть полезные техники, внедрение которых в ваш проект позволит ускорить и оптимизировать процесс создания программного продукта. Рисунок 5.8. Схема методологии разработки ПО Scrum. 103 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Глава 6. Автоматизация выполняемых повседневных задач при помощи технологий программирования (макросы, скрипты, визуальные средства программирования) 6.1. Скриптовые языки В операционных системах обычно существует специальный скриптовый язык, обычно называемый языком командного интерпретатора. Скриптовые языки операционных систем имеют свои особенности и специфику. Например. в операционной системе Windows используется командный язык cmd, который позволяет решать несложные задачи автоматизации, а в системах Unix – shell и bash, обладающие достаточно сложным синтаксисом и громоздкостью, но обеспечивающие более мощные инструменты для работы с ресурсами системы. Главным недостатком большинства командных интерпретаторов является сложность кодирования простых алгоритмов и недостаточная развитость инструментальных средств для задач автоматизации, особенно это касается задач автоматизации средней сложности. Существуют более продвинутые скриптовые языки для обеспечения автоматизации: это, например, PowerShell для Windows. Если на примере командного интерпретатора попытаться понять, что такое скрипт, то становится очевидно, что скрипт организует работу с объектами и с помощью команд, выполнение которых реализовано средствами самой операционной системе. Скриптовый язык лишь обращается к этим средствам через программный интерфейс взаимодействия. Скрипт – программа, осуществляющая управление объектами и операциями, реализованными в другой программе. Скриптовым языком (языком сценариев) можно назвать язык программирования, предоставляющий удобные синтаксис, средства и библиотеки для взаимодействия с программой, предоставляющей набор команд. Зачастую эти команды можно выполнить «вручную» стандартными средствами пользовательского интерфейса приложения, скрипт позволяет автоматизировать выполнение последовательности команд. Примерами таких языков являются JavaScript (позволяет выполнять различные действия над веб-страницей, отображаемой в браузере), ActionScript (позволяет управлять объектами во флеш- приложениях). Приведённые примеры реализуют встраивание (embedding) возможностей скриптового языка в программу, предоставляющую функциональность скрипту. 104 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Принято выделять универсальные скриптовые языки, которые обладают собственной средой программирования и исполнения кода, независимой от автоматизируемых программ, и встраиваемые скриптовые языки, исполнение которых осуществляется самой программой (например, браузером исполняется JavaScript, а в MS Office исполняются скрипты на VBA). Среди известных универсальных скриптовых языков можно назвать Python, Perl, Lua и Ruby. Особенностями этих и других скриптовых языков являются простота синтаксиса, взаимодействие с файлами и процессами операционной системы, а также удобный инструментарий для работы со строками (парсинг, регулярные выражения и другое). Отличное описание применения языка Python для автоматизации задач администрирования Linux приведено в статье с сайта IBM DeveloperWorks [20]. Автор статьи Екатерина Марценюк проводит сравнение командного интерпретатора bash и Python. Примеры и описание использования в этой главе взяты из данной статьи. Python – удобный инструмент для решения задач системного администрирования, как повседневных, так и более специфических. Он одинаково подходит для создания как скриптов, так и более сложных приложений, в особенности сетевых, а также может служить заменой стандартному shell в Linux. В обязанности любого системного администратора входит решение большого количества разнообразных задач, призванных «облегчить жизнь» как ему самому, так и пользователям. То, с чем приходится сталкиваться постоянно, – мониторинг серверов или отдельных процессов, резервное копирование баз данных, просмотр логов с последующей выборкой необходимой информации, настройка и совершенствование системы информационной безопасности, заведение и редактирование пользовательских учетных записей и т.д. [20] Стоит отметить, что возможности командного интерпретатора зачастую используются не полностью. Многие администраторы выбирают Bash для написания простых или средних по сложности скриптов, а более крупные проекты или специфические задачи, где требуется работа с разнообразными входными данными, многомерными массивами, сокетами доверяют Perl, Python или Ruby. Python является подходящим инструментарием для решения следующих задач администрирования [20]:  парсинг лога или конфигурационного файла с использованием регулярных выражений;  разработка приложений, в том числе нестандартных, для работы с базами данных MySQL, Oracle, PostgreSQL, Sybase и др.;  сбор и анализ статистики интернет-трафика с нескольких IP-адресов;  преобразование данных в различные форматы, например, конвертация .ini-файлов в текст при помощи модуля ConfigParser; 105 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г.  работа с файлами сервера при помощи FTP-клиента;  поднятие простого прокси-сервера;  мониторинг работоспособности сервиса, запущенного на сервере, с отправкой предупреждений на e-mail администратора в случае сбоя;  поднятие ppp-соединения с использованием программы автодозвона;  поиск дубликатов с запросом на удаление или перемещение в каталоге с большим количеством файлов;  проверка целостности архивов бэкапа при помощи алгоритма md5;  и т.д. К средствам автоматизации относятся макросы – специальные скрипты, имитирующие действия пользователя при работе с системой. Для каждой операционной системы графической оболочки существуют свои средства создания макросов. Наиболее распространённые средства автоматизации и создания макросов для Windows: AutoIt, AutoHotKey. Обычно средства автоматизации и создания макросов выполняют следующие функции [13], [10]:  Создание графических интерфейсов GUI, информационных сообщений, форм ввода информации.  Перехват и эмуляция клавиатурных нажатий и кликов мышки.  Запуск консольных приложений и доступ к стандартным потокам ввода/вывода.  Работа с реестром Windows, буфером обмена, файлами (чтение, изменение, копирование, удаление).  Работа с протоколами TCP и UDP.  Автоматизация работы в браузерах: Internet Explorer, Opera, Firefox.  Переназначение клавиш, глобально или у отдельных программ.  Слежение за системой, автоматическое выполнение некоторых действий по желанию пользователя, таких как напоминание, сканирование или бэкап. Перечисленные функции выявляют ещё одно назначение средств автоматизации – это проведение и автоматизация тестирования программ, сайтов и пользовательского интерфейса. Такие распространённые задачи, как мониторинг веб-сайтов, мониторинг сетей, дефрагментация дисков, автоматизированная настройка компьютеров в сети и резервное копирование могут быть автоматизированы и скомбинированы в виде настроенной под пользователя утилиты, написанной на скриптовом языке или с помощью макроса. 106 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. 6.2. Инструментарий Python для автоматизации Данный пункт содержит примеры и их описание из статьи Екатерины Марценюк «Основы применения Python в администрировании Linux». Описываемые ниже примеры наглядно показывают, каким образом возможности Python используются как для решения повседневных задач (таких как создание дампа базы данных MySQL, получение статистики использования ресурсов сервера), так и для написания простого FTP-клиента, выполняющего поиск файлов по шаблону и скачивание их в локальный каталог [20]. Стандартный инструментарий Python позволяет системному администратору достаточно легко создавать полезные в работе скрипты или приложения вне зависимости, идет ли речь об операциях с файлами и каталогами (модули os, re, glob, fileinput, zipfile и др.), сетевых протоколах (модули socket, ftplib, urlib, poplib, imaplib, smtplib, telnetlib и др.) или базах данных (модули mySQLdb, cx_Oracle, psycopg2, Sybase и др.). Модуль socket позволяет создавать программные интерфейсы для обмена данными между процессами на стороне и клиента, и сервера. По умолчанию он поддерживает создание сокетов домена Internet для IPv4 (константа socket.AF_INET). При необходимости также есть возможность создать сокет домена UNIX (константа socket.AF_UNIX), если процессы локальны. Модуль socket участвует в создании различных сетевых приложений, например, в связке веб-сервер/браузер, почтовый сервер/почтовый клиент. Для системного администратора примером использования модуля socket может служить следующий скрипт srvstat.py: import os, re from socket import * class Srvstat: def __init__(self, host='serverhost.ru', port=52001): self.socket = socket(AF_INET, SOCK_STREAM) self.socket.bind((host, port)) self.socket.listen(5) def process(self): while 1: csocket, caddress = self.socket.accept() csocket.send('Connection established. Ready for request.\n') while 1: request = csocket.recv(64) if re.match('get\s+srvstat', request, re.IGNORECASE): csocket.send(os.popen('/usr/bin/vmstat 1 10').read()) csocket.send(os.popen('/usr/bin/netstat ta').read()) elif re.match('quit', request, re.IGNORECASE): break else: csocket.send('Unknown command.\n') csocket.close() 107 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. if __name__ == '__main__': serv = Srvstat() serv.process() Сервер serverhost.ru ожидает входящих соединений на порту 52001. При успешном подключении с использованием telnet он выдаст приглашение «Connection established. Ready for request» (Соединение установлено. Ожидается запрос). Единственную команду, которую сервер воспримет, будет get srvstat – она последовательно выведет информацию, полученную с помощью утилит vmstat и netstat. При попытке ввода любой другой команды будет выведено соответствующее уведомление «Unknown command» (Команда не найдена). Таким образом, администратор получит статистику использования ресурсов сервера за последние 10 секунд, а также сможет просмотреть список установленных и ждущих TCPсоединений. Выход осуществляется при помощи quit. Для реализации простого FTP-клиента в Python используется модуль ftplib. С его помощью можно просмотреть список файлов в заданном каталоге на ftp-сервере, скачать нужные файлы по заданному шаблону или, наоборот, закачать их на сервер – таким образом, модуль способен выполнять все основные функции, присущие FTP-клиентам. Конечно, чтобы не "изобретать велосипед", можно просто воспользоваться одним из множества уже написанных под Linux программ, например, NcFTP. Однако если задачи системного администратора более специфичны или выходят за пределы простых команд get/put, ftplib в сочетании с другими модулями Python может стать альтернативным решением проблемы. Приведенный ниже скрипт соединяется с сервером ftp и выводит список файлов из указанного каталога в соответствии с заданной маской поиска (в данном примере это все файлы с расширением *.php). После этого найденные файлы скачиваются в локальный каталог пользователя, и соединение закрывается: import os from ftplib import FTP ftpresource = 'ftp.somehost.ru' ftplogin = 'yourlogin' ftppassword = 'yourpass' todir = '/usr/home/myfiles/ftp' # задаем каталог на локальном компьютере, # куда будут # скачиваться файлы ftp = FTP(ftpresource) ftp.login(ftplogin, ftppassword) ftp.cwd('directory') # переходим в каталог, # откуда будем скачивать файлы for files in ftp.nlst('*.php'): ftp.retrbinary('RETR '+files, open(os.path.join(todir, files), 'wb').write, 1024) ftp.close() 108 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Взаимодействие языка Python с различными базами данных описывается в соответствующей спецификации – Python Database API 2.0. Благодаря универсальности используемых модулей базовая реализация доступа к базе данных, типов объектов, конструкторов и расширений применима для любой БД, поддерживаемой Python. Для обработки запросов базы данных, согласно спецификации, используются объекты подключения и объекты курсоров. В частности, доступ к базе реализуется при помощи метода connect(), к которому применяются соответствующие параметры базы: import mySQLdb db = mySQLdb.connect (db = 'dbname', host = 'host', user = 'dbuser', passwd = 'dbpasswd') При разработке интерфейса для работы с выбранной базой данных следует учитывать особенности ее параметров и корректировать метод connect() в соответствии с ними. В целом базовая структура интерфейса, написанная на Python, достаточно проста для понимания и реализации. Следующим шагом после подключения к базе является объявление объекта курсора (в терминологии БД курсором называется тот ее объект, который позволяет управлять контекстом выборки): cursor = db.cursor() Несмотря на то что некоторые БД, например MySQL, не поддерживают курсоры, они все равно будут эмулироваться, поэтому объявление объекта курсора в любом случае необходимо. После этого можно переходить к выполнению запроса: cursor.execute("select * from ANY_TABLE") Для получения результата запроса используется одна из следующих команд: cursor.fetchone() cursor.fetchall() # возвращает результат выборки построчно # возвращает полный результат выборки # и читает его построчно По окончании работы с базой необходимо завершить работу с курсором и закрыть соединение при помощи метода close(): cursor.close() db.close() Одной из основных задач системного администратора является организация резервного копирования базы данных. В сети существует достаточно много ресурсов, где выложены 109 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. подробные how-to, описывающие готовые backup-скрипты на Python. В частности, сама процедура создания дампа может выглядеть, например, следующим образом: import time, subprocess import mySQLdb mysql_dir = '/usr/bin/' backup_dir = '/usr/backup/dbarchive/' db = mySQLdb.connect(db='dbname', passwd='dbpasswd') cursor = db.cursor() cursor.execute("show databases") host='dbhost', user='dbuser', for db in cursor.fetchall(): command = '%s/mysqldump -u%s -p%s %s > %s%s-%s.sql' % (mysql_dir, dbuser, dbpasswd, db, backup_dir, db, time.strftime("%Y%m%d-%H:%M")) try: retcode = subprocess.call(command, shell=True) if retcode == 0: print "Dump completed" except Exception, e: print "Dump failed" 6.3. Визуальные средства программирования Визуальные средства программирования используются для разработки графических пользовательских интерфейсов (GUI – graphical user interface) и позволяют создавать код интерфейса путём создания элементов пользовательского интерфейса в графическом редакторе. Для разработки и проектирования пользовательского интерфейса используется инструменты визуального проектирования (экранный редактор, редактор форм и т.д.) которые позволяют выполнять следующие операции [27]:  размещение компонентов интерфейса в нужном месте;  задание моментов времени их появления на экране;  настройку связанных с ними атрибутов и событий. Практически все крупные IDE, позволяющие создавать GUI, включают инструменты ви- зуального проектирования. Рассмотрим принципы построения графического пользовательского интерфейса для различных платформ с помощью модуля tkinter, входящего в стандартный дистрибутив Python. Для создания оконного графического интерфейса необходимо понимать основные принципы программирования GUI. Базовым элементом является область (окно), на которой 110 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. располагаются различные элементы управления, которые реагируют на события, связанные с этими элементами управления. Окна и элементы управления обычно определяются, как экземпляры классов, описывающих свойства и методы этих объектов. Таким образом, программирование графического интерфейса базируется на парадигме объектно-ориентированного программирования. Особенность программирования графического интерфейса в том, что не предусмотрено выполнение алгоритма с начала до конца, но предусмотрен главный цикл программы, в котором реализовано реагирование элементов управления на действия пользователя и другие события. В данном случае речь идёт о парадигме событийно-ориентированного программирования, которое базируется на обработке событий: действий пользователя (клавиатура, мышь), сообщений других программ и потоков, событий операционной системы (например, поступление сетевого пакета). Как правило, событийно-ориентированное программирование реализуется выполнением главного цикла приложения, тело которого состоит из двух частей: выборки события и обработки события. Чтобы с помощью модуля tkinter создать окно, необходимо выполнить следующий код: from tkinter import * root = Tk() # создание объекта – главного окна root.title("Первое окно") # задание свойства – заголовок окна root.mainloop() # запуск главного цикла Можно задать и другие свойства окна, такие как, например, размер или позиция. Рассмотрим базовые элементы управления, которые можно разместить в окне: кнопка (Button), надпись (Label), текстовое поле (Entry), многострочное текстовое поле (Text), флажок (Checkbutton), радиокнопка (Radiobutton), список (Listbox), полоса прокрутки (Scrollbar). Кнопки служат для выполнения действий, надписи – для вывода неизменяемого текста, текстовые поля – для ввода текста, флажки – для множественного выбора альтернатив, радиокнопки – для выбора одной из альтернатив, списки – для выбора элементов из списка, полоса прокрутки – для перемещения по содержимому графического контейнера. Определение элементов управления в Python осуществляется в следующем формате: переменная = Класс_элемента (родительский_контейнер, [свойство=значение, … ]) Приведём пример размещения элементов управления на окне: 111 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. from tkinter import * root = Tk() # создание объекта – главного окна button1 = Button(root, text="Это кнопка", #надпись на кнопке width=30,height=5, #ширина и высота bg="white",fg="blue") #цвет фона и надписи label1 = Label(root, text="Это надпись", font="Arial 18") entry1 = Entry(root, width=20, bd=3) # поле ввода с шириной 20 и границей с толщиной 3 button1.pack() # размещение элемента управления label1.pack() entry1.pack() root.mainloop() # запуск главного цикла Аналогичным образом определяются другие элементы управления. Теперь необходимо определить события и обработчики. Одним из способов связывания элемента управления, события и функции, которая будет выполнена после возникновения события, является использование метода bind, который записывается в следующем формате: элемент_управления.bind(event, function) Параметр event записывается в виде строки, имеющей следующие возможные значения. События, производимые мышью:  – щелчок левой кнопкой мыши,  – щелчок средней кнопкой мыши,  – щелчок правой кнопкой мыши,  – двойной клик левой кнопкой мыши,  – движение мыши, и другие. События, производимые с помощью клавиатуры:  – нажатие клавиши Enter;  – пробел;  Сочетания клавиш, например: – одновременное нажатие клавиш Ctrl, Shift и z;  и другие. from tkinter import * def b1(event): root.title("Левая кнопка мыши") 112 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. def b3(event): root.title("Правая кнопка мыши") def move(event): root.title("Движение мышью") root = Tk() root.minsize(width = 500, height=400) root.bind('',b1) root.bind('',b3) root.bind('',move) root.mainloop() В этой программе меняется надпись в заголовке главного окна в зависимости от того двигается мышь, щелкают левой или правой кнопкой мыши. Подробнее со способами создания графического интерфейса с помощью модуля tkinter вы можете самостоятельно познакомиться в документации к модулю и по примерам в сети Интернет. Для реализации графического интерфейса в Python существуют другие библиотеки, например, wxPython или PyQT. Для каждой из библиотек существуют свои средства разработки, в том числе и инструменты визуального проектирования интерфейса. Например, для разработки с помощью библиотеки tkinter можно использовать Visual Tkinter Python IDE или Rapyd-Tk. 113 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Список рекомендуемой литературы и дополнительная литература 1. Фред Л. Дрейк мл. и др. Учебник Python 3.1. Документация на русском: http://ru.wikibooks.org/wiki/Учебник_Python_3.1 2. Г. Россум и др. Язык программирования Python, 2001. 3. Лутц М. Изучаем Python, 4-е издание. – Пер. с англ. – СПб.: Символ-Плюс, 2011. 4. Саммерфилд М. Программирование на Python 3. Подробное руководство. – Пер. с англ. – СПб.: Символ-Плюс, 2009. 5. Хахаев И. А. Практикум по алгоритмизации и программированию на Python: / И.А.Хахаев – М.: Альт Линукс, 2010. Сайт книги: http://books.altlinux.ru/PythonSchool/ 6. Чаплыгин А. Н. Учимся программировать вместе с Питоном, 2011. 7. Шапошникова С. Основы программирования на Python, 2011. Сайт книги: http://younglinux.info/python.php 8. Острейковский В. А. Информатика. – М.: Высшая школа, 1999. 9. Кнут Д. Искусство программирования. – М.: Мир, 1978. 10. Вирт Н. Алгоритмы + структуры данных = программы . – М.: Мир, 1985. 11. Колмогоров А.Н. Теория информации и теория алгоритмов. 12. Большой энциклопедический политехнический словарь. 2004. 13. Роберт У. Себеста. 1.7. Методы реализации // Основные концепции языков программирования = Concepts of Programming Languages / Пер. с англ — 5-е изд. — М.: Вильямс, 2001. 14. Першиков В. И., Савинков В. М. Толковый словарь по информатике / Рецензенты: канд. физ.-мат. наук А. С. Марков и д-р физ.-мат. наук И. В. Поттосин — М.: Финансы и статистика, 1991. 15. Глоссарий.ру 16. Страуструп Б. Основы программирования на C++. 17. Сайт IBM developerWorks: http://www.ibm.com/developerworks/ru/library 18. Сайт универсального десятичного http://teacode.com/online/udc/00/004.4'2.html 114 классификатора: Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. 19. ГОСТ 19781-90. Обеспечение систем обработки информации программное. Термины и определения. 20. ГОСТ 34.003-90. Информационная технология. Комплекс стандартов на автоматизированные системы. Автоматизированные системы. Термины и определения. 21. Казарин С.А., Клишин А.П. Среда разработки Java-приложений Eclipse: (ПО для объектноориентированного программирования и разработки приложений на языке Java): Учебное пособие. Москва 2008. — 77 с. 22. Фёдоров А. и Мартынова Д. Windows Azure – облачная платформа Microsoft. 23. Технологии грид. ИПМ им. М. В. Келдыша РАН. 24. Журнал «Открытые системы». 25. Ершов А.П. О человеческом и эстетическом факторах в программировании // Кибернетика. – 1972. – № 5. – с. 95-99. 115 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. Список использованных источников 1. Hetland M.L. - Python Algorithms. Mastering Basic Algorithms in the Python Language, 2010. 2. ISO 9126 (ГОСТ Р ИСО / МЭК 9126-93) — «Информационная технология. Оценка программного продукта. Характеристики качества и руководство по их применению».. 3. Бизли Д. Python. Подробный справочник. – Пер. с англ. – СПб.: Символ-Плюс, 2010. – 864 с. 4. Блэйк Д., Боренстейн Н. Стандарты для облаков: зачем и какие? – «Открытые системы» , № 06, 2011. 5. Большой энциклопедический политехнический словарь, 2004. 6. Глоссарий.ру // Глоссарий.ру. - http://www.glossary.ru. 7. ГОСТ 19781-90. Обеспечение систем обработки информации программное. Термины и определения. 8. ГОСТ 34.003-90. Информационная технология. Комплекс стандартов на автоматизированные системы. Автоматизированные системы. Термины и определения. 9. Гуйдо А.В. Технологии программирования: учебное пособие / А.В. Гуйдо; под ред. Б.М. Суховилова. – Челябинск: Издательский центр ЮУрГУ, 2010. 10. Документация к программе AutoHotKey [сайт] http://www.script- coding.com/AutoHotkeyTranslation.html. 11. Ершов А.П. О человеческом и эстетическом факторах в программировании // Кибернетика. – 1972. – № 5. – с. 95-99. 12. Закис А. RUP и другие методологии разработки ПО. Часть 2. Сравнение методологий разработки ПО. КомпьютерПресс, №11, 2006. 13. Ильин С. Секреты автоматизации. Несколько примеров того, как облегчить себе жизнь. Хакер № 01/10 (133). 14. Казарин С.А., Клишин А.П. Среда разработки Java-приложений Eclipse: (ПО для объектноориентированного программирования и разработки приложений на языке Java): Учебное пособие. Москва 2008. — 77 с. 15. Кнут Д. Искусство программирования. – М.: Мир, 1978. 16. Колмогоров А.Н. Теория информации и теория алгоритмов. 17. Кузькин М. Особенности разработки в облаках. «Открытые системы» , № 06, 2011. 18. Лутц М. Изучаем Python, 4-е издание. – Пер. с англ. – СПб.: Символ-Плюс, 2011. 19. Марков А.А. Теория алгорифмов.— Тр. матем. ин-та АН СССР им. В. А. Стеклова, 42, М. — Л.: Изд. АН СССР, 1954. 116 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. 20. Марценюк Е. Основы применения Python в администрировании Linux. Цикл статей. www.ibm.com. 21. Навех Б., Михайловский Б. и др. "Кузницы кодов" - инструмент взаимодействия разработчиков. «Открытые системы» , № 04, 2009. 22. Першиков В. И., Савинков В. М. Толковый словарь по информатике — М.: Финансы и статистика, 1991. 23. Пестречихин М. AJAX и jQuery. Динамическое обновление контента. Основы. [сайт]: http://codething.ru/ajax.php. 24. Про Тестинг - Обеспечение качества [сайт]: protesting.ru. 25. Рахимбердиев А. Современные процессы разработки программного обеспечения. RSDN Magazine #4, 2006. 26. Роберт У. Себеста. Основные концепции языков программирования = Concepts of Programming Languages / Пер. с англ — 5-е изд. — М.: Вильямс, 2001. 27. Романов А.В. Основы разработки программных средств в среде Delphi: учеб. пособие. / А.В. Романов. – Воронеж: ГОУВПО «Воронежский государственный технический университет, 2006. – 183 с. 28. Россум Г. и др. Язык программирования Python, 2001. 29. Сайт универсального десятичного классификатора: http://teacode.com/online/udc/00/004.4'2.html. 30. Саммерфилд М. Программирование на Python 3. Подробное руководство. – Пер. с англ. – СПб.: Символ-Плюс, 2009. 31. Страуструп Б. Язык программирования C++. 32. Технологии грид. ИПМ им. М. В. Келдыша РАН. 33. Фёдоров А. и Мартынова Д. Windows Azure – облачная платформа Microsoft. 34. Фред Л. Дрейк мл. и др. Учебник Python 3.1. 35. Хансон Д. Создание REST-сервисов. IBM DeveloperWorks [сайт]: http://www.ibm.com/developerworks/ru/edu/x-restatompp/section2.html. 36. Хаф Л. Методологии разработки программного обеспечения. КомпьютерПресс, №7, 2003. 37. Хахаев И. А. Практикум по алгоритмизации и программированию на Python: / И.А.Хахаев – М.: Альт Линукс, 2010. 38. Хи Д., Кастро-Леон Э. Grid виртуальных сервисов: интеграция ИТ с бизнес-процессами. «Открытые системы» , № 06, 2009. 39. Чаплыгин А. Н. Учимся программировать вместе с Питоном, 2011. 117 Московский технологический институт Платформы разработки и прикладные языки программирования Ляпин М.Г. 40. Яковлев С. Программирование на Python: Цикл статей. Источник: www.ibm.com. 41. Яковлев С. Работа со структурами данных в языках Си и Python. Цикл статей, www.ibm.com. 118