Множества

← →
vint45 (2005-01-18 11:42) [0]

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

Пример:

type
TAAA = (taAA, taAAA);
TSAAA = set of TAAA;

TBBB = record
c: TSAAA;
end;

const
arrBBB: array[0..2] of TBBB =
((c: []),
(c: [taAA, taAAA]),
(c: [taAAA])); -- вроде красиво

-- код программы
как определить какие элементы множества хранятся во 2-м элемента массива arrB[2]? Это можно сделать простым перечислением всех элементов типа TAAA и оператором in:
for inc1:=Low(TAAA) to High(TAAA) do
if inc1 in arrBBB[2] then -- элемент входит

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

← →
Poirot © (2005-01-18 12:19) [1]

А ты математику вспомни и скажи, как там определялось какие элементы есть в множестве :)

← →
vint45 (2005-01-18 12:46) [2]

ну так ты напомни, а еще лучше приведи код для выбора всех элементов множества, а то что-то я торможу :)

← →
Digitman © (2005-01-18 12:49) [3]

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

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

← →
Poirot © (2005-01-18 13:31) [4]

в математике татого сделать просто нельзя быстрее чем посмотреть принадлежит ли элемент множества подмножеству:)

← →
begin...end © (2005-01-18 18:04) [5]

> vint45 (18.01.05 11:42)

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

Можно. Но не нужно.

Множество фактически представляет собой битовый массив, т.е. массив битов. В этом массиве i-й бит равен 1, если элемент с соответствующим (i-м) номером входит во множество, и 0 - в противном случае. Размер множества зависит от того, сколько туда элементов может входить, и может быть определён на этапе компиляции.

Вот пример:

var MySet: set of Char; begin ShowMessageFmt("Размер переменной MySet равен %d байт", [SizeOf(MySet)]) end.

Если Вы выполните этот код, то получите сообщение с числом 32. Это означает, что переменная MySet занимает 32 байта, т.е. 32 * 8 = 256 битов. Почему именно 256? Потому, что переменные типа Char могут принимать только 256 значений.

Посмотрим на содержимое переменной MySet, когда она является пустым множеством. Для этого вначале напишем функцию, возвращающую значение нужного бита переменной. Вот она (в подробности вдаваться не нужно, достаточно лишь запомнить, что она возвращает True, если в переменной Value бит с индексом Index равен 1, и False - в противном случае):

function GetBit(var Value; Index: Cardinal): Boolean; begin Result := Odd(PByte(Cardinal(@Value) + Index div 8)^ shr (Index mod 8)) end.

А теперь смотрим на пустое множество:

var MySet: set of Char; I: Integer; begin MySet := []; for I := 0 to 255 do if GetBit(MySet, I) then ShowMessageFmt("%d-й бит переменной MySet равен 1", [I]) end.

Никакого сообщения Вы не увидите. Это подтверждает, что если MySet является пустым множеством, то все биты в переменной MySet обнулены.

Теперь посмотрим, что происходит с переменной MySet, если "включить" в это множество, например, символ "F". "Порядковый номер" (номер, возвращаемый функцией Ord) символа "F" во множестве символов типа Char равен 70. Так вот - после "включения" этого символа в множество MySet 70-й бит этой переменной просто выставляется в 1.

Пример:

var MySet: set of Char; I: Integer; begin MySet := []; // Включаем в множество MySet символ "F" Include(MySet, "F"); // Проверяем: какой бит теперь равен 1? for I := 0 to 255 do if GetBit(MySet, I) then ShowMessageFmt("%d-й бит переменной MySet равен 1", [I]) end.

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

Теперь рассмотрим конкретно Ваш случай.

type TA = (taAA, taAAA); TSA = set of TA; TB = record c: TSA end; var arrBBB: array [0..2] of TB;

Требуется проверить, какие значения типа TAAA включены в поле c 2-го элемента массива arrBBB. Есть 2 варианта - либо проверять, какие биты установлены (как мы это делали выше), либо делать так, как делали Вы - проверять на вхождение каждое значение типа.

1-й вариант:

var I: Integer; begin arrBBB[2].c := [taAAA]; // <-- Заполнение массива for I := 0 to 8 * SizeOf(arrBBB[2].c) - 1 do if GetBit(arrBBB[2].c, I) then ShowMessageFmt("В множество входит элемент с номером %d", [I]) end.

2-й вариант:

var I: TA; begin arrBBB[2].c := [taAAA]; // <-- Заполнение массива for I := Low(TA) to High(TA) do if I in arrBBB[2].c then ShowMessageFmt("В множество входит элемент с номером %d", [Ord(I)]) end.

Результат в обоих случаях получится одинаковым: входит элемент с "порядковым номером" 1, т.е. taAAA (у taAA этот "номер" равен 0).

Но код, сгенерированный компилятором для варианта 2, будет лучше (а написанный Вами код будет более прозрачным и понятным), чем код, сгенерированный для варианта 1.

Поэтому - можно, но не нужно.

← →
vint45 (2005-01-19 14:16) [6]

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

begin...end © (18.01.05 18:04) [5]
Если Вы выполните этот код, то получите сообщение с числом 32. Это означает, что переменная MySet занимает 32 байта, т.е. 32 * 8 = 256 битов. Почему именно 256? Потому, что переменные типа Char могут принимать только 256 значений.

Максимальный размер множества всегда равен 256 элементов в не зависимости от базового типа.

Цитата из хелпа:
The range of a set type is the power set of a specific ordinal type, called the base type; that is, the possible values of the set type are all the subsets of the base type, including the empty set. The base type can have no more than 256 possible values, and their ordinalities must fall between 0 and 255.

> [7] pasha_golub © (19.01.05 14:21)

> Максимальный размер множества всегда равен 256 элементов
> в не зависимости от базового типа.

Верно, но это НЕ противоречит тому, что сказал я.

Максимальный размер множества - да, именно 256 элементов. Но это не означает, что любая переменная-множество занимает 256 бит, или 32 байт. И "размер" этой переменной зависит именно от базового типа.

Выше я уже говорил, что множество типа Char имеет размер 32 байта. Теперь приведу другой пример.

type TMyType = (mtOne, mtTwo, mtThree, mtFour, mtFive, mtSix, mtSeven, mtEight); var MySet: set of TMyType; begin ShowMessageFmt("Размер переменной MySet составляет %d байт", [SizeOf(MySet)] end.

Размер этой переменной будет равен одному байту. Ведь совершенно незачем делать массив из 256 элементов (битов), если заранее известно, что использоваться из этих элементов будут только 8. Поэтому компилятор и "выделяет" только 1 байт.

Если теперь добавить в описание типа TMyType ещё и mtNine, то мощность этого типа будет равна 9, и соотвествующее множество будет занимать 2 байта (потому что выделить для переменной 1 1/8 байта компилятор просто не может).

Другими словами, размер переменной-множества может меняться от 1 до 32 байт, и размер этот зависит именно от мощности базового типа.

Множества Найти похожие ветки