Cardinality of a set
Jacques Melancon
is there any Delphi BUILT-IN function doing the job?
I looked at the Delphi Help and at developers.href.com
site and found nothing about such a function.
Thanks in advance
Jacques
Rudy Velthuis
>Calculating the cardinality of a set is an easy task, but
>is there any Delphi BUILT-IN function doing the job?
What do you mean with the cardinality of a set?
--
Rudy Velthuis
Glynn Owen
Phillipe has a BASM solution to this problem that he's posted a couple
of times. Maybe he'll do it again.
Glynn
Eddie Shipman
Glynn Owen <gl...@gtstrans.com> wrote in message
news:3804FEC6...@gtstrans.com...
Rene Tschaggelar
Rene
--
Ing.Buero R.Tschaggelar - http://www.ibrtses.com
Jacques Melancon wrote:
>
> Calculating the cardinality of a set is an easy task, but
> is there any Delphi BUILT-IN function doing the job?
>
Jacques Melancon
BUILT-IN function doing the job for me.
Jacques
Philippe Ranger
What do you mean with the cardinality of a set?
>>
Guess why my bit counter is named Card.
PhR
Philippe Ranger
I know I can count. I want to know if there is a
BUILT-IN function doing the job for me.
>>
There is no built-in function and, like you, I think there should be, just
as there should be sets beyond 256 elements. Many years ago, I wrote a
universal bit counter, which follows.
PhR
---------------
FUNCTION card (var tar; size: integer): integer; assembler; //tested
(*Reg usage: eax=result
ebx=work reg
ecx=nibble counter
edx=@last byte in tar, +1
esi=@next elm in tar
edi=@last dw in tar, +1
ebp=0 (to shorten opcodes)*)
(*NB the main engine is countNibble. The setup gets tar into esi and
sets two limits for it: full dw's, and bytes (i.e. full length).
CountNibble is fed from dw's until the first limit is reached, then from
the remaining bytes*)
ASM
(*setup*)
push ebx
push esi
push edi
push ebp
mov esi, eax //set esi
mov ebx, edx
and ebx, 3
add edx, eax //set edx
mov edi, edx
sub edi, ebx //set edi
xor eax, eax //set eax
xor ebp, ebp //set ebp
@doDws:
cmp esi, edi
jnb @doBytes
mov ebx, [esi]
add esi, 4
mov ecx, 8 //eight nibbles per dw
@countNibble: //repeats save three loop's
shr ebx, 1 //adding four more would only save one loop
adc eax, ebp
shr ebx, 1
adc eax, ebp
shr ebx, 1
adc eax, ebp
shr ebx, 1
adc eax, ebp
loop @countNibble
jmp @doDws
@doBytes:
cmp esi, edx
jz @exit
mov bl, [esi]
inc esi
mov ecx, 2 //two nibbles
jmp @countNibble
@exit:
pop ebp
pop ÿedi
pop esi
pop ebx
END;
---------------------------
Rudy Velthuis
>Wouldn't that be High(set)???
That would be the maximum number of items a set can have. The
cardinality would be the number of items actually in there.
The answer is no, there are no built-in functions for this. If
Philippe posted code, try to find it on
http://www.deja.com/home_ps.shtml
--
Rudy Velthuis
Robert Lee
>
> <<Jacques:
> I know I can count. I want to know if there is a
> BUILT-IN function doing the job for me.
> >>
>
> There is no built-in function and, like you, I think there should be, just
> as there should be sets beyond 256 elements. Many years ago, I wrote a
> universal bit counter, which follows.
Weren't we just here?
Your "many years ago" is in full flower. That 'loop' instruction has
got to go. Besides, it would seem that wrapping around the best of the
"bitsInByte" solutions would be both faster and less cumbersome.
--
Bob Lee
High Performance Delphi - http://www.econos.com/optimize/
Updated August 2
Jacques Melancon
As you say I think it would be usefull if we could have such a function.
Now, a question about your function. If I declare something like:
Type
TDigits = set of 0..9;
Var
Digits : TDigits;
Cardin: integer;
I would call your function like this:
Cardin := Card( Digits, sizeof(TDigits) );
or
Cardin := Card( Digits, 2 );
Which means that size is the size in bytes (not in bits) occupied by the
variable.
Jacques
Philippe Ranger <.> wrote in message news:7u3nf6$jd...@forums.borland.com...
> There is no built-in function and, like you, I think there should be, just
> as there should be sets beyond 256 elements. Many years ago, I wrote a
> universal bit counter, which follows.
> ---------------
> FUNCTION card (var tar; size: integer): integer; assembler; file://tested
Philippe Ranger
Besides, it would seem that wrapping around the best of the
"bitsInByte" solutions would be both faster and less cumbersome.
>>
Perhaps, but that involves one call per byte. Feel free to redo Card if you
want.
PhR
Philippe Ranger
I would call your function like this:
Cardin := Card( Digits, sizeof(TDigits) );
or
Cardin := Card( Digits, 2 );
Which means that size is the size in bytes (not in bits) occupied by the
variable.
>>
The first call format is right, never the second! And yes, the size is in
bytes. There are no part-byte asddresses on the x86 architecture!
PhR
Jacques Melancon
Philippe Ranger <.> wrote in message news:7u55ru$17...@forums.borland.com...
Philippe
1. I know that there is no bit addressing
2. Both calls are identical in my example ( sizeof(TDigits) IS EQUAL TO 2 ).
You need at least 2 bytes to store 10 "boolean" values.
3. My point was: Does the function need the number of bits to check (10)
within the bytes received (2) or the number of bytes (2) used to stored
the set?
4. I hope this will be a built-in function in future version of Delphi.
5. Thanks for the solution
Jacques
John Herbster
Philippe Ranger
1. I know that there is no bit addressing
2. Both calls are identical in my example ( sizeof(TDigits) IS EQUAL TO 2 ).
You need at least 2 bytes to store 10 "boolean" values.
>>
Sizeof() is not a function, Jacques, it's a compiler macro.
("Pseudo-function".) When you put it in, the executable simply has 2, or
whatever the right figure was. And that's the point -- don't trust your
calculations, trust sizeof(), the compiler knows for sure.
<<
3. My point was: Does the function need the number of bits to check (10)
within the bytes received (2) or the number of bytes (2) used to stored
the set?
>>
Same answer. The Card function would be of little use if you had to make
sure, first, that you knew the last bit used for the set type. Sets can
begin on any value, not just 0; it's absurd to ask you to figure what
happens then. So, the function wants the byte count, and it wants it from
sizeof().
PhR
Philippe Ranger
Shouldn't that be like ord(high(set)) + 1 ?
>>
Not at all sure. What happens with a set of 14..28?
PhR
Robert Lee
Philippe Ranger wrote:
>
> <<Bob:
> Besides, it would seem that wrapping around the best of the
> "bitsInByte" solutions would be both faster and less cumbersome.
> >>
>
> Perhaps, but that involves one call per byte.
By wrap I meant put the code inside a loop. This is between 1.7 and 3x
faster depending on the size of the set on a PII, and it uses your
BitsInByte Nibble algorithm crushed into one pascal expression.
function card1(var tar; size: integer): integer;
const
nibbleTable:array[0..15] of integer=( 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2,
3, 2, 3, 3, 4);
var
Data:PByteArray;
i,b:integer;
begin
result:=0;
Data:=@TByteArray(tar)[size];
i:=-size;
while i<0 do
begin
b:=Data[i];
inc(result,NibbleTable[b and $F]+NibbleTable[(b shr 4) and $F]);
inc(i);
end;
end;
John Herbster
"ord(high(set))+1". On a related topic, that I have never seen
discussed here, is the problem of using other people's definition of
enumerated types in const statements like ...
const FieldTypeNames: array [TFieldType] of string[4] = ('Unk', 'A',
... ,'Guid');
I have twice created a maintenance problem with the above kind of
code, which occured when Borland extended the types. That problem
could have been avoided by "subtyping" the TFieldType like in the
following ...
type TFieldTypeX = (ftUnknown .. ftGuid);
const FieldTypeNames: array [TFieldTypeX] of string[3] = ('Unk', 'A',
... ,'Guid');
But what is a good way to minimize the effect of adding a member in
the middle of the range?
Thanks for pointing out my error, John H
Philippe Ranger
By wrap I meant put the code inside a loop. This is between 1.7 and 3x
faster depending on the size of the set on a PII, and it uses your
BitsInByte Nibble algorithm crushed into one pascal expression.
>>
This is getting embarrassing!
To get your code to compile with typed @, I had to replace your Data
assignment with --
Data:=PbyteArray(@TByteArray(tar)[size]);
(I've been bitten recently with just kind of problem, untyped @ on an
indexed array.)
It looks like you worked on this. Can I ask --
-- Why not a For loop?
-- Why scan down the array?
-- Why use the var b? Is using this buffercheaper than doing a second
indexed access to the same spot?
In other words, what if this was --
----------
function card2(var tar; size: integer): integer;
const (*nibble table*)
Ca: array[0..15] of integer=( 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2,
3, 2, 3, 3, 4);
var
ab: TbyteArray absolute tar;
j: integer;
begin
result:=0;
for j := 0 to size - 1 do begin
inc(result, Ca[ab[j] and $F] + Ca[ab[j] shr 4]);
end;
end;
--------------------
PhR
Philippe Ranger
But what is a good way to minimize the effect of adding a member in
the middle of the range?
>>
Far as I know, none. Whoever does this on a commercial library is a criminal
(unless the type maps an OS-defined thing, which changed).
PhR
Robert Lee
>
> It looks like you worked on this. Can I ask --
Actually, I didn't 'work' on it. I just applied my standard tune-ups,
then looked at what I got (CPU window). It looked good so I quit.
>
> -- Why not a For loop?
For loops usually have more setup overhead and usually increment a
counter and one pointer for each array in the loop. The while loop has
less overhead (although the fooling around at the beginning could be
considered part of its overhead) and only increments the index.
However, it also feels compelled to test the counter against zero even
though the inc would have set the flags needed.
>
> -- Why scan down the array?
I don't. I scan up referened from the back of the array. Thus i goes
from -size to -1. This allows a termination at at constant (zero)
rather than at a variable. Net effect: reduce number of variables in
play by one.
>
> -- Why use the var b? Is using this buffercheaper than doing a second
> indexed access to the same spot?
This was a guess. The idea was to prevent reloading Data[i]. Sometimes
the compiler handles this on its own, sometimes not (it probably would
have here) Anyway, b is free as it will only be a register variable
(optimization on) and you have to load Data[i] sometime.
> In other words, what if this was --
In this particular instance this would probably have been quite
similar. Lets Check.... Yup almost exactly the same. However, there
are a couple of things in your version that don't generalize well. One
is the for loop as I mentioned. Another is the use of 'absolute'.
Using absolute as a sort of permanent typecast often forces register
variables onto the stack. In this case, the data is already memory
based so it works out.
My approach to this sort of thing is to start with the probabilities on
my side. That is I code in the style that I know
tends to result in the most efficient machine code. This way I don't
have to go back and completely re-invent the wheel with each
optimization.
BTW: I really wish they would 'fix' the for loop because I rather
dislike using while to do a for loops job.
Philippe Ranger
I don't. I scan up referened from the back of the array. Thus i goes
from -size to -1.
>>
Got it!
<<
Anyway, b is free as it will only be a register variable
(optimization on) and you have to load Data[i] sometime.
>>
Got that too. Using b means spelling out what the compiler codes anyhow, and
makes the OP code easier to read.
<<
Another is the use of 'absolute'.
Using absolute as a sort of permanent typecast often forces register
variables onto the stack. In this case, the data is already memory
based so it works out.
>>
From way back, I see absolute as the normal complement for untyped params.
Can't say your pointer and assignment look like a convincing improvement.
<<
BTW: I really wish they would 'fix' the for loop because I rather
dislike using while to do a for loops job.
>>
Could you go into detail? I don't quite see what the For does worse than
would a While in the same place. The For looks under-optimized because it
sticks to ecx when it already uses a loop var, the While because it doesn't
fully simplify its tests. But you're right that the ecx thing is a somewhat
embarrassing holdover.
PhR
Robert Lee
> <<
> Another is the use of 'absolute'.
> Using absolute as a sort of permanent typecast often forces register
> variables onto the stack. In this case, the data is already memory
> based so it works out.
> >>
>
> From way back, I see absolute as the normal complement for untyped params.
> Can't say your pointer and assignment look like a convincing improvement.
Absolute implies memory address. However, many params don't have any
memory associated with them as they are values. By using the 'absolute'
approach to typecasting them you force them on to the stack and out of a
register, making them slower in the process. Upon reflection though,
'var' params are always associated with memory so using absolute on them
generalizes well. I'll have to make a note of that as I like the look
of 'absolute' over typecasts.
> <<
> BTW: I really wish they would 'fix' the for loop because I rather
> dislike using while to do a for loops job.
> >>
>
> Could you go into detail?
The compiling and optimization of 'for' loops is probably the most
complex operation the compiler does. (case statements would run a close
second, IMO) The basic approach is to convert the loop variable (i) into
a counter that typically heads towards zero, and to convert any arrays
to typed pointer variables that are incremented along their respective
arrays. This avoids the need to multiply, which pre-Pentium II was
quite an expensive operation. However, it overlooks the fact the arrays
with element sizes of 1, 2, 4 and 8 are special cases that are directly
supported by x86 CPU's. Consequently, it is not the best generalized
approach to these types of loops. Now since classes are actually
pointers it is easy to see that the preponderance of arrays fall into
this catagory, and so I believe that the compiler should handle them
differently. This was my "wish".
So much for the generalities. As I said the for loop optimization is
complex. In some cases it does a pretty good job in spite of itself on
these types of arrays. In this instance, since the for loop conditional
is smart enough to avoid the 'test' for zero the extra increment for the
array doesn't hurt. If however, you were to reference two or three
different arrays then the problem would start to look a bit more
obvious. Additionally, it tends to eat up registers with all the arrays
and so it is often forced to reload them in more complicated loops.
I don't quite see what the For does worse than
> would a While in the same place. The For looks under-optimized because it
> sticks to ecx when it already uses a loop var,
This is the counter + array iterator that I mentioned. Using ecx is
just coincidental.
--
Bob Lee
High Performance Delphi - http://www.econos.com/optimize/
Updated August 2
Philippe Ranger
From way back, I see absolute as the normal complement for untyped params.
Can't say your pointer and assignment look like a convincing improvement.
>>>
<<Bob:
Absolute implies memory address. However, many params don't have any
memory associated with them as they are values.
>>
Bob, perhaps you want to warn people away from using absolute
indiscriminately, but I said "untyped parameters", and these cannot be
passed by value, of course.
<<
Consequently, it is not the best generalized
approach to these types of loops. Now since classes are actually
pointers it is easy to see that the preponderance of arrays fall into
this catagory, and so I believe that the compiler should handle them
differently. This was my "wish".
>>
I suppose the array access by pointer incrementation is valid for While
loops too, so you're not saying the For is less optimized than the While,
but that in the former case there's an extra optimization available for the
most common use, and it is not put in.
<<
This is the counter + array iterator that I mentioned. Using ecx is
just coincidental.
>>
My view on it is that it is historical. TP was happy to use the cx Intel had
provided for this (with the loop operator), and now that the optimizer is
smarter by a degree of magnitude, somehow this former, trivial, optimization
hasn't been removed to free a reg. Have I got this right?
PhR
Robert Lee
>
> <<
> Consequently, it is not the best generalized
> approach to these types of loops. Now since classes are actually
> pointers it is easy to see that the preponderance of arrays fall into
> this catagory, and so I believe that the compiler should handle them
> differently. This was my "wish".
> >>
>
> I suppose the array access by pointer incrementation is valid for While
> loops too, so you're not saying the For is less optimized than the While,
> but that in the former case there's an extra optimization available for the
> most common use, and it is not put in.
The while loop really isn't optimized at all in the way for loops are.
A while loop is handled more like a bent if-then statement.
Consequently, you can manually optimize access within the loop by proper
use of pointers, indicies etc. But you have to do it all yourself. I
would prefer if the already complex for loop optimizations were made a
bit more complex and treated arrays of simple sized elements
differently.
> My view on it is that it is historical. TP was happy to use the cx Intel had
> provided for this (with the loop operator), and now that the optimizer is
> smarter by a degree of magnitude, somehow this former, trivial, optimization
> hasn't been removed to free a reg. Have I got this right?
Nope, like I said the ecx usage was coincidental. Toss a routine call
into the loop and the counter will be shifted to a protected register
like esi.