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

 

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

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

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

532
9.
(b) Расстановка по составному ключу .Два или более значения индексных полей — составной ключ — дают возможность практически всегда однозначно выделить значение массива. Можно считать, что здесь используются новые 'большие' значения. Здесь, как правило, может нарушаться равномерность функции расстановки, тем не менее этот способ зачасту используется.
(c) Вырожденный случай 1: размер расстановочного поля равен числу значений ключей. Нет нужды хранить значения ключей в качестве компонентов наборов, представляющих абстрактный уровень (они вычисляются однозначно). Если размер расстановочно-го поля болье числа значений кл чей, то имеет место бессмысленная трата памяти, но этот выро денный случай поро встречается при использовании сликом моного механизма для ее не развившейся базы данных.
(d) Вырожденный случай 2: размер расстановочного поля равен единице. Это означает, что гроздь — весь массив, и он представляется списком, последовательность и иным способом. онятно, что нет смысла в расстановочной функции, но иногда этот вро ден-нй случай возникает на начальных этапах развития больой базы данных, в которой в дальнейшем без расстановки не обойтись.
4. Локально плотное представление. Оно используется в том случае, если нам заранее известна глобальная информация о строении массива, что часто случается в ходе больших вычислений с большими, но достаточно регулярно организованнми, матрицами.
усть имеется массив (матрица) следуего вида
С
A 0 B ^
0 C 0 )
(9.5)
Пусть Wa, Wb, Wc и Hab, Hc — числа элементов в ненулевых блоках матрицы по горизонтали и вертикали, соответственно, элементы строк и столбцов матриц нумеру тся с единицы. Тогда мо но построить
9.3. 533
F (k, 1) =
следуу функци :
1, если(0 < k ^ Wa)&(0 < l ^ Hab)
2, если(WA + Wc < k ^ Wa + Wb + Wc)&(0 < l ^ Hab)
3, если(Wa < k ^ Wa + Wc)&(Hab < l Hc + Hab) exception в остальных случаях
на мо ет рассматриваться в качестве функции расстановки для сле-дуего программируемого доступа:
D [k, l]=
( case F(k, l) of
1 : DA[k, l];
2 : DB[k - WA - WC, l - HAB];
3 : DC[k - WC, l - HAB];
end)
Ситуацию иллюстрирует рис. 9.11. В данном случае даже не потребовалось вводить расстановочное поле как структуру данных.
F ( k,l )
А
С
В
Рис. 9.11. Функция расстановки
ля всех вариантов массивов циклы всех видов допустим , причем они реализуются достаточно эффективно. Также для всех размеров массивов необходимо иметь функци вчисления размера массива, более того, отсутствие такой встроенной функции в стандартных язках программирования является, по алуй, одним из видов глупости, передаейся из поколение в поколение.
534
9.
9.3.5. Множества
но ество — это тип даннх, значения которого представля т мно е-ства значений другого, ранее определенного типа, называемого базовым типом множества. Особенностью конструктора set of T является то, что определяемые с его помощью объекты в высшей степени зависят от количества элементов в типе T и в принципе не содержат в себе в качестве компонент значения базового типа. В данном отношении конструктор множеств отличается от ранее рассмотреннх нами конструкторов, которые интегрировали значения базовх типов в определяеме ими структуры даннх. равда, самое тупое из приходящих на ум представлений множества: перечень всех элементов данного множества ({зщ,..., знп} : T) , — конечно, содержало бы эти элемент . о недостатки данного представления очевидн (тем не менее, в одном из упранений Вам предлагается найти случаи, когда такое представление мно ества оптимально, и подумать, как его организовать в таких случаях).
Другое представление множества естественно подсказывается изоморфной алгебре множеств математической структурой функций M : T — {0,
оскольку функция на конечном мно естве, в сво очередь, то е самое, что массив, то мно ество мо ет быть представлено как массив булевских значений.
type Set_T=array[T] of Boolean;
росим извинения у лбителей C/C++/C#, но примитивная логическая структура этих язков не позволяет вразить данну иде столь е просто и ясно. в какие ловуки ведут попытки дераться сликом близко к деталям реализации, м у е видели.13
Поскольку операции алгебры множеств над множествами A и B сводятся к логическим операциям над значениями предикатов x Є Ax Є B, вычисление объединений, пересечений и других операций булевой алгебры сводится к циклу по всем элементам T с применением соотвествуих булевых операций к их элементам. роверка равенства мно еств, вкл чения одного множества в другое и подсчет числа элементов множества также производится
12 Еще раз повторим, что изоморфизм математических понятий исключительно важен для программиста, поскольку изоморфные структуры эквивалентны лишь с математической точки зрения, на практике они дают различные представления понятий.
13 Впрочем, так же в любой области человеческой деятельности. Попытка прямо достичь цели чаще всего ведет в тупик, а победа, даже если она одержана, оказывается пирровой.
9.3. СТРУКТУРНЫЕ ТИПЫ
535
за один проход по массиву.
Таким образом, выделяются основные операции типа множеств (x, x1,... x2, y — значения базового типа T, S, S1, S2 — значения или переменные типа set of T ):
Предыдущая << 1 .. 183 184 185 186 187 188 < 189 > 190 191 192 193 194 195 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100