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

← →
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 © (2008-07-07 15:33) [29]

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

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

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

--
Regards, LVT.

← →
Sha © (2008-07-07 15:37) [30]

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

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

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

Отправил.

← →
han_malign © (2008-07-07 16:15) [31]

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

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

← →
Leonid Troyanovsky © (2008-07-07 16:20) [32]

> 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)

> Leonid Troyanovsky © (07.07.08 18:11) [38]
> Интерференцию не наблюл.

Ну, код написан на скорую руку в расчете на то, что интервал таймера больше суммы времен работы функций.
В этом случае он должен более-менее нормально работать.

> Докладываю результаты с дом.комп:
> AMD Athlon XP 1500+ 1.29 GHz 512 MB RAM:
> Параллельный метод - 6084
> Табличный метод - 11756 (!)

Если мне не изменяет память, у АМД оба юнита умеют сдвигать, у Интела - только один. Отсюда увеличение скорости параллельного метода.
Пока это только гипотеза, могу ошибаться.

> Sapersky (07.07.08 22:05) [40]
> На P3-700 табличный метод быстрее:
> ElementCountForSetOfChar3 - 2564
> ElementCountForSetOfChar4 - 2210

Опять же, ЕМНИП, оно так потому, что у P3 сдвиги реализованы хуже, чем у P4.

Тоже докладываю:
На моем 6850 также, как и на P4, параллельный метод быстрее на 11-12%.

Для тех, кому интересно проверить работу обоих методов на своей машине далее приводится код.
На форме мемо, кнопка и таймер (интервал 5-10сек (см. выше))
Я знаю, что использованный метод измерения производительности не оптимален,
если вы тоже так считаете, используйте тот, который вам нравится больше :)

unit BitCount; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, ExtCtrls; type TForm1 = class(TForm) Memo1: TMemo; Button1: TButton; Timer1: TTimer; procedure Button1Click(Sender: TObject); procedure Timer1Timer(Sender: TObject); private { Private declarations } public { Public declarations } end; var Form1: TForm1; implementation {$R *.dfm} 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); function ElementCount1(pSet: PByte; ByteSize: integer): integer; var n: integer; begin; Result:=0; for n:=0 to ByteSize-1 do begin; Inc(Result, BitCnt[pSet^]); Inc(pSet); end; end; function ElementCount4(pSet : PByteArray; ByteSize : Integer): 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; function ElementCount2(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; 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; function ElementCountForSetOfChar44(pSet: PByteArray): Integer; var i: integer; begin; Result:=0; i:=1; repeat; Result:=Result + BitCnt[pSet[i]]; Result:=Result + BitCnt[pSet[i+4]]; Result:=Result + BitCnt[pSet[i+8]]; Result:=Result + BitCnt[pSet[i+12]]; Result:=Result + BitCnt[pSet[i+16]]; Result:=Result + BitCnt[pSet[i+20]]; Result:=Result + BitCnt[pSet[i+24]]; Result:=Result + BitCnt[pSet[i+28]]; Result:=Result + BitCnt[pSet[i+2]]; Result:=Result + BitCnt[pSet[i+6]]; Result:=Result + BitCnt[pSet[i+10]]; Result:=Result + BitCnt[pSet[i+14]]; Result:=Result + BitCnt[pSet[i+18]]; Result:=Result + BitCnt[pSet[i+22]]; Result:=Result + BitCnt[pSet[i+26]]; Result:=Result + BitCnt[pSet[i+30]]; i:=i-1; until i<0; end;

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; function ElementCountForSetOfChar3(pSet: pointer): integer; asm push esi mov esi, eax push edi push ebx 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; function ElementCountForSetOfChar5(pSet: pointer): integer; asm push esi push edi push ebx xor esi, esi mov edi, 4 @loop: mov ebx, [eax] // 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, [eax+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 eax, 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 esi, edx // u:=u+v; add esi, ebx // Result:=Result + u; sub edi, 1 jg @loop // until i=0; mov eax, esi // v:=Result; and esi, $FF00FF00 // Result:=Result and $FF00FF00; xor eax, esi // v:=v xor Result; shr esi, 8 // Result:=Result shr 8; pop ebx // (moved) add esi, eax // Result:=Result + v; mov eax, esi // v:=Result; shr esi, 16 // Result:=Result shr 16; pop edi // (moved) add eax, esi // Result:=Result + v; and eax, $1FF // Result:=Result and $1FF; pop esi end; type MyBaseType = 0..255; MySetType = Set of MyBaseType; var MySet: MySetType; TimerCount: integer= 0; procedure TForm1.Button1Click(Sender: TObject); begin; Randomize; TimerCount:=10; Memo1.Lines.Clear; end; procedure TForm1.Timer1Timer(Sender: TObject); var t1, t2, t3: cardinal; i, c1, c2: integer; e: MyBaseType; begin; if TimerCount>0 then begin; MySet:=[]; for e:=Low(MyBaseType) to High(MyBaseType) do begin; RandSeed:=RandSeed * $08088405 + 1; if RandSeed<0 then include(MySet, e); end; dec(TimerCount); t1:=GetTickCount; for i:=1 to 100000000 do c1:=ElementCountForSetOfChar4(@MySet); t2:=GetTickCount; for i:=1 to 100000000 do c2:=ElementCountForSetOfChar5(@MySet); t3:=GetTickCount; Memo1.Lines.Add(IntToStr(t2-t1)); Memo1.Lines.Add(IntToStr(t3-t2)); if c1<>c2 then Memo1.Lines.Add("ERROR -----------------"); Memo1.Lines.Add(""); end; end; end.

> Sha © (08.07.08 01:15) [41]

> На моем 6850 также, как и на P4, параллельный метод быстрее
> на 11-12%.

На двухпроцессорной (P4) машине:
парал. ~2294, табл. ~2492, т.е. на 8% быстрее табличного.

--
Regards, LVT.

> Sha © (08.07.08 01:15) [41]
> Если мне не изменяет память, у АМД оба юнита умеют сдвигать

Тут ошибочкв вкралась. У AMD K6/K7 сдвиги реализует толькл один IEU, но с малой латентностью. У Атлона уже три IEU, сколько из них умеют сдвигать, не знаю.

Полезные ссылки:
http://www.agner.org/optimize/optimizing_assembly.pdf
http://www.agner.org/optimize/microarchitecture.pdf

← →
JanMihail (2008-07-08 21:20) [46]

Спасибо!)

> Sapersky (07.07.08 16:26) [33]
> Ну и 16-битная таблица ещё немного быстрее, впрочем, по использованию памяти это уже ни в какие ворота.

Если нельзя, но очень хочется, то можно :)
Как и следовало ожидать, 16-битная таблица повышает скорость работы табличного метода ровно в 2 раза.
Проверял вот на этом коде (здесь и далее процессор 6850).
function ElementCountForSetOfChar8(pSet: PWordArray): Integer; var i: integer; begin; Result:=0; i:=16; repeat; Result:=Result + BitCnt2[pSet[i-1]]; Result:=Result + BitCnt2[pSet[i-2]]; Result:=Result + BitCnt2[pSet[i-3]]; Result:=Result + BitCnt2[pSet[i-4]]; Result:=Result + BitCnt2[pSet[i-5]]; Result:=Result + BitCnt2[pSet[i-6]]; Result:=Result + BitCnt2[pSet[i-7]]; Result:=Result + BitCnt2[pSet[i-8]]; i:=i-8; until i=0; end;

Вообще-то, узким местом табличного метода является вовсе не задержка адреса, а именно операции чтения из памяти.
Если, например читать не по одному байту, а по два, то несмотря на дополнительные операции табличный метод сравнивается с параллельным:
function ElementCountForSetOfChar9(pSet: PWordArray): Integer; var i, w: integer; begin; i:=16; Result:=0; repeat; w:=pSet[i-1]; Result:=Result + BitCnt[w and 255]; Result:=Result + BitCnt[w shr 8]; w:=pSet[i-2]; Result:=Result + BitCnt[w and 255]; Result:=Result + BitCnt[w shr 8]; w:=pSet[i-3]; Result:=Result + BitCnt[w and 255]; Result:=Result + BitCnt[w shr 8]; w:=pSet[i-4]; Result:=Result + BitCnt[w and 255]; Result:=Result + BitCnt[w shr 8]; i:=i-4; until i=0; end;
Попытки читать по 4 байта или еще немного развернуть цикл к дальнейшему прогрессу не приводят.

Только полное исключение цикла в функциях ElementCountForSetOfChar5 и ElementCountForSetOfChar9 позволяет получить время работы обоих методов на 20% лучше ElementCountForSetOfChar4.

Любопытно, что даже в случае исключения цикла в ElementCountForSetOfChar9 параллельный метод занимает меньше памяти, чем любая версия табличного метода.

Ну, а лидером в заезде становится работающая в 2.36 раза быстрее ElementCountForSetOfChar4 и использующая с 16-битную таблицу
function ElementCountForSetOfChar88(pSet: PIntegerArray): Integer; var i: integer; begin; i:=pSet[0]; Result:=BitCnt2[i and $FFFF]; Result:=Result + BitCnt2[i shr 16]; i:=pSet[1]; Result:=Result + BitCnt2[i and $FFFF]; Result:=Result + BitCnt2[i shr 16]; i:=pSet[2]; Result:=Result + BitCnt2[i and $FFFF]; Result:=Result + BitCnt2[i shr 16]; i:=pSet[3]; Result:=Result + BitCnt2[i and $FFFF]; Result:=Result + BitCnt2[i shr 16]; i:=pSet[4]; Result:=Result + BitCnt2[i and $FFFF]; Result:=Result + BitCnt2[i shr 16]; i:=pSet[5]; Result:=Result + BitCnt2[i and $FFFF]; Result:=Result + BitCnt2[i shr 16]; i:=pSet[6]; Result:=Result + BitCnt2[i and $FFFF]; Result:=Result + BitCnt2[i shr 16]; i:=pSet[7]; Result:=Result + BitCnt2[i and $FFFF]; Result:=Result + BitCnt2[i shr 16]; end;

Очепатка:
Любопытно, что даже в случае исключения цикла в ElementCountForSetOfChar5 параллельный метод занимает меньше памяти, чем любая версия табличного метода.
В частности, поэтому (на 6850) его имеет смысл использовать вместо табличного с 8-битной таблицей, т.к. их скорости равны.

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