Количество элементов в множестве

← →
JanMihail (2008-07-02 15:08) [0]

Как рационально узнать количество элементов в множестве?
Например:
[1..7] - 7
[1, 3..5] - 4

← →
Сергей М. © (2008-07-02 15:19) [1]

Точно так же, как нерационально

← →
Правильный-Вася (2008-07-02 15:22) [2]

перебором?
несчетные множества дельфи вроде не поддерживает

← →
Игорь Шевченко © (2008-07-02 15:26) [3]

High - Low + 1

← →
Johnmen © (2008-07-02 16:05) [4]

Ord(High)+1

← →
Leonid Troyanovsky © (2008-07-02 16:29) [5]

> Игорь Шевченко © (02.07.08 15:26) [3]

> Johnmen © (02.07.08 16:05) [4]

Это ж не открытый массив. Или я чего-то не понял.

--
Regards, LVT.

← →
Anatoly Podgoretsky © (2008-07-02 16:34) [6]

> Игорь Шевченко (02.07.2008 15:26:03) [3]

Спорно, но имеет право на жизнь, если обоснуешь.

← →
Johnmen © (2008-07-02 16:46) [7]

> Leonid Troyanovsky © (02.07.08 16:29) [5]
> Или я чего-то не понял.

Просто телепаторы у всех по-разному срабатывают :)

← →
Sapersky (2008-07-02 17:32) [8]

Ну вот ещё вариант моего телепатора:

function GetElementCount(pSet : PByte; ByteSize : Integer): Integer;
Const BitCnt : array[ 0..255 ] of Byte =
(
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
);
Var n : Integer;
begin
Result := 0;
For n := 0 to ByteSize-1 do begin
Inc(Result, BitCnt[pSet^]);
Inc(pSet);
end;
end;

Использовать:
Cnt := GetElementCount(@aSet, SizeOf(aSet));

Идея утащена отсюда:
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable

← →
Sha © (2008-07-03 14:29) [9]

function CountOfSet(pSet: pchar; SizeOfBaseType: integer): integer; var Bound, Round, Value: integer; begin; Bound:=(SizeOfBaseType + 7) shr 3; Round:=Bound and -4; Value:=0; if Bound and 1<>0 then Value:=pByte(pSet + Bound - 1)^; if Bound and 2<>0 then Value:=(Value shl 16) + pWord(pSet + Round)^; Result:=0; while true do begin; while Value<>0 do begin; Value:=Value and (Value-1); inc(Result); end; Round:=Round-4; if Round<0 then break; Value:=pInteger(pSet+Round)^; end; end; type MyBaseType = (a=0, b=247, c=239); MySetType = Set of MyBaseType; const MyBaseSize = Ord(High(MyBaseType))-Ord(Low(MyBaseType))+1; procedure TForm1.Button2Click(Sender: TObject); var MySet: MySetType; Count: integer; begin; MySet:=[a,b,c]; Count:=CountOfSet(@MySet, MyBaseSize); ShowMessage(IntToStr(Count)); end;

По идее должно быть быстро для "неплотных" множеств.
Как следует не тестировалось.

← →
Leonid Troyanovsky © (2008-07-03 16:24) [10]

> Sha © (03.07.08 14:29) [9]

> По идее должно быть быстро для "неплотных" множеств.

Если оно такое неплотное, то можно модифицировать [8]
function GetElementCount(pSet : PByte; ByteSize : Integer): Integer; Const BitCnt : array[ 0..255 ] of Byte = ( .. ); procedure AddNextSum(var Value: Longint; Numbyte: Longint); var i: Longint; begin for i := 0 to Numbyte -1 do begin Inc(Value, BitCnt[pSet^]); Inc(pSet); end; end; Var n : Integer; begin Result := 0; For n := 0 to ByteSize div 4 -1 do begin if PLongint(pSet)^ = 0 then Inc(pSet, 4) else AddNextSum(Result, 4); end; AddNextSum(Result, ByteSize mod 4); end;

Not tested.

--
Regards, LVT.

← →
Sha © (2008-07-03 17:41) [11]

Наверно, будет также быстро, как с использованием таблицы.
Не тестировалось.

function ElementCount(pSet: pIntegerArray; Bound: integer): integer; var v, i: integer; begin; i:=Bound shr 2; v:=0; if Bound and 1<>0 then v:=pByte(integer(pSet) + Bound - 1)^; if Bound and 2<>0 then v:=v shl 16 + pWord(@pSet[i])^; Result:=0; while true do begin; v:=v - v shr 1 and $55555555; v:=v and $33333333 + v shr 2 and $33333333; v:=(v + v shr 4) and $0F0F0F0F; Result:=Result + v * $01010101 shr 24; dec(i); if i<0 then break; v:=pSet[i]; end; end; type MyBaseType = (a=0, b=247, c=239); MySetType = Set of MyBaseType; const MySetSize = (Ord(High(MyBaseType)) - Ord(Low(MyBaseType)) + 8) shr 3; procedure TForm1.Button2Click(Sender: TObject); var MySet: MySetType; Count: integer; begin; MySet:=[a,b,c]; Count:=ElementCount(@MySet, MySetSize); ShowMessage(IntToStr(Count)); end;

← →
Sha © (2008-07-03 18:14) [12]

Так, наверно, еще быстрее:
function ElementCount2(pSet: pIntegerArray; Bound: integer): integer; var v, i: integer; begin; i:=Bound shr 2; v:=0; if Bound and 1<>0 then v:=pByte(integer(pSet) + Bound - 1)^; if Bound and 2<>0 then v:=v shl 16 + pWord(@pSet[i])^; Result:=0; while true do begin; v:=v - v shr 1 and $55555555; v:=v and $33333333 + v shr 2 and $33333333; v:=(v + v shr 4) and $0F0F0F0F; // Result:=Result + v * $01010101 shr 24; Result:=Result + v; dec(i); if i<0 then break; v:=pSet[i]; end; Result:=(Result + Result shr 8) and $00FF00FF; Result:=(Result + Result shr 16) and $1FF; end;

← →
Sapersky (2008-07-03 18:49) [13]

Здесь тестировали:
http://infolab.stanford.edu/~manku/bitcount/bitcount.html
По результатам табличный метод оказался самым быстрым.

← →
Leonid Troyanovsky © (2008-07-03 19:02) [14]

> Sha © (03.07.08 17:41) [11]

> function ElementCount(pSet: pIntegerArray; Bound: integer):

Т.е., предполагается, что размер распределенной для сета памяти
кратен 4, а возможный хвостик заполнен 0?
Интересно, а как на самом деле?

Может для любого сета сразу выделяется 32 байта, чтобы не
заботиться о их перераспределении?

--
Regards, LVT.

← →
Sapersky (2008-07-03 20:53) [15]

В хелпе написано:

The number of bytes occupied by a particular set is equal to
(Max div 8) – (Min div 8) + 1
where Max and Min are the upper and lower bounds of the base type of the set.

Про выравнивание на 4 ничего нет, да и опытным путём его обнаружить не удалось.
Впрочем, у Sha, насколько я понял, "хвостик" таки обрабатывается:
i:=Bound shr 2;
v:=0;
if Bound and 1<>0 then v:=pByte(integer(pSet) + Bound - 1)^;
if Bound and 2<>0 then v:=v shl 16 + pWord(@pSet[i])^;
Оно задом наперёд считает, с хвостика начинает как раз :)

А в [10] всё-таки не очень удачный вариант, вызов функции много отъедает. Лучше так:

function GetElementCount3(pSet : PByteArray; ByteSize : Integer): Integer;
begin
Result := 0;
While (ByteSize >= 4) do begin
If PLongInt(pSet)^ <> 0 then
Inc(Result, BitCnt[pSet[0]] + BitCnt[pSet[1]] + BitCnt[pSet[2]] + BitCnt[pSet[3]]);
Inc(PByte(pSet), 4);
Dec(ByteSize, 4);
end;
If (ByteSize >= 2) then begin
Inc(Result, BitCnt[pSet[0]] + BitCnt[pSet[1]]);
Inc(PByte(pSet), 2);
Dec(ByteSize, 2);
end;
If (ByteSize = 1) then
Inc(Result, BitCnt[pSet[0]]);
end;

Sha © (03.07.08 18:14) [12]

MySetSize не всегда совпадает с SizeOf(MySet) (напр., MySetType = 1..80).

← →
Leonid Troyanovsky © (2008-07-03 22:21) [16]

> Sapersky (03.07.08 20:53) [15]

> Оно задом наперёд считает, с хвостика начинает как раз :)

Был невнимателен, sorry.

--
Regards, LVT.

← →
Германн © (2008-07-04 00:37) [17]

> Sapersky (03.07.08 20:53) [15]
>
> В хелпе написано:
>
> The number of bytes occupied by a particular set is equal
> to
> (Max div 8) – (Min div 8) + 1
> where Max and Min are the upper and lower bounds of the
> base type of the set.
>

И совершенно непонятно почему именно так.
Еще со времён ТР меня удивляло почему set of 0..7 занимает один байт, а set of 1..8 - два байта? Ведь в обоих случаях количество значений во множествах одинаково.

← →
oldman © (2008-07-04 01:02) [18]

> Как рационально узнать количество элементов в множестве?

Можно узнать, а как описано множество?

← →
Sha © (2008-07-04 09:27) [19]

> Sapersky (03.07.08 18:49) [13]
> Здесь тестировали:
> http://infolab.stanford.edu/~manku/bitcount/bitcount.html
> По результатам табличный метод оказался самым быстрым.

Там немножко не то тестировали. Они считали биты в целом числе.
Вариант [12] только часть подобных вычислений производит в цикле,
а окончательный подсчет откладывает на коней и выполняет один раз.

> Leonid Troyanovsky © (03.07.08 19:02) [14]
> Т.е., предполагается, что размер распределенной для сета памяти кратен 4, а возможный хвостик заполнен 0?
> Интересно, а как на самом деле?

Нет, не кратен..Хвостики (не более 7 битов) в начале и конце нулевые.
Больше того, ЕМНИП выравнивание на 4 не гарантируется.

> Sapersky (03.07.08 20:53) [15]
> В хелпе написано:
> The number of bytes occupied by a particular set is equal to
(Max div 8) – (Min div 8) + 1

Спасибо буду иметь ввиду. Исправлю при возможности. Понадеялся на беглый взгляд на асм-код Дельфи. Был не прав.

> oldman © (04.07.08 01:02) [18]
> Можно узнать, а как описано множество?

Хороший вопрос. Знание конкретики может облегчить задачу.

← →
Sha © (2008-07-04 11:18) [20]

После небольшой оптимизации приведенная ниже функция стала почти в 2 раза быстрее табличного варианта [8] (812 us против 1516 us).
Сравнивались времена 20000000 итераций на P4 для случайно сформированных множеств..
Множество включало элементы 0..255, вероятность вхождения элемента в множество 1/2.
function ElementCount(pSet: pIntegerArray; Bound: integer): integer; var v, i: integer; begin; Result:=0; i:=Bound shr 2; if Bound and 3<>0 then begin; v:=0; if Bound and 1<>0 then v:=pByte(integer(pSet) + Bound - 1)^; if Bound and 2<>0 then v:=v shl 16 + pWord(@pSet[i])^; v:=v - v shr 1 and $55555555; v:=v and $33333333 + v shr 2 and $33333333; Result:=(v + v shr 4) and $0F0F0F0F; end; while i>0 do begin; v:=pSet[i-1]; v:=v - v shr 1 and $55555555; v:=v and $33333333 + v shr 2 and $33333333; Result:=Result + (v + v shr 4) and $0F0F0F0F; dec(i); end; Result:=(Result + Result shr 8) and $00FF00FF; Result:=(Result + Result shr 16) and $1FF; end;

← →
Sha © (2008-07-04 11:26) [21]

ms а не us, конечно.

← →
Anatoly Podgoretsky © (2008-07-04 11:39) [22]

> Sha (04.07.2008 11:26:21) [21]

Не Микрософт точно?

← →
Sapersky (2008-07-04 15:42) [23]

функция стала почти в 2 раза быстрее табличного варианта [8] (812 us против 1516 us).

Я в [15] приводил оптимизированный вариант. Хотя под ваши тестовые данные выгоднее отключить проверку на 0:

function GetElementCount4(pSet : PByteArray; ByteSize : Integer): Integer;
Var i : Integer;
begin
Result := 0;
While (ByteSize >= 4) do begin
Inc(Result, BitCnt[pSet[0]] + BitCnt[pSet[1]] + BitCnt[pSet[2]] + BitCnt[pSet[3]]);
Inc(PByte(pSet), 4);
Dec(ByteSize, 4);
end;
If (ByteSize >= 2) then begin
Inc(Result, BitCnt[pSet[0]] + BitCnt[pSet[1]]);
Inc(PByte(pSet), 2);
Dec(ByteSize, 2);
end;
If (ByteSize = 1) then
Inc(Result, BitCnt[pSet[0]]);
end;

В 1.35 раза быстрее [20]. Даже с включённой проверкой - в 1.15 раза.

← →
Sha © (2008-07-04 16:16) [24]

Если в [20] полностью развернуть цикл, то она отстанет от [23] всего на 6%.
Правда длина функции получается 592 байта, что больше размеров таблицы.

← →
Sha © (2008-07-04 16:29) [25]

Можно еще попробовать оператор типа
Result:=Result + (v + v shr 4) and $0F0F0F0F;
выполнять один раз на 2 dword"а, но это ускорит работу только для полноразмерных [0..255] множеств.
Дома попробую.

← →
Sha © (2008-07-07 13:29) [26]

Для испытаний на полноразмерных множествах была использована оптимизированная процедура [23] (табличный вариант):
function ElementCountForSetOfChar4(pSet: PByteArray): Integer; var i: integer; begin; Result:=0; i:=32; repeat; Result:=Result + BitCnt[pSet[i-1]]; Result:=Result + BitCnt[pSet[i-2]]; Result:=Result + BitCnt[pSet[i-3]]; Result:=Result + BitCnt[pSet[i-4]]; Result:=Result + BitCnt[pSet[i-5]]; Result:=Result + BitCnt[pSet[i-6]]; Result:=Result + BitCnt[pSet[i-7]]; Result:=Result + BitCnt[pSet[i-8]]; i:=i-8; until i=0; end;

и оптимизированная процедура [20] (вычислительный вариант):
function ElementCountForSetOfChar2(pSet: pIntegerArray): integer; var s, u, v, i: integer; begin; Result:=0; i:=8; repeat; v:=pSet[i-1]; u:=v; v:=v and $AAAAAAAA; v:=v shr 1; u:=u-v; v:=u; u:=u and $CCCCCCCC; v:=v xor u; u:=u shr 2; s:=u+v; v:=pSet[i-2]; u:=v; v:=v and $AAAAAAAA; v:=v shr 1; u:=u-v; v:=u; u:=u and $CCCCCCCC; v:=v xor u; u:=u shr 2; u:=u+v; u:=u+s; v:=u; u:=u and $F0F0F0F0; v:=v xor u; u:=u shr 4; u:=u+v; Result:=Result + u; i:=i-2; until i=0; v:=Result; Result:=Result and $FF00FF00; v:=v xor Result; Result:=Result shr 8; Result:=Result + v; v:=Result; Result:=Result shr 16; Result:=Result + v; Result:=Result and $1FF; end;

Как и раньше, множество включало элементы 0..255, вероятность вхождения элемента в множество 1/2.
Вычислительный вариант проигрывает в скорости 4% табличному.

To be continued :)

← →
Sha © (2008-07-07 13:36) [27]

Оба варианта функций [26] обрабатывают по 8 байт множества за один проход цикла. Но в то время, как у табличного варианта потенциал дальнейшей оптимизации практически исчерпан, у вычислительного кое-что есть в запасе. Попробуем переложить его на ассемблер:
function ElementCountForSetOfChar3(pSet: pointer): integer; asm push esi push edi push ebx mov esi, eax mov edi, 4 xor eax, eax @loop: mov ebx, [esi] // v:=pSet[i-1]; mov ecx, ebx // u:=v; and ebx, $AAAAAAAA // v:=v and $AAAAAAAA; shr ebx, 1 // v:=v shr 1; mov edx, [esi+4] // v:=pSet[i-2]; (moved) sub ecx, ebx // u:=u-v; mov ebx, ecx // v:=u; and ecx, $CCCCCCCC // u:=u and $CCCCCCCC; xor ebx, ecx // v:=v xor u; shr ecx, 2 // u:=u shr 2; add esi, 8 // i:=i-2; (moved) add ebx, ecx // s:=u+v; mov ecx, edx // u:=v; and edx, $AAAAAAAA // v:=v and $AAAAAAAA; shr edx, 1 // v:=v shr 1; sub ecx, edx // u:=u-v; mov edx, ecx // v:=u; and ecx, $CCCCCCCC // u:=u and $CCCCCCCC; xor edx, ecx // v:=v xor u; shr ecx, 2 // u:=u shr 2; add ebx, edx // u:=u+v; add ebx, ecx // u:=u+s; mov edx, ebx // v:=u; and ebx, $F0F0F0F0 // u:=u and $F0F0F0F0; xor edx, ebx // v:=v xor u; shr ebx, 4 // u:=u shr 4; add eax, edx // u:=u+v; add eax, ebx // Result:=Result + u; sub edi, 1 jg @loop // until i=0; mov edx, eax // v:=Result; and eax, $FF00FF00 // Result:=Result and $FF00FF00; xor edx, eax // v:=v xor Result; shr eax, 8 // Result:=Result shr 8; add eax, edx // Result:=Result + v; mov edx, eax // v:=Result; shr eax, 16 // Result:=Result shr 16; add eax, edx // Result:=Result + v; and eax, $1FF // Result:=Result and $1FF; pop ebx pop edi pop esi end;

Теперь мы имеем выигрыш по сравнению с табличнм вариантом по скорости более 10% и по памяти примерно в 2.5 раза

← →
Leonid Troyanovsky © (2008-07-07 15:18) [28]

> Sha © (07.07.08 13:29) [26]

> Для испытаний на полноразмерных множествах была использована
> оптимизированная процедура [23] (табличный вариант):

> function ElementCountForSetOfChar4(pSet: PByteArray): Integer;
..
> repeat;

Ну, а чего бы цикл не развернуть до конца:

Result := pSet[0] + pSet[1] + .. + pSet[31];

--
Regards, LVT.

PS Может сбросишь куда весь тестовый проект,
скажем, мне на почту.

> Leonid Troyanovsky © (07.07.08 15:18) [28]

> Result := pSet[0] + pSet[1] + .. + pSet[31];

В смысле, Result := BitCnt[pSet[0]] +..
Sorry.

--
Regards, LVT.

> Leonid Troyanovsky © (07.07.08 15:18) [28]
> Ну, а чего бы цикл не развернуть до конца:
> Result := pSet[0] + pSet[1] + .. + pSet[31];

Скорее всего, заметно лучше не будет.

> Может сбросишь куда весь тестовый проект, скажем, мне на почту.

Отправил.

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

- а если табличный переложить на ассемблер с использованием LODS и XLAT?

> Sha © (07.07.08 15:37) [30]

> Скорее всего, заметно лучше не будет.

Да, практически незаметно.

Но, первое выводимое значение относится, как я понял,
к ElementCountForSetOfChar5 - параллельному методу,
а второе - к ElementCountForSetOfChar4 - табличному.

У меня выводится:
4000
3500
Где-то так. W2K3, Celeron 2 GHz, 256Mb RAM
Дома испытаю на XP, AMD.

--
Regards, LVT.

← →
Sapersky (2008-07-07 16:26) [33]

Sha © (07.07.08 13:36) [27]

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

> Leonid Troyanovsky © (07.07.08 16:20) [32]

> Да, практически незаметно.

В принципе, даже заметить можно.
3500 vs 3330.

--
Regards, LVT.

> han_malign © (07.07.08 16:15) [31]

Все в твох руках :)

Честно говоря, лень проверять, т.к. для ElementCountForSetOfChar4 компоятор генерирует практичеси идеальный код для раьоты с таблицей.
Переписывание на ассемблере позволит выкинуть из цикла одно сложение.
Разворачивание цикла может увеличить время исполнения.

> Leonid Troyanovsky © (07.07.08 16:28) [34]

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

> Leonid Troyanovsky © (07.07.08 16:28) [34]

На моем P4 развертывание цикла еще в 2раза (с 8 до 16) для табличного метода дает смешное улучшение 2797 -> 2781.
Если совсем избавиться от цикла, то компилятор перестает везде использовать movzx и результат резко ухудшается.

> Sha © (07.07.08 16:39) [36]

> Иначе будет интерференция с выводом в мемо.

Интерференцию не наблюл.
Докладываю результаты с дом.комп:
AMD Athlon XP 1500+ 1.29 GHz 512 MB RAM:

Параллельный метод - 6084
Табличный метод - 11756 (!)

Было б любопытно услышать соображения.

Кста, уважаемый Александр, не мог бы ты выложить код сюда -
объем его небольшой, а испытать его на разных конфигурациях
было б любопытно, IMHO.

--
Regards, LVT.

> Leonid Troyanovsky © (07.07.08 18:11) [38]

> Параллельный метод - 6084
> Табличный метод - 11756 (!)

После развертывания цикла:

пар - 6626
таб - 12050

Хорошо, мы можем посчитать GetProcessTimes, например.
Но, как объяснить разницу Celeron - AMD?

--
Regards, LVT.

← →
Sapersky (2008-07-07 22:05) [40]

На P3-700 табличный метод быстрее:
ElementCountForSetOfChar3 - 2564
ElementCountForSetOfChar4 - 2210
(ms, замерял QPC)

Количество элементов в множестве Найти похожие ветки