Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 190

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 184 185 186 187 188 189 < 190 > 191 192 193 194 195 196 .. 316 >> Следующая

1. x Є S — предикат;
2. Sl = S2 — предикат;
3. Sl П S2 — пересечение;
4. Sl U S2 — объединение;
5. Sl — S2 — дополнение;
6. Sl C S2 — предикат включение;
7. |S| — размер множества (число элементов).
оскольку физическая структура памяти маин близка к массиву булевх значений, представление множества можно сделать еще эффективнее. Hо в этом случае ну но четко представлять себе, какого размера мно ества мы стремимся представить. ростейие ресурсные рассмотрения приводят к четырем случаям, для которых реализации множественных типов должны принципиально различаться:
(I) маленькое n, меньшее либо равное числу разрядов адресуемого регистра маин Cell;
(II) небольшое n, меньшее величины k * Cell, где k — размер не очень боль-ого массива, затраты памяти на который мо но считать приемлемыми.
(III) конечное, но довольно больое n, когда несколько прямо построенных массивов приведут к неприемлемому расходу памяти;
(IV) величина n не определяется как конечное с точки зрения маинной памяти целое число.
Случай (I) наиболее легок с практической точки зрения: он реализуется наиболее эффективно, красиво и концептуально естественно на уровне маин-ной логики. При этом используются шкалы — битовые наборы, размещаемые в ячейках. Каждый бит шкалы указывает наличие или отсутствие того
536
9.
или иного признака. В частности, пустое мно ество — кала из всех нулей, множество всех возможных значений базового типа представляется шкалой из всех единиц. Указанные выше операции вычисляются почти что на уровне пары маиннх команд.
К примеру, если S1 и S2 — множества-шкалы со следующими значениями битов (нулевые значения не показан ), то их объединение вычисляется как логическая дизъюнкция шкал:
A: 1 1 1 1 1 1 1 1
B: 1 1 1 1 1 1
A U B: 1 1 1 1 1 1 1 1 1 1 1 1
В изобра ениях мно еств вместо круглх скобок, унаследованных от набора компонентов, часто использу т фигурные скобки.14
Случай (II) ненамного сложнее, но технические детали, которые придется использовать, несколько сниа т эффективность реализации, следуей принципам случая (I).
Случай (III) требует перехода от представления мно ества калой к массивам или спискам. В зависимости от моностей мно еств, с которыми предполагается иметь дело, а так е от фактически ну нх в данной обработке операций, могут оказаться полезнми плотные или разре енные массив , представляющие, соответственно плотные или разреженные множества, для работы с которыми применяются те же методы, что и для массивов. Но есть нанс, связаннй с тем, что в массивах явно задается индексирование, тогда как для мно еств оно избыточно. тс да, во-первых, возмо ность более эффективного расположения значений (какого?), а во-вторых, надстройку, связанную с заданием индексирования, можно либо исключить вовсе, либо сделать удобнее для выполнения нужных операций.
В данном случае есть три варианта представления:
• хранение значений — явный перечень элементов множества, например, в виде списка;
• хранение ссылок на значения — эту лучше, когда возможных значений не очень много, и их размер превышает размер памяти, требуемый для ссылки;
14 язке Pascal использу тся квадратне скобки.
9.3.
537
• хранение кодов значений — использование таблицы кодов (функция перекодировки — каждому значению однозначно сопоставляется его код) может оказаться экономнее явного перечня элементов (шкала — это частный случай данного метода, сслка — другой частнй случай).
Случай (IV). Вообе говоря, здесь требуется реализация символических вы-числений15 (не путать с символьными!), в которых объектами оперирования явля тся утвердения, т. е. предикаты, формируие мно ества. Таким образом, явное представление мно еств элементов, мест элементов или каких б то ни было значений базового типа либо их заменителей не требуется. Более того, оно было бы ограничительным по отношению к бесконечным множествам.
В языке Pascal есть только минимально необходимый набор операций над мно ествами. ормально базовй тип мно ества в этом язке и его раси-рениях дол ен бть перечислением. од единой синтаксической оболочкой в этом язке кро тся представления мно еств, представления коотрх соответствуют случаям (I) и (II). Этого хватает даже для множеств всех коротких целх чисел.
В языке Pascal и его расирениях име тся литерал для изобра ения мно еств. апример, мно ество четырех приемлемых состояний выхода из подпрограммы мо ет бть изобра ено как
const goodend= [OK, User_break, Suspended_and_saved, Negative_result].
Пожалуй, небольшие множества — это единственное 'гармоничное' средство в программировании, сочетаее наглядность с эффективность реализации.
Литеральные изображение множеств — нужное и полезное средство программирования. Возможны выражения типа множеств, для которых они явля-тся исходнми константами. ля реализации литеральнх изобра ений мно еств мо но предусматривать специальные представления с конверсией в стандартные представления. Естественное ограничение: за исключени-
15 Символические вычисления — раздел информатики и программирования, который изучает вычисления, представленные обозначениями значений (символами). Все, что можно вычислить в рамках символических вычислений — это преобразование символических выражений, направленные на их сокращение, на доказательство их свойств и т. п. В отличие от символических вычислений символьные вычисления имеют дело с данными символьного и строкового типов.
Предыдущая << 1 .. 184 185 186 187 188 189 < 190 > 191 192 193 194 195 196 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100