Невозможно. Нет способа сосчитать количество установленных бит в числе, не проходя по нему циклом. А множество так и организовано. Может, есть какая-то функция, которая внутри себя уже делает такой цикл, но я и такой не знаю.
Slicer
Специалист — это варвар, невежество которого не всесторонне :)
Здравствуйте, Balax, Вы писали:
B>Пример:
B>type B> TSetInt = set of 0..20;
B>var B> s: TSetInt = [1, 5, 15];
B>Как определить количество элементов множества? B>Нужно что-то типа B> Count := Length(s); // Count = 3
B>PS: Желательно без использования циклов
Без циклов нельзя. Самы простой пример:
var
I : TSetInt;
Count : Integer;
begin
Count := 0;
for I := Low (TSetInt) to High (TSetInt) do
if I in S then
Inc (Count);
end;
Re[2]: Определить количество элементов в множестве
Здравствуйте, Danchik, Вы писали:
D>Без циклов нельзя. Самы простой пример: D>
D>var
D> I : TSetInt;
D> Count : Integer;
D>begin
D> Count := 0;
D> for I := Low (TSetInt) to High (TSetInt) do
D> if I in S then
D> Inc (Count);
D>end;
D>
Это я, конечно, знаю, но хотел получить оптимальным способом, а жаль...
Но все равно спасибо всем ответившим.
Re[3]: Определить количество элементов в множестве
Здравствуйте, Balax, Вы писали:
B>Здравствуйте, Danchik, Вы писали:
D>>Без циклов нельзя. Самы простой пример: D>>
D>>var
D>> I : TSetInt;
D>> Count : Integer;
D>>begin
D>> Count := 0;
D>> for I := Low (TSetInt) to High (TSetInt) do
D>> if I in S then
D>> Inc (Count);
D>>end;
D>>
B>Это я, конечно, знаю, но хотел получить оптимальным способом, а жаль... B>Но все равно спасибо всем ответившим.
Как сказал Slicer: биты нужно перебирать. А без цикла я себе это тоже не представляю...
Можна правда написать универсальную функцию, но в нее придется передавать TypeInfo (об этом будет поподробнее если интересно)
Re[4]: Определить количество элементов в множестве
От:
Аноним
Дата:
14.10.05 05:46
Оценка:
D>Как сказал Slicer: биты нужно перебирать. А без цикла я себе это тоже не представляю... D>Можна правда написать универсальную функцию, но в нее придется передавать TypeInfo (об этом будет поподробнее если интересно)
Давай поподробнее
Re[3]: Определить количество элементов в множестве
B>Это я, конечно, знаю, но хотел получить оптимальным способом, а жаль... B>Но все равно спасибо всем ответившим.
Тут оптимальный способ надо выбирать самому. Либо терять время на проходах, либо терять память — сделать таблицу со всеми возможными вариантами числа и количеством включенных битов и брать значение из таблицы.
Re[5]: Определить количество элементов в множестве
Здравствуйте, Аноним, Вы писали:
D>>Как сказал Slicer: биты нужно перебирать. А без цикла я себе это тоже не представляю... D>>Можна правда написать универсальную функцию, но в нее придется передавать TypeInfo (об этом будет поподробнее если интересно)
А>Давай поподробнее
Ну чтож, Аноним, если интересно то держи:
uses
TypInfo
...
function ElementCount (const aSet; aTypeInfo : PTypeInfo) : Integer;
var
aTypeData : PTypeData;
aCompTypeData : PTypeData;
K: Integer;
aDataByte : PByte;
aBitByte : Byte;
aCurIndex : Integer;
begin
Assert (aTypeInfo <> nil, 'aTypeInfo is required parameter in ElementCount');
Assert (aTypeInfo.Kind = tkSet, 'aTypeInfo is not Set Type');
Result := 0;
aTypeData := GetTypeData (aTypeInfo);
if aTypeData.CompType = nil then
begin
aDataByte := @aSet;
for K := 0 to aTypeData.MaxLength - 1 do begin
aBitByte := aDataByte^;
while aBitByte <> 0 do begin
if aBitByte and 1 <> 0 then
Inc (Result);
aBitByte := aBitByte shr 1;
end;
Inc (aDataByte);
end;
end else begin
aCompTypeData := GetTypeData (aTypeData.CompType^);
aDataByte := @aSet;
for K := aCompTypeData.MinValue shr 3 to aCompTypeData.MaxValue shr 3 do begin
aBitByte := aDataByte^;
aCurIndex := K shl 3;
while aBitByte <> 0 do begin
if (aBitByte and 1 <> 0) and (aCurIndex >= aCompTypeData.MinValue) then
Inc (Result);
Inc (aCurIndex);
if aCurIndex > aCompTypeData.MaxValue then
Break;
aBitByte := aBitByte shr 1;
end;
Inc (aDataByte);
end;
end;
end;
И пример использования:
type
TElement = (el1, el2, el3, el4);
TElementSet = set of TElement;
procedure TForm1.Button1Click(Sender: TObject);
var
aSet : TElementSet;
aElementCount : Integer;
begin
aSet := [el1, el3, el4];
aElementCount := ElementCount(aSet, TypeInfo (TElementSet));
end;
Re[4]: Определить количество элементов в множестве
Здравствуйте, Dimonka, Вы писали:
D>Тут оптимальный способ надо выбирать самому. Либо терять время на проходах, D>либо терять память — сделать таблицу со всеми возможными вариантами числа и D>количеством включенных битов и брать значение из таблицы.
Ни то, ни другое меня не устраивает, но решил ограничиться проходом, т.к. определять количество элементов приходится не так часто.
Просто хотел найти более изящный способ.
Re[4]: Определить количество элементов в множестве
Здравствуйте, Danchik, Вы писали:
D>Как сказал Slicer: биты нужно перебирать. А без цикла я себе это тоже не представляю... D>Можна правда написать универсальную функцию, но в нее придется передавать TypeInfo (об этом будет поподробнее если интересно)
Конечно, было интересно узнать и я хотел попросить вас выложить, но Аноним меня опередил.
Насколько, судя по вашему примеру, я понимаю, что битовое представление множества заключается так:
s: set of 0..7 (sizeof(s) = 1 байт)
s := [2, 5] -> битовое представление: 00100100
Так ли?
Re[5]: Определить количество элементов в множестве
Здравствуйте, Balax, Вы писали:
B>Здравствуйте, Danchik, Вы писали:
D>>Как сказал Slicer: биты нужно перебирать. А без цикла я себе это тоже не представляю... D>>Можна правда написать универсальную функцию, но в нее придется передавать TypeInfo (об этом будет поподробнее если интересно) B>Конечно, было интересно узнать и я хотел попросить вас выложить, но Аноним меня опередил. B>Насколько, судя по вашему примеру, я понимаю, что битовое представление множества заключается так: B>s: set of 0..7 (sizeof(s) = 1 байт) B>s := [2, 5] -> битовое представление: 00100100 B>Так ли?
Именно так.
Re[5]: Определить количество элементов в множестве
Здравствуйте, Balax, Вы писали:
D>>Тут оптимальный способ надо выбирать самому. Либо терять время на проходах, D>>либо терять память — сделать таблицу со всеми возможными вариантами числа и D>>количеством включенных битов и брать значение из таблицы. B>Ни то, ни другое меня не устраивает, но решил ограничиться проходом, т.к. определять количество элементов приходится не так часто. B>Просто хотел найти более изящный способ.
А чем предложенный способ не изящный? Создать таблицу на 256 элементов с количеством битов для каждого варианта и брать значение из таблицы. Если ипользуется больше 8 бит, то разбивать входящее число на байты, брать значение для каждого байта отдельно, а затем возвращать сумму. Куда уж изящнее и быстрее?
Примерно так:
BitCount := MyBitCountArray[byte(MyBitSet)];
и всё..
Могу показать для сетов из более 8 значений, если хочешь..
Re[6]: Определить количество элементов в множестве
D> while aBitByte <> 0 do begin D> if aBitByte and 1 <> 0 then D> Inc (Result); D> aBitByte := aBitByte shr 1; D> end;
Лучше бы попробовать подготовить массив из 8 вариантов байта, по одному на каждый бит, и проверять через And:
if (srcByte and TestSample[bit_in_byte]) <> 0 then Inc(result)
Может, так получится быстрее, т.к. процессоры класса P4 не любят операции битового сдвига.
Можно было бы еще немножко ускорить, но Object Pascal не предоставляет доступа к регистру флагов.
Slicer
Специалист — это варвар, невежество которого не всесторонне :)
Re[7]: Определить количество элементов в множестве
Здравствуйте, Slicer [Mirkwood], Вы писали:
D>> while aBitByte <> 0 do begin D>> if aBitByte and 1 <> 0 then D>> Inc (Result); D>> aBitByte := aBitByte shr 1; D>> end; SM>Лучше бы попробовать подготовить массив из 8 вариантов байта, по одному на каждый бит, и проверять через And: SM>
if (srcByte and TestSample[bit_in_byte]) <> 0 then Inc(result)
Может, так получится быстрее, т.к. процессоры класса P4 не любят операции битового сдвига. SM>Можно было бы еще немножко ускорить, но Object Pascal не предоставляет доступа к регистру флагов.
SM>Slicer
Черт, забыл написать, что пример был создан на скорую руку, просто чтобы показать куда рыть
Для себя я бы это дело написал на чистом асме
Re[6]: Определить количество элементов в множестве
Здравствуйте, Dimonka, Вы писали:
D>А чем предложенный способ не изящный? Создать таблицу на 256 элементов с количеством битов для каждого варианта и брать значение из таблицы. Если ипользуется больше 8 бит, то разбивать входящее число на байты, брать значение для каждого байта отдельно, а затем возвращать сумму. Куда уж изящнее и быстрее? D>Могу показать для сетов из более 8 значений, если хочешь..
Такой способ подходит, если надо очень часто вычислять количество, не теряя при этом скорость.
Для остальных форумчан можешь выложить, а мне идея понятна.
D>А чем предложенный способ не изящный? Создать таблицу на 256 элементов с количеством битов для каждого варианта и брать значение из таблицы. Если ипользуется больше 8 бит, то разбивать входящее число на байты, брать значение для каждого байта отдельно, а затем возвращать сумму. Куда уж изящнее и быстрее?
Особенно учитывая, что таблица не на 256 элемантов, а 2^256, а это резко меняет дело, мумеешь найти хотябы винчестер такой емкости, не говорю уж про память?
Re[7]: Определить количество элементов в множестве
D>>А чем предложенный способ не изящный? Создать таблицу на 256 элементов с количеством битов для каждого варианта и брать значение из таблицы. Если ипользуется больше 8 бит, то разбивать входящее число на байты, брать значение для каждого байта отдельно, а затем возвращать сумму. Куда уж изящнее и быстрее?
AP>Особенно учитывая, что таблица не на 256 элемантов, а 2^256, а это резко меняет дело, мумеешь найти хотябы винчестер такой емкости, не говорю уж про память?
Что-то я не понял, откуда такая степень появилась? Можно увидеть пример?
Хотя.. 256 бит — это 32 байта. Тебе сосчитать, сколько времени займёт подобное вычисление в тактах на ассемблере?
Re[7]: Определить количество элементов в множестве
D>>А чем предложенный способ не изящный? Создать таблицу на 256 элементов с количеством битов для каждого варианта и брать значение из таблицы. Если ипользуется больше 8 бит, то разбивать входящее число на байты, брать значение для каждого байта отдельно, а затем возвращать сумму. Куда уж изящнее и быстрее?
AP>Особенно учитывая, что таблица не на 256 элемантов, а 2^256, а это резко меняет дело, мумеешь найти хотябы винчестер такой емкости, не говорю уж про память?
Ты не понял! Не обязательно ведь все 256 бит анализировать сразу, можно группами по 8 бит (байт!). На каждую группу получится, очевидно, 256 вариантов
Slicer
Специалист — это варвар, невежество которого не всесторонне :)
Re[8]: Определить количество элементов в множестве
D>>>А чем предложенный способ не изящный? Создать таблицу на 256 элементов с количеством битов для каждого варианта и брать значение из таблицы. Если ипользуется больше 8 бит, то разбивать входящее число на байты, брать значение для каждого байта отдельно, а затем возвращать сумму. Куда уж изящнее и быстрее?
AP>>Особенно учитывая, что таблица не на 256 элемантов, а 2^256, а это резко меняет дело, мумеешь найти хотябы винчестер такой емкости, не говорю уж про память?
SM>Ты не понял! Не обязательно ведь все 256 бит анализировать сразу, можно группами по 8 бит (байт!). На каждую группу получится, очевидно, 256 вариантов :
Это к вопросу о циклах, С циклами все просто и нет нужды делать таблично, операция редкая над небольшим количеством данных,
Re[7]: Определить количество элементов в множестве
Здравствуйте, Hacker_Delphi, Вы писали:
H_D>Если уж говорить про оптимизацию — надо однозначно пользовать асм и команду BSF, благо она еще с 486 проца есть в системе команд....
Спорный вопрос — надо смотреть, как она в конвейеры ляжет. За сколько выполнится, если точнее, и каком вычислительном модуле. Я так навскидку не вспомню, разумеется Наверное, в ALU, а вот за сколько...
Slicer
Специалист — это варвар, невежество которого не всесторонне :)