Recent

Author Topic: Large or huge sets  (Read 2634 times)

PascalDragon

  • Hero Member
  • *****
  • Posts: 1751
  • Compiler Developer
Re: Large or huge sets
« Reply #15 on: September 11, 2019, 09:41:36 am »
Large or huge sets are often requested. Just today I needed one. Wrote it in ten minutes, but maybe useful?
If the critics are not too harsh, I will add it to to the wiki.
Note it can be written *way* more efficient.
Small remark: due to the use of global operators they can't be used inside generics (at least as of now) while normal sets have no problem with that.

Thaddy

  • Hero Member
  • *****
  • Posts: 10206
Re: Large or huge sets
« Reply #16 on: September 11, 2019, 09:50:31 am »
Large or huge sets are often requested. Just today I needed one. Wrote it in ten minutes, but maybe useful?
If the critics are not too harsh, I will add it to to the wiki.
Note it can be written *way* more efficient.
Small remark: due to the use of global operators they can't be used inside generics (at least as of now) while normal sets have no problem with that.
I know. It is not perfect in any way, but it works.... :-X and the code is reasonably clean and not bloat as was suggested.
I was able to use this in re-examining my translation of the Delphi Gold parser system.
« Last Edit: September 11, 2019, 09:54:54 am by Thaddy »
I am more like donkey than shrek

avk

  • Sr. Member
  • ****
  • Posts: 269
    • my self-education project
Re: Large or huge sets
« Reply #17 on: September 13, 2019, 08:48:31 pm »
@Thaddy, but why exactly TSortedHashSet?

Thaddy

  • Hero Member
  • *****
  • Posts: 10206
Re: Large or huge sets
« Reply #18 on: September 13, 2019, 09:35:35 pm »
Because it has a distinctive "set" of advantages  :D
It is reasonably fast, is sorted (essential) and does not accept duplicates. It behaves like normal, basic, Pascal sets. (But I wrote it is in no way optimal, it is also not bloat as suggested - that one is fired if he was working for me)

The approach was to have large sets with as few lines of code possible and it should match normal set behavior. Job done. And really in 10 minutes. I like simple code for complex problems....
I am more like donkey than shrek

Mogens Lundholm

  • New Member
  • *
  • Posts: 23
Re: Large or huge sets
« Reply #19 on: April 18, 2020, 10:38:26 am »
Large or huge sets are often requested. Just today I needed one. Wrote it in ten minutes, but maybe useful?

Get this message:
unithugeset.pas(23,3) Fatal: Cannot find generics.collections used by UnitHugeSet of the Project Inspector.

PascalDragon

  • Hero Member
  • *****
  • Posts: 1751
  • Compiler Developer
Re: Large or huge sets
« Reply #20 on: April 18, 2020, 10:55:22 am »
As mentioned in the other thread:

You either need to use FPC 3.2 or newer as Generics.Collections ships with that by default or if you want to use 3.0.4 you can download or clone this repo of the original author (hnb on this forum).

Mogens Lundholm

  • New Member
  • *
  • Posts: 23
Re: Large or huge sets
« Reply #21 on: April 19, 2020, 08:42:21 am »

Large or huge sets:
unit largesets;

PascalDragon wrote:
"Best to report this in the other thread, so that Thaddy knows that he might
want to fix this."

I am testing generics.collections for an object for sets

Test program with two sets, s1=[10,11], s2=[20,1000020]. The code snip writes s1, s2 and s1+s2 two times and
the expected result second time is of cause the same result as first time - but is not.
Code: Pascal  [Select][+][-]
  1. // Set 1 = [10,11], Set 2 = [20,1000020],
  2.   write('Set 1:   '); writeset(s1);
  3.   write('Set 2:   '); writeset(s2);
  4.   write('Set 1+2: '); writeset(s1+s2);
  5.  
  6.   write('Set 1:   '); writeset(s1);
  7.   write('Set 2:   '); writeset(s2);
  8.   write('Set 1+2: '); writeset(s1+s2);        
  9.  

The result output is:
Code: Pascal  [Select][+][-]
  1. Set 1:   [10,11]
  2. Set 2:   [20,1000020]
  3. Set 1+2: [10,11,20,1000020]
  4. Set 1:   [10,11]
  5. Set 2:   [10,11,20,1000020]
  6. Set 1+2: [10,11,20,1000020]
  7.  

The problem is that "operator+" overwrites the s2-variable.
 
All my efforts seem to end with the problem of the assignment operator.

E.g. operator:=(s: TNormalSet): TVarSet;

But what was needed was:

operator:=(var r: TVarSet; s: TVarSet);

So that we had the address that should be assigned to. Then
we could decide about allocation and deallocation.

Also an "operator.." - iteration and operator[] (specifying set or list) would be nice. Also "+=", "*=" etc.



« Last Edit: April 19, 2020, 12:03:56 pm by Mogens Lundholm »

Thaddy

  • Hero Member
  • *****
  • Posts: 10206
Re: Large or huge sets
« Reply #22 on: April 19, 2020, 09:08:53 am »
The bug seems not in my code but in the underlying generics.collections.
I will contact Maciej (a.k.a. hnb) if he can confirm this. He wrote that code.
Maciej, if you read this can you please test?

But I will do some extra tests myself. (I have a test suite for this code, but it is a bit of a mess)
Please note that I actually used this code in my gold parser translation and never ran into problems (yet)
« Last Edit: April 19, 2020, 09:20:52 am by Thaddy »
I am more like donkey than shrek

PascalDragon

  • Hero Member
  • *****
  • Posts: 1751
  • Compiler Developer
Re: Large or huge sets
« Reply #23 on: April 19, 2020, 12:03:20 pm »
The bug seems not in my code but in the underlying generics.collections.
I will contact Maciej (a.k.a. hnb) if he can confirm this. He wrote that code.
Maciej, if you read this can you please test?

Did you even look at your code?

Code: Pascal  [Select][+][-]
  1.   operator + (const a,b:TWordset):TWordSet;
  2.   begin
  3.     b.UnionWith(a);
  4.     Result := b;
  5.   end;

You are modifying b. And TSortedHashSet<> is a class, so of course that modifies also the passed in instance.

Thaddy

  • Hero Member
  • *****
  • Posts: 10206
Re: Large or huge sets
« Reply #24 on: April 19, 2020, 12:05:09 pm »
Aha. tnx Sven. Will fix. Strange that - for my use - this did not show up, though.
Is this correct?
Code: Pascal  [Select][+][-]
  1.   { union }
  2.   operator + (const a,b:TWordset):TWordSet;
  3.   begin  
  4.     Result := b;
  5.     Result.UnionWith(a);
  6.   end;
 
« Last Edit: April 26, 2020, 11:11:00 am by Thaddy »
I am more like donkey than shrek

Thaddy

  • Hero Member
  • *****
  • Posts: 10206
Re: Large or huge sets
« Reply #25 on: April 26, 2020, 11:12:46 am »
Aha. tnx Sven. Will fix. Strange that - for my use - this did not show up, though.
Is this correct?
Code: Pascal  [Select][+][-]
  1.   { union }
  2.   operator + (const a,b:TWordset):TWordSet;
  3.   begin  
  4.     Result := b;
  5.     Result.UnionWith(a);
  6.   end;


If it is, its fixed for all occurrences and I can add a new version.
« Last Edit: April 26, 2020, 11:14:27 am by Thaddy »
I am more like donkey than shrek

PascalDragon

  • Hero Member
  • *****
  • Posts: 1751
  • Compiler Developer
Re: Large or huge sets
« Reply #26 on: April 26, 2020, 12:11:14 pm »
First of, sorry that I didn't answer. For some reason I had not seen that you had replied. %)

Second: Thaddy, I thought you know how classes work? Class instance variables are pointers to class instances. Simply assigning the pointer to another class instance variable will not change anything, you're operating on the same instance. You need to completely clone the set.

Here is an example that fails:

Code: Pascal  [Select][+][-]
  1. program tsets;
  2.  
  3. uses
  4.   largesets;
  5.  
  6. var
  7.   w1, w2, w3: TWordSet;
  8. begin
  9.   w1 := TWordSet.Create;
  10.   w2 := TWordSet.Create;
  11.   w1.Add($8000);
  12.   w2.Add($0004);
  13.  
  14.   Writeln(w1.Count, ' ', w2.Count);
  15.  
  16.   w3 := w1 + w2;
  17.  
  18.   Writeln(w1.Count, ' ', w2.Count);
  19.  
  20.   if w1.Count <> 1 then
  21.     Writeln('w1 was modified!');
  22.   if w2.Count <> 1 then
  23.     Writeln('w2 was modified!');
  24.   if w3.Count <> 2 then
  25.     Writeln('w3 has wrong amount of elements!');
  26. end.

Thaddy

  • Hero Member
  • *****
  • Posts: 10206
Re: Large or huge sets
« Reply #27 on: April 26, 2020, 12:24:38 pm »
Clear.
I am more like donkey than shrek

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 8493
  • FPC developer.
Re: Large or huge sets
« Reply #28 on: May 02, 2020, 01:17:52 pm »
I tried to make a generic value type set, but it doesn't work.

  • needs ord(T) and that is refused. Probably need ordinal constraint type
  • operator overloading for records is refused (?)

Code: Pascal  [Select][+][-]
  1. program bigvalueset;
  2. // test to make value type sets.
  3.  
  4. {$define useFPCsyntax}                     // to test in objfpc mode in case there are differences, and because we invoke ord() on enums.
  5. {define testoperatoroverloading}          // try operator overloading
  6.  
  7. {$ifdef useFPCsyntax}
  8. {$Mode objfpc}
  9. {$else}
  10. {$Mode delphi}
  11. {$endif}
  12. {$modeswitch advancedrecords}
  13. type  
  14.     {$ifdef useFPCsyntax}generic {$endif}
  15.      TBigValueSet<T> =  record
  16.                            Type
  17.                             TMySet =  {$ifdef useFPCsyntax}specialize {$endif} TBigValueSet<T>;
  18.                            var
  19.                            data : array[0.. ord(high(T)) div 32] of cardinal;
  20.  
  21.                            procedure xinclude (element:T); inline;
  22.                            procedure xexclude (element:T); inline;
  23.                            function test(element:T) : boolean; inline;
  24.                            {$ifdef testoperatoroverloading}
  25.                            class operator in (A: T; const B: TMySet): boolean;  
  26.                            {$endif}
  27.                         end;
  28.  
  29. Type
  30.     TDWordSet = set of 0..31;
  31.     pdwordset = ^TDwordSet;
  32.  
  33.  
  34.  
  35. {$ifdef testoperatoroverloading}
  36. class operator TBigValueSet<T>.in (A: T; const B: TMySet): boolean;                        
  37. begin
  38. end;
  39. {$endif}
  40.  
  41. procedure TBigValueSet{$ifndef useFPCsyntax} <T>{$endif}.xinclude(element:T);
  42. begin
  43.   system.include (pdwordset(data[ord(element) div 32])^,cardinal(ord(element) and 31));
  44. end;
  45.  
  46. procedure TBigValueSet{$ifndef useFPCsyntax}<T>{$endif}.xexclude (element:T);
  47. begin
  48.  system.exclude (pdwordset(data[ord(element) div 32])^,cardinal(ord(element) and 31));
  49. end;
  50.  
  51. function TBigValueSet{$ifndef useFPCsyntax}<T>{$endif}.test (element:T):boolean;
  52. begin
  53.   result:=cardinal(ord(element) and 31) in pdwordset(data[ord(element)^ div 32])^;
  54. end;
  55.  
  56. begin
  57. end.
  58.  

avk

  • Sr. Member
  • ****
  • Posts: 269
    • my self-education project
Re: Large or huge sets
« Reply #29 on: May 02, 2020, 06:23:04 pm »
Something like that?
Code: Pascal  [Select][+][-]
  1. program test_bigset;
  2. {$mode objfpc}{$modeswitch advancedrecords}
  3. type
  4.   generic TBigValueSet<T> = record
  5.   private
  6.   const
  7.     LOWER   = Low(T);
  8.     UPPER   = High(T) - LOWER;
  9.     SET_LEN = (Upper shr 5 + Ord(Upper and 31 <> 0)) + Ord(UPPER = 0);
  10.   type
  11.     TDWordBits = 0..31;
  12.     TDWordSet = set of TDWordBits;
  13.     PDWordSet = ^TDWordSet;
  14.     TSet = array[0..Pred(SET_LEN)] of DWord;
  15.   var
  16.     FSet: TSet;
  17.     class operator Initialize(var s: TBigValueSet);
  18.   public
  19.     procedure Include(aValue: T);
  20.     procedure Exclude(aValue: T);
  21.     class operator +(constref L, R: TBigValueSet): TBigValueSet;
  22.     class operator -(constref L, R: TBigValueSet): TBigValueSet;
  23.     class operator *(constref L, R: TBigValueSet): TBigValueSet;
  24.     class operator ><(constref L, R: TBigValueSet): TBigValueSet;
  25.     class operator =(constref L, R: TBigValueSet): Boolean;
  26.     class operator <=(constref L, R: TBigValueSet): Boolean;
  27.     class operator in (aValue: T; const aSet: TBigValueSet): Boolean;
  28.   end;
  29.  
  30. class operator TBigValueSet.Initialize(var s: TBigValueSet);
  31. begin
  32.   s.FSet := Default(TSet);
  33. end;
  34.  
  35. procedure TBigValueSet.Include(aValue: T);
  36. begin
  37.   System.Include(PDWordSet(@FSet[(Integer(aValue) - LOWER) shr 5])^, (Integer(aValue) - LOWER) and 31);
  38. end;
  39.  
  40. procedure TBigValueSet.Exclude(aValue: T);
  41. begin
  42.   System.Exclude(PDWordSet(@FSet[(Integer(aValue) - LOWER) shr 5])^, (Integer(aValue) - LOWER) and 31);
  43. end;
  44.  
  45. class operator TBigValueSet.+(constref L, R: TBigValueSet): TBigValueSet;
  46. var
  47.   I: Integer;
  48. begin
  49.   for I := 0 to Pred(SET_LEN) do
  50.     Result.FSet[I] := L.FSet[I] or R.FSet[I];
  51. end;
  52.  
  53. class operator TBigValueSet.-(constref L, R: TBigValueSet): TBigValueSet;
  54. var
  55.   I: Integer;
  56. begin
  57.   for I := 0 to Pred(SET_LEN) do
  58.     Result.FSet[I] := L.FSet[I] and not R.FSet[I];
  59. end;
  60.  
  61. class operator TBigValueSet.*(constref L, R: TBigValueSet): TBigValueSet;
  62. var
  63.   I: Integer;
  64. begin
  65.   for I := 0 to Pred(SET_LEN) do
  66.     Result.FSet[I] := L.FSet[I] and R.FSet[I];
  67. end;
  68.  
  69. class operator TBigValueSet.><(constref L, R: TBigValueSet): TBigValueSet;
  70. var
  71.   I: Integer;
  72. begin
  73.   for I := 0 to Pred(SET_LEN) do
  74.     Result.FSet[I] := L.FSet[I] xor R.FSet[I];
  75. end;
  76.  
  77. class operator TBigValueSet.=(constref L, R: TBigValueSet): Boolean; inline;
  78. var
  79.   I: Integer;
  80. begin
  81.   for I := 0 to Pred(SET_LEN) do
  82.     if L.FSet[I] <> R.FSet[I] then
  83.       exit(False);
  84.   Result := True;
  85. end;
  86.  
  87. class operator TBigValueSet.<=(constref L, R: TBigValueSet): Boolean; inline;
  88. var
  89.   I: Integer;
  90. begin
  91.   for I := 0 to Pred(SET_LEN) do
  92.     if R.FSet[I] <> L.FSet[I] or R.FSet[I] then
  93.       exit(False);
  94.   Result := True;
  95. end;
  96.  
  97. class operator TBigValueSet.in (aValue: T; const aSet: TBigValueSet): Boolean;
  98. begin
  99.   Result := TDWordBits((Integer(aValue) - LOWER) and 31) in PDWordSet(@aSet.FSet[(Integer(aValue) - LOWER) shr 5])^;
  100. end;
  101.  
  102. type
  103.   TMyRange = -1022..1023;
  104. var
  105.   s, s2: specialize TBigValueSet<TMyRange>;
  106. begin
  107.   WriteLn('SizeOf(s) = ', SizeOf(s));
  108.   s.Include(-5);
  109.   WriteLn('-5 in s = ', -5 in s);
  110.   s.Include(1022);
  111.   WriteLn('1022 in s = ', 1022 in s);
  112.   s2.Include(-15);
  113.   s2.Include(-900);
  114.   s2 := s2 + s;
  115.   WriteLn('-5 in s2 = ', -5 in s2);
  116.   WriteLn('-15 in s2 = ', -15 in s2);
  117.   WriteLn('-900 in s2 = ', -900 in s2);
  118.   WriteLn('1022 in s2 = ', 1022 in s2);
  119.   s2 := s2 - s2;
  120.   WriteLn('-5 in s2 = ', -5 in s2);
  121.   WriteLn('-15 in s2 = ', -15 in s2);
  122.   WriteLn('-900 in s2 = ', -900 in s2);
  123.   WriteLn('1022 in s2 = ', 1022 in s2);
  124. end.
  125.  
« Last Edit: May 03, 2020, 11:34:59 am by avk »

 

TinyPortal © 2005-2018