Фундаментальные структуры данных, универсальность и сложность алгоритмов

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

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

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

роль типов в создании надежного ПО;

универсальность: как объявлять классы контейнера, безопасные по типу хранимых элементов;

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

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

5.1. Статическая типизация и универсальность

Первая проблема, возникающая при работе с контейнером, – это проблема типизации.

Статическая типизация

Все сущности в наших программах объявляются с указанием типа. Это правило позволяет компилятору проверять, что любая операция, которую вы хотите применить к сущности x, например вызов метода x.f(a), использует метод, разрешенный для применения. Компилятор может:

найти объявление сущности x и установить тип T, заданный при ее объявлении;

найти класс, задающий тип Т;

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

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

Выбор статической типизации, принятый в большинстве современных ОО-языков программирования, включая Java, C#, Eiffel, основан на двух основных аргументах:

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

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

Статическая типизация для контейнерных классов

Как можно применить принципы статической типизации к контейнерам? Мы уже знакомы со списками, так как мы видели, что экземпляры LINE являются списками экземпляров класса STATION с методами, такими как

extend (s: STATION)                                          — Команда
            —Добавить s в конец линии
item: STATION                                                — Запрос
            — Станция в текущей позиции курсора)
        

Предположим теперь, что мы хотим иметь класс LIST, который может описывать списки чего угодно: список станций метро, список целых чисел, список объектов некоторого заданного типа. Класс должен иметь вышеприведенные методы, но невозможно объявить тип s в методе extend или результат item без знания типа элементов списка: STATION, как выше, или любого другого типа, который вы выбрали для объектов конкретного списка.

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

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

Универсальные классы (классы с родовыми параметрами)

Используя универсальность, объявим класс LIST следующим образом:

class LIST [G] feature
    extend (s:G)
            —Добавить s в конец списка.
        do … end
    item: G
        — Элемент в текущей позиции курсора.
    … Другие методы и инварианты…
end
        

G – это просто имя, известное как формальный родовой параметр (таких параметров у класса может быть несколько). Родовой параметр задает тип, так что его можно применить для объявлений внутри класса, как в нашем примере для аргумента s в методе extend и при объявлении результата запроса item.

Какой же тип обозначает G? Сам класс на этот вопрос не отвечает. Используя класс LIST, можно объявить, например:

first_1000_primes: LIST [INTEGER]
stations_visited_today: LIST [STATION]
        

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

Эта техника решает проблему статической типизации для общих контейнерных классов. Объявим переменные:

some_integer: INTEGER
some_station: STATION
        

Следующие операторы будут правильными:

first_1000_primes.extend (some_integer)
stations_visited_today.extend (some_station)
some_integer:= first_1000_primes.item
some_station:= stations_visited_today.item
        

Здесь все удовлетворяет правилам типа. Формальный аргумент extend в LIST имеет тип G; это значит INTEGER для first_1000_primes, объявленного как LIST [INTEGER], и STATION для stations_visited_today, поэтому вполне законно передать целое в качестве фактического аргумента в первом случае, и станцию метро – во-втором. То же справедливо и для результата item.

Но с другой стороны, следующие вызовы ошибочны:

first_1000_primes.extend (some_station)
stations_visited_today.extend (some_integer)
        

На этапе компиляции возникнут ошибки:

(рис 5.1)

До середины 80-х годов на шоссе 101 от Сан-Франциско до Лос-Анджелеса и Сан-Диего водителей ждало только одно прерывание – светофор в Санта-Барбаре, создающий вечную пробку. Губернатор Калифорнии в семидесятых годах Джерри Браун ответил на жалобы недовольных в чисто калифорнийском стиле, что на самом деле они должны быть благодарны за возможность сделать паузу и расслабиться. Именно так и следует реагировать на ошибки, полученные в период компиляции.

Почувствуй методологию

Дзен и искусство реагирования на сообщения компилятора

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

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

Дальнейшее рассмотрение требует ввода новых понятий.

Определения: родовой или универсальный класс, родовое порождение

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

Класс LIST является универсальным классом; тип LIST [INTEGER], полученный из LIST подстановкой родового параметра INTEGER, является родовым порождением LIST.

Все контейнерные классы, изучаемые в этой лекции, такие как ARRAY [G], LINKED_LIST [G], HASH_TABLE [G, H], являются универсальными, родовыми классами. Родовой параметр с именем G всегда задает тип элементов в контейнере. Конечно, для родового параметра можно выбирать любое имя, лишь бы оно не совпадало с фактическим именем одного из классов системы.

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

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

Правильность против корректности

Целью механизма универсальности является, как отмечалось, проверка правильности некоторых видов программ (тех, что включают контейнерные структуры). Универсальность – это то, что делает "правильными" такие вызовы, как first_1000_primes.extend (some_integer). Правильность означает, что вызовы удовлетворяют правилам типа языка, а, следовательно, компилятор их допускает.

Это, однако, еще не означает, что такие операторы всегда будут работать корректно. Цель вызова first_1000_primes может быть void во время выполнения, extend может иметь предусловие, которому some_integer не удовлетворяет. Следует различать два разных понятия.

Определения: правильность, корректность

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

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

Определение корректности применимо только к правильным программам. Фактически, для статически типизированного языка (языка с точными правилами правильности, такого как Eiffel) нет смысла говорить о корректности, если программа не прошла проверку на "правильность".

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

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

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

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

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

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

Классы против типов

Универсальность позволяет нам лучше разобраться в отношениях между классами и типами.

Тип – это описание множества значений периода выполнения: тип INTEGER задает свойства целых, тип STATION задает свойства объектов (периода выполнения), представляющих станции.

Класс является программным модулем, определяющим коллекцию компонентов (полей и методов) и их свойств, таких как инварианты класса, применимых к множеству объектов периода выполнения.

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

some_integer: INTEGER
some_station: STATION
        

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

Связь между классами и типами остается такой же сильной и для универсальных классов. Новый поворот состоит в том, что универсальный класс, такой как LIST или ARRAY, более не задает тип – он задает шаблон типа, параметризованный тип. Для получения типа достаточно выполнить родовое порождение, задав фактические родовые параметры. Например:

INTEGER и STATION являются классами, но они также являются и типами. Это справедливо для любого неуниверсального класса;

LIST и ARRAY являются классами; LIST [STATION] и ARRAY [INTEGER] являются типами. Родовое порождение любого универсального класса является типом.

Дадим точное определение.

Определения: тип класса, универсально порожденный, базовый класс

Тип класса – это:

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

Вложенные родовые порождения

Осталось уточнить, чем может быть фактический родовой параметр для универсального класса. Ответ напрашивается: типом. Вы могли видеть это в последних примерах: в LIST [STATION] фактический родовой параметр STATION является типом, так же как и INTEGER в ARRAY [INTEGER].

Возможно, вы ощутили некоторую странность в этих определениях.

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

Затем фактические параметры определяются как типы.

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

благодаря предложению Т1 определения мы знаем, например, что STATION – не универсальный класс, является типом;

тогда мы можем использовать Т2, чтобы вывести, что ARRAY [STATION] также является типом.

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

Определение открывает, фактически, интересные возможности. Тип, используемый в качестве фактического параметра в Т2, не обязательно определяется предложением Т1; он может определяться, в свою очередь, предложением Т2 – другими словами, параметр может быть универсально порожденным. Это позволяет задавать такие типы, как

LIST [LIST [INTEGER]]
LIST [ARRAY [STATION]]
ARRAY [ARRAY [ARRAY [INTEGER]]]
        

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

5.2. Контейнерные операции

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

Большинство базисных операций одни и те же: вставка и удаление элемента, поиск заданного элемента, определение числа элементов …

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

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

Прежде чем начать рассматривать специфические виды контейнеров, дадим обзор фундаментальных операций: вначале рассмотрим запросы, а затем команды. Пусть G будет обозначать тип элементов контейнера, и он будет всегда первым родовым параметром соответствующих классов, как в ARRAY [G] или LINKED_LIST [G].

Запросы

Одна из операций, необходимая всем контейнерам, – это запрос, определяющий, пуст ли контейнер (не содержит элементов). Запрос, возвращающий значение BOOLEAN, называется is_empty. Его сигнатура проста:

is_empty: BOOLEAN
        

Другими словами, у него нет аргументов, он вызывается в форме c.is_empty, возвращая булевское значение для каждого контейнера c.

Выяснить, находится ли некоторый элемент в контейнере, можно с помощью запроса

has(v:G):BOOLEAN
        

Для определения числа элементов в контейнере служит запрос:

count: INTEGER
        

Инвариант, применимый ко всем рассматриваемым контейнерным классам:

is_empty = (count = 0)
        

Для получения элемента контейнера, определяемого политикой контейнера, а не клиентом:

item: G
        

Некоторые контейнеры, такие как массивы, позволяют получить элемент по заданному клиентом индексу, как в предложении "дайте мне третий элемент". Такой запрос с параметром имеет вид:

item (i:INTEGER): G
        

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

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

item (i: STRING): G
        

Мы покажем, как обобщить тип ключа, допуская не только строки. Пока используемое имя запроса по-прежнему не приводит к конфликтам.

Команды

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

make(n:INTEGER)
        

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

Для наиболее общей операции по добавлению или замене элемента используется имя put. Эта операция применима с разными сигнатурами, соответствующими сигнатуре запроса item, но с добавлением еще одного аргумента, задающего новое значение:

put (v: G)
put (v: G; i: INTEGER)
put (v: G; k: STRING)
        

Постусловие всегда должно включать предложение

inserted: has (x)
        

и вдобавок должно выражать отношение с соответствующей версией item:

item = v, если put не имеет аргументов (первый случай);

item (i) = v для версии с целочисленным индексом;

item (k) = v в последнем случае.

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

extend (v: G)
extend (v: G; i: INTEGER)
extend (v: G; k: STRING)
        

с постусловием

one_more: count = old count + 1
        

или для замены использовать

replace (v: G)
replace (v: G; i: INTEGER)
replace (v: G; key: STRING)
        

с постусловием

same_count: count = old count
        

Когда существует либо extend, либо replace, то put обычно является синонимом одного из них, соответствуя (если оба присутствуют) более общему использованию. Во всех случаях постусловие has(v) выражает то, что после добавления элемента структура должна давать ответ "да", если делается запрос о его присутствии.

Процедура для удаления элемента в зависимости от контекста называется remove или prune.

Стандартизация имен методов для базисных операций

Имена, применяемые выше – item, has, put …, – повторяются во всех библиотеках. Даже беглый взгляд на контейнерные классы показывает, что большинство из них содержит методы с этими именами.

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

put (v: like item; i: INTEGER)
            — Заменить i-й элемент на v, если индекс в допустимом интервале.
        require
            valid_key: valid_index (i)
        ensure
            replaced: item (i) = v
        

Аналогично для put в классе STACK:

put (v: G)
            — Поместить v в вершину стека.
        require
            extendible: extendible
        ensure
            pushed: item = v
        

Поэтому из-за сходства имен двусмысленность не возникает. Использование согласованных имен облегчает использование библиотек и – для новичков – обучение использованию: при знакомстве с новым классом читатели могут быстро идентифицировать ключевые методы и их назначение.

Почувствуй методологию

Принцип стандартных имен методов

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

Автоматическая перестройка размера

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

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

Даже наши массивы должны быть перестраиваемыми.

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

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

Не попадайте в такие ловушки!

Почувствуй методологию

Не замыкайте в камеры ваших пользователей

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

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

5.3. Оценка алгоритмической сложности

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

Необходим надежный способ сравнения производительности для выбора нужного типа контейнера. Недостаточно провести эксперименты над конкретным контейнером и сделать вывод, что "в среднем запрос на вызов элемента требует 10 наносекунд при работе с массивом и 40 наносекунд при работе со связным списком".

Корректные рассуждения "о средних" требуют знания статистического распределения. Для размеров контейнеров трудно ожидать разумного определения такого распределения (сколько контейнеров может быть с 10 элементами, сколько с 1000 элементами и т. д.).

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

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

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

Измерение порядка величин

Абстрактная сложность основывается на двух принципах.

Рассматривает меру сложности как функцию от размера структуры данных. Для большинства примеров этой лекции размер задается одним параметром – count – числом элементов контейнера.

Функция определяется не точной формулой, а порядком величины, задаваемой нотацией "О-большое", как O(count).

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

Для такой меры:

константные мультипликативные множители не играют роли: $$O(100* count^2)$$ означает то же самое, что и $$O(count^2)$$. Объяснение этого соглашения состоит в том, что не следует придавать большого значения умножению на константу, так как реализация того же алгоритма может быть в сто раз быстрее или медленнее, будучи перенесенной на другую машину. Но рост времени вычислений при изменении count не зависит от таких технических деталей;

понятно, что не имеет значения и константная аддитивная составляющая: $$O(count^2 + 1000)$$ означает то же самое, что и $$O(count^2)$$. Конечно, константа может оказывать влияние при небольших значениях count, но с его ростом влияние становится ничтожным;

аналогично: любая аддитивная составляющая с меньшим значением экспоненты также не оказывает влияния на порядок величины – $$O(count^3 + count^2)$$ означает то же самое, что и $$O(count^3)$$.

Как следствие, чтобы выразить тот факт, что алгоритм работает константное время, более точно – что на любой платформе время выполнения ограничено константой, будем говорить, что время работы O(1). Конечно с тем же успехом можно писать O(37) или O(1000), но принято писать O(1).

Математические основы

Нотация "О-большое" может показаться неформальной, но ее можно строго определить, как отношение между функциями.

Определение: нотация "О-большое" и абстрактная сложность

Пусть f и g – две функции над натуральными числами, задающие отображение в положительные вещественные числа. Говорят, что f есть O (g) – или, в более общем виде, f (n) является O (g (n)), указывая аргумент, – если существует константа K, такая, что f (n) / g (n)< K для каждого натурального числа n.

Алгоритм является O (g (n)) по времени или по памяти, если функция, задающая время выполнения или требуемый объем памяти при входном размере n, есть O (g (n)).

При анализе сложности алгоритма можно встретиться с таким выражением, как "$$f (n) = g (n) + O (n^2)$$", что является сокращением записи "f (n) = g (n) + s (n) для некоторой функции s, где s (n) есть $$O (n^2)$$". Тем самым устанавливается, что f "подобна" g, отличаясь на терм $$O (n^2)$$.

Следствием определения является тот факт, что если функция есть $$O (n^2)$$, то верно, что она есть также $$O (n^3)$$, $$O (n^4)$$ и так далее. Это потому, что О-большое задает верхнюю границу, а не представляет точную оценку. Полезные утверждения, связанные со сложностью, часто имеют вид: "Доказано, что сложность данного алгоритма есть $$O (n^{2.5})$$. Можно ли улучшить оценку и доказать, что его сложность есть $$O (n^2)$$?"

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

При анализе сложности алгоритмов часто возникают логарифмы. Например, лучшие алгоритмы сортировки списка из n элементов имеют сложность $$O(n\times(\log n))$$. В этой формуле не указывается основание системы логарифмов (2 или 10), поскольку изменение основания приводит к появлению мультипликативной константы $$\log_b n=\log_b a\times\log_a n$$.

Лучшее использование выигрыша в лотерею

Соглашение об игнорировании мультипликативной константы на первый взгляд кажется удивительным. Алгоритм, работающий $$count^2$$ наносекунд, считается хуже алгоритма, работающего $$10^6 * count$$ наносекунд, хотя последний работает быстрее при count меньше миллиона.

Следующее наблюдение позволяет понять преимущества алгоритмов, лучших по сложности. Рассмотрим четыре алгоритма, каждый из которых, непрерывно работая на вашем компьютере, за 24 часа может решить задачу максимальной размерности соответственно $$N_1, N_2, N_3, N_4$$. Предположим теперь, что алгоритмическая сложность наших алгоритмов соответственно составляет $$O(n), O(n \log n), O(n^2), O(2^n)$$. Предположим еще (что менее вероятно), что вы выиграли в лотерею большую сумму и можете купить новый компьютер, работающий в 1000 раз быстрее старого. Что это может вам дать?

Для первого алгоритма со сложностью O(n) теперь можно будет решить задачу в 1000 раз большего размера – $$1000 * N_1$$.

Для второго алгоритма со сложностью $$O(n \log n)$$ теперь можно будет решить задачу большего размера с множителем, близким к 1000.

Для третьего алгоритма со сложностью $$O(n^2)$$ теперь можно будет решить задачу большего размера с существенно меньшим множителем, равным квадратному корню из 1000, примерно равным 32.

Для четвертого алгоритма увеличение размера почти неощутимо, размер задачи увеличится на 10 (не в 10 раз, а на 10!).

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

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

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

Абстрактная сложность на практике

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

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

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

Минимальная сложность, также называемая сложностью в лучшем случае, дающая время или память для случая, на котором алгоритм работает быстрее всего (требует минимальной памяти). Этот критерий используется редко – его любят те, кто верит в удачу.

Презентация структур данных

В оставшейся части лекции будем рассматривать фундаментальные структуры данных. Их презентация основана на библиотеке EiffelBase, содержащей повторно используемые классы для всех изучаемых понятий: ARRAY, LINKED_LIST, HASH_TABLE, STACK и так далее.

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

5.4. Массивы

Начнем с самого распространенного вида контейнера – массива.

Понятие массива является программистским понятием, но его важность определяется свойствами главной памяти компьютера, которая известна как RAM (Random Access Memory) – память со случайным доступом. Несмотря на такое имя, вовсе не предполагается, что в момент доступа к ячейке памяти компьютер случайным образом выбирает, из какой ячейки выбрать (или куда записать) значение (идея, сама по себе интересная). На самом деле эта память предполагает, что время доступа к ее ячейкам – для чтения или модификации – не зависит от адреса ячейки (понятие "случайный" следует трактовать, как во фразе: "вы можете случайным образом выбрать ячейку и не беспокоиться о времени доступа"). Если у Вас память в 2 GB, то доступ к первой ячейке (адрес 0) или к последней занимает одно и то же время.

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

(рис 5.3) Последовательный и случайный доступ

Свиток слева позволяет последовательное чтение (и запись). Справа показаны почтовые ящики, с прямым к ним доступом.

Массивы используют все преимущества прямого доступа, позволяя работать со структурой данных, хранимой в непрерывном сегменте памяти; доступ к каждому элементу массива возможен по индексу (номеру) элемента:

(рис 5.4)

Границы и индексы

Массив имеет нижнюю и верхнюю границы, задаваемые запросами класса ARRAY[G]:

lower: INTEGER
        — Минимальный индекс.
upper: INTEGER
        — Максимальный индекс.
        

Инвариант класса устанавливает, что count – число элементов (также известное как емкость) задается соотношением upper – lower + 1. Так как count >= 0, требуется выполнение условия:

lower <= upper + 1
        

Случай lower = upper соответствует массиву с одним элементом, lower = upper +1 соответствует пустому массиву (эти наблюдения можно визуализировать, передвигая на последнем рисунке вправо нижнюю границу или влево верхнюю, пока они не пересекутся). Это законные состояния массива.

Почувствуй методологию

Принцип экстремальных случаев

При проектировании структуры объектов, например контейнеров, рассматривайте экстремальные случаи – пустую структуру, структуру с одним элементом, "полную" структуру, если задана максимальная емкость, – и убедитесь, что определения имеют смысл и в этих случаях.

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

Инвариант класса является первичным руководством для проверки того, что определение все еще имеет смысл. Здесь случай lower = upper +1 остается совместимым с инвариантом класса lower <= upper +1, полученное при этом минимальное значение count (upper -lower+1) все еще удовлетворяет требованиям.

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

valid_index (i: INTEGER): BOOLEAN
        — Является ли i правильным индексом, лежащим внутри границ?
    ensure
        Result implies ((i >= lower) and (i <= upper))
        

Создание массива

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

your_array: ARRAY [SOME_TYPE]
…
create your_array.make (your_lower_bound, your_upper_bound)
При этом используется процедура создания:
make (min_index, max_index: INTEGER)
— Выделить память массиву; установить интервал для индекса min_index ..
— max_index
    — установить все значения по умолчанию.
    — (Сделать массив пустым, если min_index = max_index + 1).
require
    valid_bounds: min_index <= max_index + 1
ensure
    lower_set: lower = min_index
    upper_set: upper = max_index
    items_set: all_default
        

Как показывают первые два предложения в постусловии, процедура устанавливает lower и upper в соответствии с переданными в нашем примере значениями your_lower_bound и your_upper_bound. Они могут быть произвольными выражениями, например, константами:

create yearly_twentieth_century_revenue.make (1901,2000)
        

Здесь значения границ задаются в тексте программы, но они могут зависеть от переменных, входящих в выражения:

create another_array.make (m, m+n)
        

В приведенном примере интервал индексов имеет собственный смысл, задавая годы 20-го столетия. Если же просто необходимо создать массив из n значений, то нижняя граница обычно задается равной 1, а верхняя – n:

create simple_array.make (1,n)
        

Язык С и его последователи (С++, Java, C#) требуют, чтобы у всех массивов начальный индекс был равным 0. В примерах, таких как "годы 20-го столетия", это требует взаимных преобразований (сложение и вычитание 1901 в примере) между физическим индексом и его представлением. Для таких случаев, как simple_array, выбор между 0 и 1 – дело вкуса. Если вы, подобно мне, предпочитаете рассматривать большой палец на руке как первый, а не нулевой, а мизинец как пятый, а не четвертый, то выбор 1 кажется более разумным. Менее субъективный довод состоит в том, что начиная нумерацию элементов с нуля, приходится заканчивать ее номером n-1 для последнего элемента, и это, как показывает практика, является вечным источником ошибок.

Запрос all_default в последнем предложении постусловия выражает тот факт, что все элементы массива типа ARRAY [SOME_TYPE] будут после создания иметь значения по умолчанию, определяемые типом SOME_TYPE: ноль для INTEGER и REAL, false – для булевских, void – для любого ссылочного типа.

Доступ и модификация элементов массива

Приведем базисный запрос и команду для получения и модификации элемента массива:

item (i: INTEGER): G
        — Элемент с индексом i, если это правильный индекс.
    require
        valid_key: valid_index (i)
put (v: like item; i: INTEGER)
        — Изменить значение элемента с индексом i, если это правильный
            — индекс, на значение v.
    require
        valid_key: valid_index (i)
    ensure
        inserted: item (i) = v
        

В обоих случаях предусловие требует, чтобы индекс находился в границах массива. Типичное применение команды, если уже объявлены переменные your_array: ARRAY [SOME_TYPE] и your_value: SOME_TYPE:

your_array.put (your_value, your_index)
        

Вызов метода put установил новое значение соответствующего элемента массива:

(рис 5.5)

Заметьте порядок следования аргументов: сначала новое значение, затем индекс. После этого вызова оператор

your_value:= your_array.item (your_index)
        

присвоит переменной your_value значение элемента массива с индексом your_index.

Постусловие put показывает, что непосредственно после выполнения put значение item с заданным индексом есть значение, заданное в put. Примеры с put и item корректны только при условии, что гарантируются "правильные" индексы. Если гарантии нет, то следует использовать вызовы в форме:

if your_array.valid_index (your_index) then
your_array.put (your_value, your_index)
else
…
end
        

Аналогично для item.

Для любой разумной реализации массивов вызов put и item выполняется за константное время – О(1). Это свойство используемой для хранения массивов RAM-памяти и причина широкого использования массивов.

Скобочная нотация и команды присваивания

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

your_value:= your_array [your_index]
    — Краткая запись для your_value:= your_array.item (your_index).
your_array [your_index]:= your_value
    — Краткая запись для your_array.put (your_value, your_index).
        

Это особенно удобно для таких операторов, как

a [i]:= a [i] + 1         [3]
        

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

Ничего магического в скобочной записи нет, и она не является спецификой массивов. Для того, чтобы применить ее к любому типу, где это имеет смысл, достаточно включить сочетание alias "[]" после имени соответствующего метода при его объявлении. Именно это и сделано в классе ARRAY для item:

item(i: INTEGER) alias "[]": G assign put
        — Элемент с индексом i, если индекс правильный
    require
        valid_key: valid_index (i)
    do
        —… Реализация метода …
    end
        

Добавление alias "[]" к имени метода означает, что квадратные скобки являются псевдонимом имени метода ( в данном случае – item) – еще одним способом вызова метода. В результате нотация

your_array [i]
        

это синоним (псевдоним) для

your_array.item (i)
        

В объявлении item также присутствует конструкция assign put. Любой запрос q, независимо от того, имеет ли он псевдоним в виде квадратных скобок, можно пометить assign c, где c – команда из того же класса, которому принадлежит запрос. Эффект состоит в том, чтобы сделать корректной нотацию, подобную присваиванию:

your_array.item(i):= your_value         [4]
        

представляющую краткую запись вызова команды put

your_array.put (your_value, i)          [5]
        

Предложение assign связывает команду (put) с запросом (item). Такие команды называются командами-присваивателями.

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

Поскольку item имеет скобочный псевдоним и связан с присваивателем, вполне законно использовать скобочную форму в последнем вызове:

your_array[i]:= your_value              [6]
        

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

Механизм команд-присваивателей применим к любым запросам, в том числе к атрибутам. Операторы 5.4, 5.6 хотя и имеют форму оператора присваивания, таковыми не являются, поскольку, как известно, скрытие информации запрещает прямое присваивание атрибутам (полям) класса. Они являются простыми вызовами процедур, эквивалентными 5.5 и соблюдающими все ОО-принципы. Это просто "синтаксический сахар", добавленный для удобства записи.

Большинство языков программирования, начиная с Pascal, C и C++ до Java и C#, предлагают скобочную запись для массивов, как при доступе (your_array [i]), так и при модификации (your_array [i]:= your_value). В большинстве случаев эта форма является спецификой массивов, а сами массивы рассматриваются как встроенный в язык специфический тип данных. В языке Eiffel ARRAY рассматривается как обычный класс с методами item и put, согласующийся с другими структурами данных и ОО-подходом (позволяя, например, наследование от класса ARRAY). Язык предлагает скобочную нотацию как псевдоним, благодаря конструкции alias "[]". Это общая конструкция, применимая не только к массивам. Она будет использоваться и при работе с другими структурами данных, в частности, с хэш-таблицами. Ее можно применять с тем же успехом при создании собственных классов.

Изменение размеров массива

В любой момент выполнения массивы имеют границы – lower и upper, следовательно, фиксированное число (count) элементов. Предусловие valid_index методов put и item отражает это свойство. В большинстве языков программирования это свойство массива устанавливается однажды и навсегда либо статически (используя константные границы), либо динамически в момент создания. В Eiffel можно перестраивать массив, используя метод resize:

resize (min_index, max_index: INTEGER)
            — Изменение границ массива, вниз к min_index
            — и вверх к max_index. Существующие элементы сохраняются.
        require
            good_indexes: min_index <= max_index
        ensure
            no_low_lost: lower = min_index.min (old lower)
            no_high_lost: upper = max_index.max (old upper)
        

Функции min и max, применяемые в постусловии, являются функциями над двумя целыми числами, дающими соответственно минимум и максимум из текущего числа, вызывавшего функцию, и ее аргумента.

Чаще всего для перестройки границ массива не вызывается специальный метод – она индуцируется при вызове метода force. Обычно, если нужно изменить значение элемента массива, базисным механизмом является метод put(v, i) с предусловием: valid_index(i). Это правильный способ работы, но при условии, что вы заранее знаете, какие элементы массива могут понадобиться. Если же в своих расчетах вы ошиблись, то это может привести к отказу в работе программы. В таких случаях для работы с массивом вместо put следует использовать метод force:

force (v: like item; i: INTEGER)
          — Заменить значение элемента массива на v, если индекс в допустимых
          — пределах.
          — Всегда применять перестройку границ массива, если индекс выходит
          — за пределы.
          —Сохранять существующие элементы
    ensure
          inserted: item (i) = v
          higher_count: count >= old count
        

В отличие от put, метод force не имеет предусловия, а потому всегда применим. Если i лежит вне интервала lower.. upper, процедура вызовет resize для изменения границ так, чтобы индекс оказался внутри нового интервала.

Из-за того, что реализация массива требует отведения ему непрерывного участка памяти, при перестройке массиву отводится обычно новый участок памяти и происходит копирование старых элементов массива:

(рис 5.6)

Перераспределение и копирование – это дорогие операции со сложностью O(count). В результате и force имеет сложность O(count), в то время как сложность put – O(1). Очевидно, что force следует использовать с осторожностью. Заметьте, что реализация force вполне разумна: она вызывает resize только при необходимости и, что более важно, изменяет размер массива с запасом, по умолчанию размер массива при перестройке увеличивается на 50%.

your_array.force (some_value, your_array.count + 1)
        

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

Использование массивов

Массив типа ARRAY [G] представляет всюду определенную функцию, задающую отображение целочисленного интервала lower..upper в G. Если после создания границы lower и upper не изменяются или редко изменяются, то реализация высокоэффективна: так, доступ к значению и его модификация имеет сложность O (1) и, следовательно, работает быстро. Это делает массивы подходящими в тех случаях, когда:

необходимо обрабатывать множество значений, ассоциированных с целочисленным интервалом;

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

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

Производительность операций над массивами

Вот итоговая таблица, содержащая стоимость операций.

Операция	Метод в классе ARRAY	Сложность	Комментарий
Доступ по индексу	item alias "[]"	O(1)
Замена по индексу	put alias "[]"	O(1)
Замена по индексу вне текущих границ	force	O(count)	Требует перераспределения массива. Только небольшая часть последовательных выполнений метода будет причиной перераспределения
Вставка нового элемента		O(count)	Требует перенумерации индексов. У класса нет такого метода
Удаление элемента		O(count)	Требует перенумерации индексов. У класса нет такого метода

5.5. Кортежи

Массивы однородны: в экземпляре ARRAY [T] все элементы принадлежат типу T или типу, совместимому с T. Кортежи (Tuples) подобны массивам, но они могут содержать значения разных типов. Рассмотрим объявление:

tup: TUPLE [number: INTEGER, street: STRING, resident: PERSON]
    

Возможные значения tup во время выполнения представляют последовательности из трех компонентов, первый из которых имеет тип INTEGER, второй – STRING, третий – PERSON, предполагая, что такой класс существует. Такие кортежи полезны в различных приложениях, отражая тот факт, что в некотором доме с номером number на некоторой улице street живет гражданин resident.

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

tup:= [99, "Rue de Rivoli", Louvre_museum_curator]         [7]
    

Термин tuple в английский пришел из математики, где тройки, четверки называются triple, quadruple и по аналогии n-tuple. На русском мы говорим двойка, тройка и по аналогии n-ка (энка), но в переводах чаще используется более благозвучный термин "кортеж", понимаемый как последовательность из n значений.

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

Операция	Нотация	Сложность	Комментарий
Доступ к компоненту	t.comp	O(1)	Смотри ниже о нотации
Замена компонента	t.comp:= value	O(1)
Вставка, удаление		Неприменима

Интерес к кортежам в другом: этот механизм языка позволяет описать простым и ясным способом структуры данных без обращения к классам. В нашем примере 5.7, где задавалось значение кортежа в целом, теги – number, street, resident – не играли роли, но они важны для доступа к индивидуальным значениям.

После выполнения 5.7 tup.number имеет значение 99. Теги можно также использовать и для задания значений компонентам, поскольку они рассматриваются как атрибуты с ассоциированными командами-присваивателями, что позволяет писать такие операторы, как:

tup.resident:= some_person
    

Конечно, можно было бы обойтись без типа TUPLE, используя классы, такие как:

class CENSUS_RECORD feature
        number: INTEGER assign set_number
        street: STRING assign set_street
        resident: PERSON assign set_resident
        set_number (n: INTEGER) do number:= n ensure number = n end
        … set_street, set_resident like set_number …
end
    

Над переменной cr типа CENSUS_RECORD были бы допустимы те же операции, что и над tup: доступ к полю (cr.number), модификация поля (cr.resident:= some_person).

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

Заметим, что теги не влияют на тип кортежа, фактически, они не обязательны. Ранее определенный кортеж можно задать как TUPLE [a: INTEGER, b: STRING, x: PERSON ] или просто TUPLE [INTEGER,STRING, PERSON ], если нет необходимости обращаться к компонентам по имени.

Синтаксически такие типы выглядят как универсально порожденные типы, подобные LIST [T]. Действительно, концепции очень похожи, но формально не существует класса TUPLE, поскольку это потребовало бы задать его с произвольным числом параметров, в то время как универсальный класс имеет фиксированное число параметров (один параметр у классов ARRAY [G] и LIST [G], два в HASH_TABLE [G, KEY]). Для кортежных типов можно описать последовательности любой длины: TUPLE без параметров задает все последовательности, TUPLE [T] – последовательность по меньшей мере из одного элемента, первый из которых имеет тип T, и так далее.

Это замечание определяет свойство согласованности кортежных типов: можно присваивать выражение типа TUPLE [T, U, V] переменной того же типа или любого из следующих типов – TUPLE [T, U]; TUPLE [T]; просто TUPLE. Последний из них (не класс, как отмечалось, но тип) покрывает задание всех возможных кортежей.