Рисунок 1. Модель с ограниченным числом состояний для пар "a".

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

К сожаления удовлетворительные методы для создания хороших моделей с конечным числом состояний на основании обpазцов строк еще не найдены. Один подход заключается в просмотре всех моделей возможных для данного числа состояний и определении наилучшей из них. Эта модель растет экспотенциально количеству состояний и годится только для небольших текстов [30,31]. Более эвристический подход состоит в построении большой начальной модели и последующем сокращении ее за счет объединения одинаковых состояний. Этот метод был исследован Виттеном [111,112], который начал с контекстно-ограниченной модели k-го порядка. Эванс [26] применил его с начальной моделью, имеющей одно состояние и с количеством переходов, соответствующим каждому символу из входного потока.

Моделирование и энтропия.

Одним из наиболее важных достижений в теории сжатия за последнее десятилетие явилась впервые высказанная в [83] идея разделения пpоцесса на две части: на кодировщик, непосредственно производящий сжатый поток битов, и на моделировщик, поставляющий ему информацию. Эти две раздельные части названы кодиpованием и моделированием. Моделирование присваивает вероятности символам, а кодирование переводит эти вероятности в последовательность битов. К сожалению, последнее понятие нетрудно спутать, поскольку "кодирование" часто используют в широком смысле для обозначения всего процесса сжатия (включая моделирование). Существует разница между понятием кодирования в широком смысле (весь процесс) и в узком (производство потока битов на основании данных модели).

Связь между вероятностями и кодами установлена в теореме Шеннона кодирования истоточника[92], которая показывает, что символ, ожидаемая вероятность появления которого есть p лучше всего представить -log p битами(1). Поэтому символ с высокой вероятностью кодируется несколькими битами, когда как маловероятный требует многих битов. Мы можем получить ожидаемую длину кода посредством усреднения всех возможных символов, даваемого формулой:

-S p(i) log p(i)

Это значение называется энтропией распределения вероятности, т.к. это мера количества порядка (или беспорядка) в символах.

Задачей моделирования является оценка вероятности для каждого символа. Из этих вероятностей может быть вычислена энтропия. Очень важно отметить, что энтропия есть свойство модели. В данной модели оцениваемая вероятность символа иногда называется кодовым пространством, выделяемым символу, и соответствует pаспpеделению интервала (0,1) между символами, и чем больше вероятность символа, тем больше такого "пространства" отбирается у других символов.

Наилучшая средняя длина кода достигается моделями, в которых оценки вероятности как можно более точны. Точность оценок зависит от широты использования контекстуальных знаний. Например, вероятность нахождения буквы "o" в тексте, о котоpом известно только то, что он на английском языке, может быть оценена на основании того, что в случайно выбpанных образцах английских текстов 6% символов являются буквами "o". Это сводится к коду для "o", длиной 4.17. Для контраста, если мы имеем фразу "to be or not t", то оценка вероятности появления буквы "o" будет составлять 99% и ее можно закодировать чеpез 0.014 бита. Большего можно достичь формируя более точные модели текста. Практические модели рассматриваются в разделах 1,2 и лежат между двумя крайностями этих примеров.

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

Набор прав

В этом случае некоторому пользователю дается (или не дается) право выполнять некоторую операцию. Так как операции и пользователи связаны отношением "многие - ко - многим" здесь потребуются уже три таблицы: "пользователи", "операции", "пользователь имеет право на операцию".

Необходимость контроля неизменности

Если не контролировать свойство неизменности, то его обеспечение будет целиком зависеть от квалификации программиста. Если же "неизменный" метод в процессе выполнения будет производить посторонние эффекты, то результат может быть самым неожиданным; отлаживать и поддерживать такой код очень тяжело. В качестве примера можно рассмотреть часть кода из библиотеки STL, поставляемой с компилятором Borland C++ 5.01 (файл memory.h):

Метод operator=() вместо операции присвоения выполняет операцию переноса указателя на объект, что позволяет написать вот такой странный код:

После выполнения операции присвоения одного объекта другому, вполне естественно ожидать их равенства, но в данном случае равенства не будет. Объект first_string не будет содержать объект типа string, которым был проинициализирован: при выполнении операции присвоения он был удален из first_string. В результате, текст "some text" будет напечатан только один раз в последней строке. operator=() обладает определенной семантикой; в частности, предполагается, что копируемый объект остается неизменным. Однако в данном случае выполняются действия, которые не совпадают с этой семантикой. Если бы интерфейс был описан верно (параметр rhs метода operator=() был неизменным), то подобная ошибочная реализация была бы невозможна. Вариант такого решения предлагает библиотека STL, поставляемая с компилятором Visual C++ 6.0; он также является хорошим примером несовпадения логической и физической неизменности.

Допустим, метод get() объекта auto_ptr не объявлен как неизменный. В этом случае была бы возможна ошибочная реализация:

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

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

Объекты

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

Ограничения по памяти.

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

Простейшей стратегией является прекращение адаптации модели после заполнения всей памяти[108]. Сжатие продолжается под управлением теперь уже статичной модели, полученной при адаптации начальной части входного потока. Немного более сложным подходом для статистического кодирования является следующий. Хотя эти модели имеют две компоненты - структуру и вероятность - память обычно используется только для адаптивной структуры, обычно настраивающей вероятности простым увеличением значения счетчика. После истощения памяти процесс адаптирования не нуждается в мгновенной остановке - вероятности могут продолжать изменяться в надежде, что структура останется пригодной для сжатия оставшейся части входа. Существует еще вероятность переполнения счетчика, но этого можно избежать контролируя ситуацию и вовремя производя деление значений всех счетчиков пополам [52,69,115]. Эффект этой стратегии состоит в том, что просмотренные в прошлом символы будут получать все меньший и меньший вес по мере выполнения сжатия - поведение, свойственное в пределе моделям новизны (раздел 2.3).

Выключение (или ограничение) адаптации может привести к вырождению сжатия, если начальная часть текста в целом не является представительной. Подход, снимающий эту проблему, состоит в очистке памяти и начале строительства новой модели всякий раз при переполнении [119]. Сразу после этого сжатие будет плохим, что в итоге компенсируется достигаемой в дальнейшем лучшей моделью. Эффект от отбрасывания модели к самому началу может быть смягчен поддержанием буфера последнего ввода и использованием его для конструирования новой начальной модели [19]. Кроме того, новая модель не должна начинать работу сразу же по переполнению памяти. При вынужденном прекращении адаптации надо сначала понаблюдать за результатами сжатия [100].
Снижение коэффициента сжатия указывает на то, что текущая модель несостоятельна, требует очищения памяти и запуска новой модели.

Все эти подходы очень общие, страдают от регулярной "икоты" и неполного использования памяти при построении модели. Более ритмичный подход состоит в применении "окна" для текста - как в семействе алгоритмов LZ77[118]. Это включает поддержание буфера из последних нескольких тысяч закодированных символов. При попадании символа в окно (после того, как он был закодирован), он используется для изменения модели; а при покидании, его влияние из модели устраняется. Хитрость в том, что представление модели должно позволять сжимать его также хорошо, как и разворачивать. Эффективного метода осуществления этого для DMC еще не было предложено, но это можно осуществить в других схемах. Медленный, но общий путь состоит в использовании сплошного окна для перестройки модели с самого начала при каждом изменении окна (т.е. при кодировании очеpедного символа). Ясно, что каждая модель будет очень похожа на предыдущую, поэтому такой же результат может быть достигнут со значительно меньшими усилиями путем внесения в модель небольших изменений. Кроме того, эффект окна может быть пpиближен сокращением редко используемых частей структуры [44,101]. Кнут [52] в своем адаптивном кодировании Хаффмана использовал окно.

Оптимизация

1.5.1. Маски прав

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

1.5.2. Эффективные права

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

Осознание

А теперь, после того, как мы добились столь блестящего результата, давайте осознаем: что же мы сделали и что у нас получилось.

Что сделали (или как все это назвать по-настоящему)

Мы изобразили наш алгоритм как блок-схему или, другими словами, направленный граф Затем провели инвариантное преобразование этого графа с выделением нескольких стационарных состояний программы - конечного автомата В результате получили новый граф, который легко укладывается в структурные конструкции Паскаля (Delphi)

Что из это следует

Проводя указанные действия несколько раз для разных алгоритмов, можно заметить, что на самом деле наши произвольно расставленные точки-состояния не такие уж случайные и произвольные. Как правило, при более глубоком рассмотрении вашего конкретного алгоритма можно найти каждому из этих состояний свое название. Это название может быть гораздо более выразительным, чем просто 1-2-3, поскольку это действительно состояния вашей программы.

О чем я говорю? Пусть ваш алгоритм занимается, скажем, синтаксическим разбором HTML-файла. Тогда одно из состояний может звучать как "Обнаружен тэг BODY" или "Найден конец документа".

Паскаль предлагает нам замечательное средство для работы с такими обозначениями в символическом виде и об этом средстве сейчас часто забывают. Программа из нашего примера может выглядеть так:

var State:(START, EOF_found, Line_Added, DONE); begin State:=START; {для любого алгоритма} repeat case State of START: begin B1; if C1 then State:=EOF_Found else State:=Line_Added end; EOF_Found: begin B2; if C2 then State:=DONE else State:=Line_Added end; Line_Added: begin B3; State:=START end; end; until State=DONE; {тоже для любого алгоритма} end;

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

Другое следствие

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

Небольшое исследование: крайние случаи

Подсчет.

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

Если n есть максимальное количество наблюдений, то счетчикам требуется log n битов памяти. Однако, можно применять меньшие регистры, если при угрозе переполнения делить значения счетчиков пополам. Понижение точности частот наносит небольшой ущерб, поскольку возникновение небольших ошибок в их предсказании почти не оказывает влияния на среднюю длину кода. На самом деле, масштабирование счетчиков часто улучшает сжатие, поскольку дает более старым счетчикам меньший вес, чем текущим, а последние статистики часто являются лучшей основой для предсказания следующего символа, чем более ранние. Счетчики настолько малы, что 5 битов описаны как оптимальные [22], когда как в других исследованиях применялись 8-битовые счетчики [69].

Для двоичного алфавита необходимо хранить только два счетчика. Лэнгдон и Риссанен использовали в [57] приближенную технику, называемую ассиметричным счетом, записывающую требуемую информацию только одним числом. Счетчик менее вероятного символа полагается равным 1, а счетчик более вероятного при его обнаружении всегда увеличивается на 1 и делится пополам при обнаружении следующего. Знак счетчика используется для определения, какой символ в текущий момент более вероятен.

Моррис в [70] предложил технику, при которой счетчики, достигшие значения n, помещаются в log(log(n)) битовый регистр. Принцип состоит в хранении логарифма счетчика и увеличении счетчика с вероятностью 2^-c, где c есть текущее значение регистра. Этот вероятностный подход гарантирует увеличение значения счетчика так часто, как следует, т.е. в среднем. Для анализа этой техники смотри Флажолета [29].

Полуадаптированное словарное кодирование.

Естественным развитием статичного n-адного подхода является создание своего словаря для каждого кодируемого текста. Задача определения оптимального словаря для данного текста известна как NP-hard от размера текста [95,97]. При этом возникает много решений, близких к оптимальному, и большинство из них совсем схожи. Они обычно начинают со словаря, содержащего все символы исходного алфавита, затем добавляют к ним распространенным диады, триады и т.д., пока не заполнится весь словарь. Варианты этого подхода были предложены в [62,64, 86,90,106,109,116].

Выбор кодов для элементов словаря являет собой компромисс между качеством сжатия и скоростью кодирования. Они представляют собой строки битов целой длины, причем лучшее сжатие будут обеспечивать коды Хаффмана, получаемые из наблюдаемых частот фраз. Однако, в случае равной частоты фраз, подход, использующий коды переменной длины, мало чего может предложить, поэтому здесь более удобными являются коды с фиксированной длиной. Если размер кодов равняется машинным словам, то реализация будет и быстрее, и проще. Компромиссом является двухуровневая система, например, 8 битов для односимвольных фраз и 16 битов - для более длинных, где для различия их между собой служит первый бит кода.

Пользователи, права, роли и группы

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

Практические контекстно-ограниченные модели.

Теперь рассмотрим все контекстно-ограниченные модели, взятые из источников, содеpжащих их подробное описание. Методы оцениваются и сравниваются в разделе 4. За исключением особых случаев, они применяют модели от -1 до некоторого максимального поpядка m.

Модели 0-го порядка представляют собой простейшую форму контекстно-ограниченного моделирования и часто используются в адаптированном и неадаптированном виде вместе с кодированием Хаффмана.

DAFC - одна из первых схем, смешивающих модели разных порядков и адаптиpующих ее структуры [57]. Она включает оценки 0-го и 1-го порядков, но в отличии от построения полной модели 1-го порядка она, для экономии пространства, основывает контексты только на наиболее часто встречаемых символах. Обычно первые 31 символ, счетчики которых достигли значения 50, адаптивно используются для формирования контекстов 1-го порядка. В качестве механизма ухода применяется метод A. Специальный "режим запуска" начинается в случае, если одни и тот же символ встретился более одного раза подряд, что уже хаpактеpно для модели 2-го порядка. Применение контекстов низшего порядка гарантирует, что DAFC pаботает быстpо и использует пpи этом ограниченный (и относительно небольшой) объем памяти. (Родственный метод был использован в [47], где несколько контекстов 1-го порядка объединялись для экономии памяти).

ADSM поддерживает модель 1-го порядка для частот символов [1]. Символы в каждом контексте классифицируются в соответствии с их частотами; этот порядок передается с помощью модели 0-ой степени. Т.о., хотя модель 0-го порядка доступна, но разные классы условий мешают друг другу. Преимуществом ADSM является то, что она может быть реализована в качестве быстрого предпроцессора к системе 0-го порядка.

PPMA есть адаптированная смешанная модель, предложенная в [16]. Она пpименяет метод A для нахождения вероятностей ухода и перемешивания на основе техники исключений. Счетчики символов не масштабируются.

PPMB это PPMA, но с применением метода B для нахождения вероятности ухода.

Права на объекты

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

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

Если же позволить назначать права не только на объекты, но и на группы объектов (т. к. назначать права на каждый объект в отдельности трудоемко), то получаем шесть сущностей (пользователь, группа, право, роль, объект, группа), которые объединяются восемью тройными связями. Восемью, так как у нас три пары сущностей, а 2^3 = 8. Еще есть три двойные связи (право-роль, пользователь-группа и объект-группа).

Это подводит к мысли - нельзя ли обойтись общей таблицей "право на"?

Предлагаемый вариант решения

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

В случае необходимости, используя ключевое слово mutable, разрешается вызывать неконстантные методы этого же объекта в константном методе, в константном методе присваивать неконстантной ссылке значение this или значения полей этого же объекта. Наличие ключевого слова mutable служит сигналом компилятору для вставки проверки того, что состояние объекта не изменилось; эта проверка аналогична постусловию в Eiffel-варианте и выполняется по завершении работы метода независимо от того, сколько точек возврата имеет метод (это может быть реализовано либо с помощью прокси-метода, либо вставкой проверки во все точки возврата). Для осуществления проверки перед выполнением метода копируется исходное состояние объекта. Также проверка выполняется при выходе из метода в случае исключительной ситуации. Проверка осуществляется во время выполнения только в отладочной версии независимо от того, выполнялась или нет часть метода, которая содержит инструкцию mutable. В случае если проверка не прошла генерируется исключение. На число использований ключевого слова mutable в теле метода ограничений не накладывается. Должен быть определен метод, который задает критерий оценки неизменности состояния, этот метод будет вызываться в проверке вставляемой компилятором. Использование ключевого слова mutable в таком методе запрещено.

Отличие от варианта С++ состоит в том, что const означает не физическую, а наблюдаемую неизменность объекта. Разница с Eiffel в том, что в случае, когда метод физически константен, проверка не вставляется, а также в том, что механизм обеспечения неизменности является дополнением к уже существующим элементам языка.

Процесс разработки или… разрабатываем процесс!

Александр Родыгин,

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

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

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

Какие особенности характеризуют программирование как сферу деятельности? По-моему мнению, наиболее резко выделяются такие аспекты:

Легкость порождения новых конструкций (достаточно "просто пошевелить мозгами"); Сложность решаемых задач (например, многопроцессорные вычислительные комплексы); Высокие темпы развития технологий и смены стандартов (новые виды программных средств возникают, развиваются и исчезают буквально за считанные годы); Непредсказуемость даже ближайшего будущего (еще недавно платформа J2EE в сочетании с CORBA считалась наиболее технологичной для распределенных приложений, с появлением SOAP и .Net это уже не так очевидно);

Программное обеспечение разрабатывают

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

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

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

Реализация.

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

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

СД, пригодные для смешанных контекстуальных моделей обычно основываются на деревьях цифрового поиска[51]. Контекст представляется в виде пути вниз по дереву, состоящему из узлов-счетчиков. Для быстрого отыскания расположения контекста относительно уже найденного более длинного (что будет случаться часто пpи доступе к моделям разного порядка) можно использовать внешние указатели.

Это дерево может быть реализовано через хеш-таблицу, где контекстам соответствуют элементы[78]. С коллизиями дело иметь не обязательно, поскольку хотя они и адресуют разные контексты, но маловероятны и на сжатие будут оказывать небольшое влияние (скорее на корректность системы).

Ролевая модель

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

С++

Язык С++ позволяет пометить метод как константный [1]; неконстантные методы этого объекта запрещается использовать в теле помеченного метода, и в контексте этого метода ссылки на сам объект и все его поля константны. Также существует возможность пометить ссылку (указатель) как константную. Применительно к ссылке свойство константности означает, что через эту ссылку можно вызывать только константные методы; присвоение константной ссылки неконстантной запрещено. Проверку этих условий обеспечивает компилятор. Для обозначения константности используется модификатор const. Пример интерфейса с константными методами:

В примере методы Name, Age, Picture объявлены константными. Кроме того, можно наблюдать и использование константных ссылок: параметр методов SetName и SetPicture, возвращаемое значение методов Name и Picture. Компилятор обеспечит проверку того, что реализация константных методов не имеет побочных эффектов в виде изменения состояния объекта, реализующего интерфейс Personal. Как только обнаружится попытка выполнить запрещенную операцию, компилятор сообщит об ошибке.

Предположим, мы намерены оптимизировать работу метода Picture. Вовсе не обязательно, что во всех вариантах использования класса Personal будет требоваться получить фотографию, занимающую много памяти. Можно так реализовать метод Picture, чтобы фотография загружалась только в случае использования именно этого метода. Но в Picture нельзя менять переменную picture_data, которая хранит ссылку на фотографию: компилятор запрещает менять поля объекта в константном методе. Это и есть проблема логической неизменности. Пожалуй, самым распространенным случаем возникновения несоответствия логической и физической неизменности является кэширование данных и создание прокси-объектов [9]. Таким образом, в С++ модификатор const означает лишь физическую неизменность. Чтобы обеспечить возможность реализации логически константных методов, в С++ имеется конструкция const_cast. С ее помощью приведенный пример можно переписать так:

С 2000 по 2009 год: инженерия?

В первые годы нового десятилетия мы гадаем, что нас ждет в будущем. Сможем ли мы именно в этом десятилетии решить проблему качества программного обеспечения? Будет ли это десятилетием, когда разработчики и пользователи начнут воспринимать ошибку в программном обеспечении как нечто исключительное? Или в конце этого десятилетия мы опять станем возлагать на будущее те же надежды, что и в 2000 году: «Все программное обеспечение содержит ошибки, и каждый должен с этим смириться» (Charles C. Mann, «Why Software Is So Bad, and What Is Being Done to Fix It?» MIT Technology Rev., 17 June 2002)?

По словам Леса Хеттона (Les Hatton, «Does OO Sync With How We Think?» IEEE Software, vol. 15, no. 3, May 1998), «отраслевой стандарт на хорошее коммерческое программное обеспечение предусматривает около 6 ошибок на тысячу строк кода при среднем показателе в 30 ошибок». Таким образом, уровень ошибок последние двадцать лет практически не меняется, несмотря на объектно-ориентированную технологию, автоматические отладчики, более качественные средства тестирования и более строгий контроль типов в таких языках, как Java и Ada. Есть ли основание считать, что в этом десятилетии ситуация изменится? Хотя технические трудности растут, но серьезный стимул дает тот факт, что расходы из-за некачественного программного обеспечения также увеличиваются. Согласно данным отчета, опубликованного в 2002 году Национальным институтом по стандартам и технологии, «объем экономических потерь из-за ошибочного программного обеспечения в США достигает миллиардов долларов в год и составляет, по некоторым оценкам, около 1% национального валового внутреннего продукта» (Research Triangle Institute, «The Economic Impacts of Inadequate Infrastructure for Software Testing,» NIST Planning Report 02-3, May 2002).

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

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

Разработчики программного обеспечения, как минимум, столь же талантливы, как и те, кто работает в этих отраслях, поэтому мы уверены, что в будущем появится более качественное программное обеспечение. Мы, как сообщество, сможем решить эту задачу. Фактически, даже Билл Гейтс, по-видимому, осознал необходимость «расколоть этот крепкий орешек», как он назвал проблему качества программного обеспечения в своем письме, разосланном, по некоторым сведениям, всем сотрудникам корпорации 15 января 2002 года.

«Каждые несколько лет я рассылаю письма, в которых рассказываю о наивысшем приоритете для Microsoft. Два года назад это была реализация стратегии .NET. До того было несколько писем о том, насколько важным является Internet для нашего будущего, и каким образом мы можем сделать Internet действительно полезным для людей. За последний год стало ясно, что задача превращения .NET в платформу надежных вычислений (Trustworthy Computing) — важнее, чем любая другая часть нашей работы. Если мы этого не добьемся, люди попросту не захотят (или не смогут) использовать все остальные наши достижения. Надежные вычисления — это самый высокий приоритет для всего, что мы делаем. Мы должны вывести отрасль на абсолютно новый уровень надежности в вычислениях».

Так оно и есть, хотя и не понятно, когда удастся этого добиться. Когда мы получим возможность создавать действительно высококачественное программное обеспечение? Ответ существенно зависит от того, сможем ли мы (и насколько быстро) воплотить в жизнь некоторые идеи, возникшие в прошлых десятилетиях, идеи, описанные в этой статье.


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

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

Джеймс Уайттеккер (jw@cs.fit.edu) — профессор факультета информатики Технологического института штата Флорида. Джеффри Воас (voas@cigital.com) — один из основателей и директор по науке компании Cigital.

James A. Whittaker, Jeffrey M. Voas, 50 Years of Software: Key Principles of Quality. IEEE IT Pro, November-December 2002. IEEE Computer Society, 2002, All rights reserved. Reprinted with permission.

СЛОВАРHЫЕ МЕТОДЫ.

В основе этих методов лежит идея совеpшенно отличная от идеи статистического сжатия. Словарный кодировщик добивается сжатия заменой групп последовательных символов (фраз) индексами некоторого словаря. Словарь есть список таких фраз, которые, как ожидается, будут часто использоваться. Индексы устроены так, что в среднем занимают меньше места, чем кодируемые ими фразы, за счет чего и достигается сжатие. Этот тип сжатия еще известен как "макро"-кодирование или метод "книги кодов". Отличие между моделированием и кодированием для словарных методов туманно, поскольку пpи изменении словарей коды обычно не изменяются.

Словарные методы обычно быстры, в частности по тем причинам, что один код на выходе соответствует нескольким входным символам и что размер кода обычно соответствует машинным словам. Словарные модели дают достаточно хорошее сжатие, хотя и не такое хорошее как контекстно-ограниченные модели. Можно показать, что большинство словарных кодировщиков могут быть воспроизведены с помощью контекстно-ограниченных моделей [6,9,53,83], поэтому их главным достоинством является не качество сжатия, а экономия машинных ресурсов.

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

Совершенствование

Следующее «решение» проблемы качества программного обеспечения появилось в 90-х годах под названием «совершенствование процесса разработки программ». Основой этого движения была теперь популярная и часто критикуемая модель Capability Maturity Model. Для краткости мы сознательно упростим формулировку основного принципа совершенствования процесса разработки программ: создание программного обеспечения — это задача управления, к которой можно применять соответствующие процедуры управления данными, процессами и практическими методами, с целью создания максимально оптимального решения. Управление разработкой программного обеспечения гарантирует получение более качественного продукта.

Другими словами, поскольку разработчики не могли должным образом управлять своими проектами (что исторически подтверждается весьма низким уровнем качества программного обеспечения), менеджеры должны ввести организационный контроль. Впрочем, даже самые лучшие в мире процессы можно неправильно реализовать (Jeffrey Voas, «Can Clean Pipes Produce Dirty Water?» IEEE Software, vol. 14, no. 4, July 1997).

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

Однако разработка программного обеспечения в основе своей — это техническая задача. Хорошие разработчики могут создать хорошее программное обеспечение, несмотря на плохое руководство или даже его полное отсутствие. Однако обратное неверно: неквалифицированные технические специалисты вряд ли разработают хорошее программное обеспечение даже при блестящем руководстве.
Описание другого исследования, но с аналогичными выводами, главным образом относительно роли руководства в решении проблемы 2000 года, можно найти в статье Роберта Гласса (Robert Glass, «Y2K and Other Software Noncrises,» IEEE Software, vol. 17, no. 2, Mar. 2002). В силу вышесказанного, CMM внедряется медленно. Во многих программных компаниях разработчики по-прежнему не знают о ее существовании.

Модель CMM — это не только идея совершенствования процессов разработки, возникшая в 90–х годах. В последние годы этого десятилетия организации, специализирующиеся на разработке программного обеспечения, начали применять ту или иную популярную теорию к своим процессам. Пример тому — Six Sigma, метод первоначально предназначенный для сокращения ошибок при проектировании и производстве аппаратных систем.

«Шесть сигма» (Six Sigma) — это дисциплинарный, определяемый данными подход и методология ликвидации дефектов в любом процессе — от производства до транзакций, от продукта до службы. Чтобы добиться уровня «шести сигма», процесс не должен порождать более 3,4 дефектов на миллион случаев (http://www.isixsigma.com/sixsigma/six_sigma.asp).

Главный недостаток методики Six Sigma, состоит в том, что до сих пор не ясно, что означает миллион потенциальных случаев появления ошибок в программном продукте. Более того, как это вообще их можно корректно подсчитать?

Еще большему увеличению пропасти, разделяющей руководство и технических специалистов в процессе разработки программного обеспечения, способствовало то, что в 90-е годы достигнут значительный прогресс в развитии вычислительной инфраструктуры. Новые операционные платформы превзошли более старые операционные системы по функциональности. Знания, которые раньше были полезными, стали ненужными. Появились новые языки программирования, мгновенно завоевавшие популярность. Программированию приходилось учиться снова и снова. Новые API для коммуникаций, защиты, распределенных вычислений и, конечно, Web, полностью перевернули жизнь разработчиков.


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

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

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

Наконец, 1990-е годы ознаменовали первую реальную попытку превратить разработку программного обеспечения в инженерную дисциплину с помощью концепций CBSE (component-based software engineering — «компонентная разработка программного обеспечения») и COTS (commercial off-the-shelf — готовые коммерчески доступные компоненты). Идея состоит в создании небольших, высококачественных модулей и последующего их объединения. Проблема, безусловно, заключается в том, что объединенные вместе высококачественные модули не обязательно превратятся в высококачественную систему.Комбинированная система может оказаться никуда негодной из-за некорректного способа объединения, либо из-за ошибочных представлений о поведении компонентов или о среде, в которую они помещаются. Более того, COTS-компоненты, которые обычно лицензируются в виде исполняемых модулей, могут породить неприятные побочные эффекты, неизвестные получателю лицензии. Подобные побочные эффекты иногда проявляются только при объединении одних компонентов с другими, и их практически невозможно обнаружить при тестировании каждого модуля в отдельности. Парадигма «разделяй и властвуй», которая оправдывает себя в случае аппаратных и физических систем, может оказаться губительной для систем логических. Лишь время покажет, как CBSE повлияет на качество программного обеспечения в будущем.

СРАВHЕHИЕ.

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

Статичные словарные кодировщики.

Они полезны в том случае, если достаточен невысокий уровень сжатия, достигаемый за счет небольших затрат. Предложенный в различных формах быстрый алгоритм кодирования диадами поддерживает словарь распространенных пар символов или диад [11,20,46,89,94,98]. На каждом шаге кодирования очередные два символа проверяются на соответствие диадам в словаре. Если оно есть, они вместе кодируются, иначе кодируется только первый символ, после чего указатель продвигается вперед соответственно на две или одну позицию.

Диадные коды достраиваются к существующим кодам символов. Например, алфавит ASCII содержит только 96 текстовых символов (94 печатных, пробел и код для новой строки) и т.о. часто размещается в 8 битах. Оставшиеся 160 кодов доступны для представления диад. Их может быть и больше, если не все из 96 символов используются. Это дает словарь из 256 элементов (96 символов и 160 диад). Каждый элемент кодируется одним байтом, причем символы текста будут представлены их обычными кодами. Поскольку все коды имеют одинаковый размер, то кодировщику и раскодировщику не надо оперировать с битами внутри байтов, что обеспечивает большую скорость диадному кодированию.

В общем случае, если дано q символов, то для заполнения словаpя будет использовано 256-q диад, для чего было предложено два метода. Первый - просмотр образца текста для определения 256-q наиболее распространенных диад. Список можно организовать так, что он будет отслеживать ситуацию вpоде pедкой встpечи "he" из-за того, что "h" обычно кодируется как часть предшествующего "th".

Более простой подход состоит в выборе двух небольших множеств символов, d1 и d2. Диады для pаботы получаются перекрестным умножением элементов d1 и d2, где первый элемент пары берется из d1, а второй - из d2. Словарь будет полным, если |d1|*|d2| = 256-q. Обычно и d1, и d2 содержат часто встречающиеся символы, дающие множество типа:

{ _,e,t,a, ... } * { _,e,t,a, ... } = { __,_e,_t, ... ,e_,ee,et, ... } [20].

Другая часто используемая возможность основана на идее pаспpостpаненности паpы гласная-согласная и создает множество d1 = { a,e,i,o,u,y,_ } [98].

Сжатие, получаемое с помощью диадного метода, может быть улучшено обобщением для "n-адных" фрагментов, состоящих из n символов [76,103]. Проблема со статичной n-адной схемой состоит в том, что выбор фраз для словаря неоднозначен и зависит от природы кодируемого текста, при том, что мы хотим иметь фразы как можно длиннее. Надежный подход состоит в использовании нескольких распространенных слов. К сожалению, краткость слов не дает возможность добится впечатляющего сжатия, хотя оно и представляет собой определенное улучшение диадного метода.

Стратегия разбора.

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

К сожалению тщательный разбор не обязательно будет оптимальным. На практике определение оптимального разбора может быть очень затруднительным, поскольку предел на то, как далеко вперед должен смотреть кодировщик, не установлен. Алгоритмы оптимального разбора даются в [49,86,91,97,106], но все они требуют предварительного просмотра текста. По этой причине на пpактике шиpоко используется тщательный метод, даже если он не оптимален, т.к. пpоводит однопроходное кодирование с ограниченной задержкой.

Компромиссом между тщательным и оптимальным разборами является метод помещения самого длинного фрагмента в начало - LFF [91]. Этот подход ищет самую длинную подстроку ввода (не обязательно начиная сначала), которая также есть и в словаре. Эта фраза затем кодируется, и алгоритм повторяется до тех пор, пока не закодиpуются все подстроки.

Например, для словаря M = { a,b,c,aa,aaaa,ab,baa,bccb,bccba }, где все строки кодируются 4-мя битами, LFF - разбор строки "aaabccbaaaa" сначала опpеделяет "bccba" как самый длинный фрагмент. Окончательный разбор строки есть: "aa,a,bccba,aa,a", и строка кодируется 20-ю битами. Тщательный разбор дает "aa,ab,c,c,baa,aa" (24 бита), когда как оптимальный разбор есть "aa,a,bccb,aaaa" (16 битов). В общем случае показатели сжатия и скорости для LFF находятся между тщательным и оптимальным методами. Как и для оптимального сжатия LFF требует просмотра всего ввода перед пpинятием решения о разборе. Теоретическое сравнение техник разбора можено посмотpеть в [34,49,97].

Другое приближение к оптимальному разбору достигается при помощи буфера, скажем из последних 1000 символов ввода [48]. На практике, точки разреза (где может быть определено оптимальное решение) почти всегда всегда располагаются после 100 отдельных символов, и поэтому использование такого большого буфера почти гарантирует оптимальное кодирование всего текста. При этом может быть достигнута такая же скорость, как и при тщательном кодировании.

Опыты показали, что оптимальное кодирование раза в 2-3 раза медленнее, чем тщательное, улучшая при этом сжатие лишь на несколько процентов[91]. LFF и метод ограниченного буфера улучшают сжатие еще меньше, но и времени на кодирование требуют меньше. На практике небольшое улучшение сжатия обычно перевешивается допольнительными временными затратами и сложностью программирования, поэтому тщательный подход гораздо более популярен. Большинство словарных схем сжатия организуют словарь в предположении, что будет применен именно этот метод.

Структуры данных для метода Зива-Лемпела

Наиболее распространенной СД в методе Зива-Лемпела и для моделирования в целом является дерево цифрового поиска. Такая СД и ее вариации обсуждаются в [51]. Для работающих с окнами схем можно пpименять линейный поиск, поскольку размер области поиска постоянен (хотя сжатие может быть очень медленным). В качестве компромисса между быстpотой дерева цифрового дерева поиска и экономным расходованием памяти линейного поиска можно применить двоичное дерево [5]. Для этой цели также можно использовать хеширование [12]. Подобное применение хеширования можно обнаружить в [110]. Сравнение СД, используемых для сжатия Зива-Лемпела, приводится у Белла [7].

Работающие с окнами схемы имеют то неудобство, что подстроки после своего исчезновения из окна должны уничтожаться в индексной СД. В [85] описан метод, позволяющий избежать этого посредством поддерживания нескольких индексов окна, что т.о. позволяет осуществлять поиск в СД, где уничтожение затруднительно. Однако, особая предложенная там СД была без необходимости сложной для pаботы с окнами.

Проблема поиска вполне поддается мультипроцессорной реализации, поскольку на самом деле существует N независимых строчных соответствий, которые необходимо оценить. В [34] описана параллельная реализация сжатия Зива-Лемпела.

Свойство неизменности: ООП под микроскопом

Алексей Лапшин,

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

Говорят, что метод объекта обладает свойством неизменности (константности), если после его выполнения состояние объекта не изменяется. Различают два вида неизменности, логическую и физическую. Физическая неизменность означает полную идентичность объекта, с точностью до каждого поля, а логическая - его наблюдаемую идентичность (невидимые внешнему миру поля private и protected могут быть изменены, но это не должно быть заметно для клиента, использующего объект).

Терминология.

Сжимаемые данные называются по-разному - строка, файл, текст или ввод. Предполагается, что они производятся источником, который снабжает компрессор символами, пpинадлежащими некоторому алфавиту. Символами на входе могут быть буквы, литеры, слова, точки, тона серого цвета или другие подобные единицы. Сжатие иногда называют кодированием источника, поскольку оно пытается удалить избыточность в строке на основе его предсказуемости. Для конкретной строки коэффициент сжатия есть отношение размера сжатого выхода к ее первоначальному размеру. Для его выражения используются много разных единиц, затpудняющих сравнение экспериментальных результатов. В нашем обозрении мы используем биты на символ (бит/символ) - единицу, независимую от представления входных данных. Другие единицы - процент сжатия, процент сокращения и пpочие коэффициенты - зависят от представления данных на входе (например 7-или 8-битовый код ASCII).

Термины

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

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

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

пользователь; программа; функция программы

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

пользователю может быть дано или не дано право использовать некоторую функцию программы. роль (набор прав); группа пользователей.

Требования скорости и памяти.

В общем случае лучшее сжатие достигается большим расходом ресурсов ЭВМ: времени и прежде всего памяти. Моффат [69] описывает реализацию одного из лучших архиваторов (PPMC), обрабатывающего около 2000 символов в секунду на машине MIP (OC VAX 11/780). DMC выполняется немного медленнее, так как работает с битами. Для сравнения, у LZFG на подобной машине зафиксирована скорость кодирования около 6000 симв/сек, а раскодирования - 11000 симв/сек [28]. LZB имеет особенно медленное кодирование (обычно 600 симв/сек), но очень быстрое раскодирование (1600 симв/сек), которое может достичь 40.000.000 симв/сек при использовании архитектуры RISC [43].

Большинство моделей пpи увеличении доступной памяти улучшают свое сжатие. Пpи использовании лучшей СД скоpость их pаботы повысится. Реализация PPMC, предложенная Моффатом, выполняется на ограниченной памяти в 500 Кб. На таком пространстве может работать и схема DMC, хотя полученные результаты ее работы достигнуты на неограниченной памяти, временами составляющей несколько Мб. LZFG использует несколько сотен Кб, LZB для кодирования применяет сравнимое ее количество, когда как раскодирование обычно требует всего 8 Мб.

DIGM и HUFF по сравнению с остальными методами требуют очень немного памяти и быстpо выполняются.

Вероятность ухода.

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

В этом разделе описывается метод выведения весов из "вероятности ухода". В сочетании с "исключениями" (раздел 1.4) они обеспечивают простую реализацию, дающую тем не менее очень хорошее сжатие. Этот более прагматический подход, который сначала может показаться совсем не похожим на перемешивание, выделяет каждой модели некоторое кодовое пространство, учитывая пpи этом возможность доступа к моделям низшего порядка для предсказания следующего символа [16,81]. Можно увидеть, что эффективное придание веса каждой модели основано на ее полезности.

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

Вероятность обнаружения невстречаемого ранее символа называется "вероятностью ухода", потому что она опpеделяет, уходит ли система к меньшему контексту для оценки его веpоятности. Механизм ухода является аналогом механизма перемешивания, что далее находит свое подтвержение. Обозначим вероятность ухода на уровень o через e(o), тогда соответствующие веса могут быть вычислены из вероятностей ухода по формуле:

Возникновение

Программируемые компьютеры впервые начали использовать для решения военных задач, стоявших перед США во Второй мировой войне. Такие устройства требовались для самых разных целей, от вычисления траекторий бомб до дешифровки вражеских радиопередач. Именно война стимулировала создание более качественных и быстрых способов вычислений. К решению этой проблемы были привлечены самые блестящие специалисты. Первыми «компьютерами» были люди, главным образом женщины, которых в 40-х годах не брали в армию США. Они составляли длинные «конвейеры» из механических счетных машин. Представьте себе «работу» программы следующим образом: каждая из сидящих в ряд женщин, работает на своей станции, выполняя определенную часть вычислений траектории бомбы, и передает ответ своей соседке для выполнения следующего шага.

Но в военных условиях скорость и точность одинаково важны, а компьютер ENIAC Дж. Преспера Эккерта и Джона Мочли гарантировал и то, и другое. Кроме того, война открывает финансовые возможности, которых в других условиях может и не представиться. ENIAC был в большей степени электрической, нежели механической машиной, используя электричество не только для управления механическими компонентами, но и для самих вычислений. Эта машина могла не только порождать результаты, но и автоматически использовать эти результаты для других вычислений. Однако ENIAC опоздал, не успев решить ни одной задачи для военных целей (Scott McCartney, ENIAC: The Triumphs and Tragedies of the World’s First Computer, Walker and Company, New York, 1999).

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

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

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

Возрождение

В 80-е годы были предприняты первые попытки вернуть здравый смысл разработке программного обеспечения. Две из них заслуживают особого внимания.

Сжатие сокращает объем пространства, тpебуемого

Выход в свет

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

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

Между тем, в эти годы развитие отрасли могло пойти по тупиковому пути. Менее талантливые люди брались за решение более сложных задач. (Действительно, как можно было найти еще более талантливых и более дотошных разработчиков, чем программисты 50-х годов?) Ситуация располагала к катастрофе, но катастрофы не произошло. Программное обеспечение, написанное в 60-х годах, отличается столь же высоким качеством, что и программы, созданные десятилетием раньше.

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

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

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

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

XP

Из всех новых методологий eXtreme Programming находится в самом центре всеобщего внимания. Именно благодаря XP активные методологии вызвали такой ажиотаж и всевозможные слухи.

Поначалу XP относили в лучшем случае к хакерству в худшем смысле слова. Многие до сих пор считают эту методологию чем-то вроде культа Вуду, несмотря на то, что ее основателем и главным идеологом является Кент Бек (Kent Beck) - всемирно известный эксперт по языку Smalltalk и разработке объектно-ориентированных систем. Другим видным пропагандистом XP является Мартин Фаулер (Martin Fowler) - тоже всемирно признанный ученый-исследователь и автор многочисленных публикаций на темы ОО систем, паттернов, UML и реструктуризации программ.

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

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

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

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

Все эти принципы применимы и при создании программной системы. Хотя Кент Бек и говорит, что они давно известны в практике программирования, только с появлением XP они действительно образовали эффективную методологию.

Простейшее работоспособное решение (Simplest thing that could possibly work)

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

Проникновение задачей (Personal involvement)

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

Постоянное общение

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


Известны успешные проекты и больших коллективов, вплоть до 40 человек.

Наместник заказчика (On site customer)

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

Парное программирование (Pair programming)

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

Общий стандартизованный код

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

Тесты вперед (Test first)

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


Все тесты объединяются и, прежде чем вновь написанный или измененный код будет присоединен к проекту, производится тестирование на уровне модулей (unit testing).

Кроме этого, отдельная группа создает второй вид существующих в XP тестов - функциональные тесты (functional tests), которые проверяют работоспособность системы в целом перед поставкой заказчику и делают это в автоматизированном режиме.

Таким образом, "тесты вперед" подход, хотя и не гарантирует 100% работоспособности, все-таки предоставляет очень высокие гарантии качества и позволяет и программистам и заказчику чувствовать себя более уверенно на пути к окончательному выпуску продукта.

Ежедневная сборка (Daily builds)

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

Рассказы пользователей (User stories)

Как же можно разрабатывать систему, если нет ни утвержденных спецификаций, ни плана разработки, ни архитектуры, да еще постоянно вносятся изменения? Вот это - то самое чудо, которое стало возможным благодаря XP. Ответ прост как все гениальное: мы начинаем разработку как только понимаем, чего хочет заказчик В ДАННЫЙ МОМЕНТ. В последующем, мы перестраиваем программы так, чтобы отражать вносимые изменения. При этом мы планируем только то, что можем предвидеть, а разрабатываем только то, что востребовано.

Для проведения этого простого принципа в жизнь, в XP предназначена специальная процедура, называемая "Рассказы пользователей", которая означает то же, что и прецеденты использования (use cases) в UML, но не имеют никакого формального выражения.


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

Рефакторинг (Refactoring)

Как же писать программы в такой динамичной и постоянно меняющейся обстановке? Это объясняет другая, также нашумевшая техника XP, подразумевающая реструктуризацию и заключающаяся в осознанном подходе к вопросам модификации кода без потери его функциональности. Книга М. Фаулера подробно описывает этот процесс и включает большое количество примеров. На сайте www.retactoring.com поддерживается on-line версия каталога приемов реструктуризации и полезные ссылки. Конечно, программы модифицировали всегда, но только с появлением XP это стало не второстепенным занятием исправления просчетов, а полноценной техникой разработки, позволяющей вносить изменения таким образом, чтобы улучшать внутреннее устройство системы, а не приводить к ее деградации.

Разумное проектирование

Очень многие считают, что XP - это новый вид RAD (Rapid Application Development - Быстрая Разработка Приложений) технологии, которая зарекомендовала себя как недальновидная. На самом деле, XP не только поощряет проектирование, но и включает его в методологию. Как обычно, система требует тщательного планирования, но только уже без излишнего "пророчества" и требований к инструментарию. Для разработки общей архитектуры достаточно настенной доски для рисования.


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

"Экстремальная" символизация

XP является флагманом новых методологий и в наибольшей мере символизирует их ценности:

Взаимодействие личностей Работающие программы Сотрудничество с заказчиком Реакция на изменения

Как и все остальные прогрессивные методологии, XP не является жестко детерминированным процессом и предполагает настройку на конкретную ситуацию и людей в контексте существующего проекта.

Продолжение может последовать. Если эта тема Вас заинтересовала - пишите мне!

Александр Родыгин,

В данной работе рассмотрены различные

---