The size of a set

[Mogens Lundholm]

I am new to the forum. Added comments, but cannot see them. So now I write here, so you can see I am not impolite.

About jamie's question: I need enumeration (I would like to have), e.g. [3000..4000] And cannot find operator for that. Actually also an "operator.." could be needed. But Anyway, with TBits I make a set-implementation and it runs this test-program:

Code: Pascal  [Select][+][-]

1. // Main variable
2. var
3.     i,j: integer;
4.     s1: TVarSet;  // First set
5.     s2: TVarSet;  // Second set
6.     sx: TVarSet;  // result set
7.  
8.   // Main
9.   begin
10.   writeln('VarSet V0.900');
11.   s1:=[3,5,7];
12.   s2:=[13,15,17];
13.   sx:=s1+s2;
14.   // Different ways of adding elements
15.   sx:=sx+10017;
16.   include(sx,10000010);
17.   include(s1,10000017);
18.   include(s2,100000117);
19.  
20.   // Union set run 100 times
21.   for j:=1 to 100 do
22.     sx:=s1+s2;
23.  
24.   // Measure execution time for "For i in set"
25.   for j:=1 to 100 do
26.     begin
27.     for i in sx do begin end;;
28.     end;
29.  
30.   writeln;
31.   writeln('Expected output: ','3 5 7 13 15 17 10000017 100000117');;
32.   write('Actual output:   ');
33.   for i in sx do begin write(i,' ') end;
34.   writeln(chr(7));
35.   readln;
36.   end.
37.  
38.  
39.  

This seems to do the jobb. It uses TBits and runs surprisingly fast. Except for one thing: I need to free memory at assign. I write "operator:=(r: TVarSet; s: TVarSet), " But the compiler writes:
"Error: Impossible to overload assignment for equal types"
But that is what I need to free class at assignment.

My original text:
___________________________________

From the beginning of Pascal the size of a set is limited to 256 elements. The size has not been increased in 50 years.

I need bigger sets.
I was proposed to change the compiler but - I don't know where to begin. In the Facebook group (Free Pascal and Lazarus Foundation) I was told that the file '..../rtl/inc/compproc.inc' has a definition of length (Part of PFC).
The size may be "fpc_small_set" or "fpc_normal_set".

What would the effort be to increase this limit, remove the limit or make fpc_huge_set?

Alternative: Allow "[]" as an operator. Then all operators could be programmed.

To Set-haters: It does not harm you or offend you that I have a bigger set. You can just let let be using sets.

[jamie]

Why don't you simply write a container class with operator overloads to give you that bloated field?

[winni]

Hi!

You are right - sets are the misstreated children in Pascal.

Simple but not so nice workaround:

Code: Pascal  [Select][+][-]

1. Type
2. TMySet = set of byte;
3. TBigSet = array of  TMySet;
4.  

The index of the array gives

Offset := Index * 256;

Winni

[jamie]

If you need larger sets then I think you are abusing them already..

 there is a class like Tbits If I remember that allows you to play with bit fields up to some unlimited size.

[marcov]

Set types are mostly built in, and would require compiler work before changing the helpers for non inlinable functionality in the  RTL.

[PascalDragon]

From the beginning of Pascal the size of a set is limited to 256 elements. The size has not been increased in 50 years.

I need bigger sets.
I was proposed to change the compiler but - I don't know where to begin. In the Facebook group (Free Pascal and Lazarus Foundation) I was told that the file '..../rtl/inc/compproc.inc' has a definition of length (Part of PFC).
The size may be "fpc_small_set" or "fpc_normal_set".

What would the effort be to increase this limit, remove the limit or make fpc_huge_set?

Alternative: Allow "[]" as an operator. Then all operators could be programmed.

The larger sets get, the larger the waste of memory is. A set of 256 elements already takes 32 Byte or 8 32-bit values. Especially if you're working with sparse sets that is a huge waste of space. Thus it would be better to use a sparse set mechanism. The functionality provided by FPC 3.2 (operator overloads, generic and the new dynamic array constructors) allow for such implementation. There is no need to extend the compiler for this and it can be done in a more efficient way.

[jamie]

maybe I got off on the foot here, are we talking about range in sets ?

Like for example

 if Something in [3000..4000] Then...

 then yes I would agree that is lame but it works with variables..

 As with constants in that particular expression it shouldn't care about the range size because it should be just a two value compare, not a whole streak of memory to scan through...

actually a Range Function can be made to do the same …

[PascalDragon]

maybe I got off on the foot here, are we talking about range in sets ?

No, we're talking about set types:

Code: Pascal  [Select][+][-]

1. type
2.   TMyEnum = (One, Two, Three);
3.   TMySet = set of TMyEnum;

The size of a set type is between 1 Byte (with directive $PackSet 1) and 32 (if the enum as the maximum of 256 elements allowed for sets). The more elements the enumeration type of the set has, the bigger the set. And the bigger the potential waste of memory when you're only dealing with a sparsly populated set.

[Mogens Lundholm]

Hi!

You are right - sets are the misstreated children in Pascal.

Simple but not so nice workaround:

Code: Pascal  [Select][+][-]

1. Type
2. TMySet = set of byte;
3. TBigSet = array of  TMySet;
4.  

The index of the array gives

Offset := Index * 256;

This is my solution. All operators work except "[]". I use [] for initialization and for computations like a_set:=a_set+. 

Winni

[Mogens Lundholm]

Why don't you simply write a container class with operator overloads to give you that bloated field?

That is what I did. But have to made a lot of changed because "[]" cannot be programmed as operator.

[Mogens Lundholm]

Why don't you simply write a container class with operator overloads to give you that bloated field?

That is what I did. But have to made a lot of changed because "[]" cannot be programmed as operator.

Also performance would be much better if built-in

[marcov]

The larger sets get, the larger the waste of memory is. A set of 256 elements already takes 32 Byte or 8 32-bit values. Especially if you're working with sparse sets that is a huge waste of space. Thus it would be better to use a sparse set mechanism. The functionality provided by FPC 3.2 (operator overloads, generic and the new dynamic array constructors) allow for such implementation. There is no need to extend the compiler for this and it can be done in a more efficient way.

(I don't agree, the simple reason is that sets then become pointless in general, since it doesn't scale. So you can't design set use into e.g. a state machines, because when the number of states gets to 256, you have to rewrite. IMHO an expansion would be a good thing, but maybe the compiler should warn if sets above a certain size would be passed by value)

Sparse sets are an memory efficiency measure for some problem, but  less universal because insertion often becomes O(n) and lookup O(log n) instead of just O(1). And of course needs special care while streaming (since it is a dynamic field inside a record)

[Mogens Lundholm]

From the beginning of Pascal the size of a set is limited to 256 elements. The size has not been increased in 50 years.

I need bigger sets.
I was proposed to change the compiler but - I don't know where to begin. In the Facebook group (Free Pascal and Lazarus Foundation) I was told that the file '..../rtl/inc/compproc.inc' has a definition of length (Part of PFC).
The size may be "fpc_small_set" or "fpc_normal_set".

What would the effort be to increase this limit, remove the limit or make fpc_huge_set?

Alternative: Allow "[]" as an operator. Then all operators could be programmed.

The larger sets get, the larger the waste of memory is. A set of 256 elements already takes 32 Byte or 8 32-bit values. Especially if you're working with sparse sets that is a huge waste of space. Thus it would be better to use a sparse set mechanism. The functionality provided by FPC 3.2 (operator overloads, generic and the new dynamic array constructors) allow for such implementation. There is no need to extend the compiler for this and it can be done in a more efficient way.
I just said: I need it! If you don't need it. Then don't care. It does not harm you if I can I have bigger sets.

[jamie]

Why don't you simply write a container class with operator overloads to give you that bloated field?

That is what I did. But have to made a lot of changed because "[]" cannot be programmed as operator.

 Have you looked at the "TBITS" class yet ?

 That allows you to address bits up to any size until you run out of memory and it has a [] bracket default for array indexing of bits..

[marcov]

TBits doesn't work with enums. Maybe we need some generic variant for that.

But that still would be a reference type.