Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Количество элементов в множестве [D7, WinXP]

Страницы: < 1 2 3 >
JanMihail © (2008-07-02 15:08:00)
Как рационально узнать количество элементов в множестве?
Например:
[1..7] - 7
[1, 3..5] - 4

Leonid Troyanovsky (2008-07-07 15:18:00) [21]

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

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

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

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

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

--
Regards, LVT.

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

Sha (2008-07-07 13:36:00) [22]
Оба варианта функций [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 раза

Sha (2008-07-07 13:29:00) [23]
Для испытаний на полноразмерных множествах была использована оптимизированная процедура [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-04 16:29:00) [24]
Можно еще попробовать оператор типа
Result:=Result + (v + v shr 4) and $0F0F0F0F;
выполнять один раз на 2 dword'а, но это ускорит работу только для полноразмерных [0..255] множеств.
Дома попробую.

Sha (2008-07-04 16:16:00) [25]
Если в [20] полностью развернуть цикл, то она отстанет от [23] всего на 6%.
Правда длина функции получается 592 байта, что больше размеров таблицы.

Sapersky (2008-07-04 15:42:00) [26]
функция стала почти в 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 раза.

Anatoly Podgoretsky (2008-07-04 11:39:00) [27]
> Sha (04.07.2008 11:26:21) [21]

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

Sha (2008-07-04 11:26:00) [28]
ms а не us, конечно.

Sha (2008-07-04 11:18:00) [29]
После небольшой оптимизации приведенная ниже функция стала почти в 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 09:27:00) [30]
> 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]
> Можно узнать, а как описано множество?

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

oldman (2008-07-04 01:02:00) [31]

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

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

Германн (2008-07-04 00:37:00) [32]

> 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 - два байта? Ведь в обоих случаях количество значений во множествах одинаково.

Leonid Troyanovsky (2008-07-03 22:21:00) [33]

> Sapersky (03.07.08 20:53) [15]

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

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

--
Regards, LVT.

Sapersky (2008-07-03 20:53:00) [34]
В хелпе написано:

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 19:02:00) [35]

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

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

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

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

--
Regards, LVT.

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

Sha (2008-07-03 18:14:00) [37]
Так, наверно, еще быстрее:
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;

Sha (2008-07-03 17:41:00) [38]
Наверно, будет также быстро, как с использованием таблицы.
Не тестировалось.

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;

Leonid Troyanovsky (2008-07-03 16:24:00) [39]

> 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 14:29:00) [40]
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;

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

Страницы: < 1 2 3 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »