Union: computing the union of many sets in on step if this is more efficient

[Stefan-Kohl]

What to do when forming a union of many sets in one step would be quick, but the function Union does it step-by-step, calling the operation Union2 repeatedly? -- This is interesting for example in situations when the union of many residue class unions should be computed (every call to Union2 needs to bring the result to normal form etc., such that computing the union of several thousand residue class unions can sometimes take a thousand times longer than it would take to compute the union in one step). Of course, the ugly solution would be to write a dedicated function with a name different from Union -- but I am looking for a more elegant solution.

[james-d-mitchell]

Can you please give an example?

[Stefan-Kohl]

Let's just take the trivial example of computing the union of all residue classes modulo n.

gap> Union(AllResidueClassesModulo(100));
Integers
gap> time;
56
gap> Union(AllResidueClassesModulo(1000));
Integers
gap> time;                                
1876
gap> Union(AllResidueClassesModulo(2000));
Integers
gap> time;                                
6564
gap> Union(AllResidueClassesModulo(3000));
Integers
gap> time;                                
17336

The time is taken by forming all n-1 intermediate unions and bringing each of them to normal form, i.e. in particular figuring out whether they can be written with modulus n/2, n/3, n/5, etc..

[james-d-mitchell]

Thanks @Stefan-Kohl, but AllResidueClassesModulo isn't a function in GAP, maybe a package is required?

[james-d-mitchell]

I installed rcwa and then your examples run, here's the profile, it seems that essentially all of the time is spent in the method for Union2 from ResClasses. That being the case, isn't this an issue for ResClasses rather than GAP? Or do you have another example which doesn't use ResClasses?

  count  self/ms  chld/ms  stor/kb  chld/kb  package  function
  10458        2        0        0        0  (oprt.)  HasIS_SSORT_LIST
  10461        2        0       87        0  GAP      in: for integers
  10458        1        0        0        0  (oprt.)  SetIS_SSORT_LIST
  12691        3        0        0        0  GAP      StandardAssociate: for integers
  16380        3        0        0        0  (oprt.)  HasLENGTH
  17150        3        0      133        0  GAP      Difference: for empty list, and collection
  18690        4        0        0        0           =: for cyclotomic and unknown
  12690        2        2        0        0  (oprt.)  HasSize
  17917        3        2      783        0  (oprt.)  IsSSortedList
  15687        7        0    20070        0           Enumerator: for a collection that is a list
  40428        4        2        0        0  (oprt.)  IsFinite
  10460        2        4      204        0  ResCla*  ResidueClassUnionsFamily
  10460        6        1      122       40  GAP      Intersection
  17150        3        4        0      133  (oprt.)  Difference
  27624        7        1    80566        0  (oprt.)  ShallowCopy
  12691        4        4        0        0  (oprt.)  StandardAssociate
  10460        7        2        0        0  (oprt.)  SetIsEmpty
  10458        8        2      320        0  GAP      Filtered
  85907       12        1        0        0           Meth(=)
  13380        7        8      104    39565  GAP      Concatenation
  40428       18        2        0        0  GAP      Meth(Size)
  80856       32        9      947        0  GAP      Maximum
  48658       12       38        0      490  (oprt.)  Size
   5230       29       25    13136      817  GAP      Meth(SetSize)
   5230        2       54        0    13953  (oprt.)  SetSize
  13380       25       44     2299    39826  GAP      Union
   6000        8      153      474    20381  ResCla*  ResidueClass
      2        0      162        0    20880  ResCla*  AllResidueClassesModulo
   8922        4      162    19858    20856  GAP      List
  99411      217        0   245931        0           SSortedList: for a plist
127959*     1697        0        0        0  (oprt.)  Length
127561*     1824        0   269294        0  (oprt.)  Add
  26146     3771     3719      204   486713  GAP      SSortedList: for a list, and a function
 125557       34     7500        0   506981  (oprt.)  SSortedList
   2229        7     7669     1096   659472  ResCla*  Union2: for two residue class unions in standard rep. (ResC*
   2229        2     7676        0   660569  (oprt.)  Union2
   5229       41     7649    12296   584485  ResCla*  ResidueClassUnionCons: residue list rep., for Z, Z_pi and G*
   5229        0     7691        0   596781  (oprt.)  ResidueClassUnionCons
  10458       11     7698      724   596915  ResCla*  ResidueClassUnionNC
              82             27468                    OTHER
            7906            696126                    TOTAL

[Stefan-Kohl]

To be clear: I meant to ask what best to do about this in ResClasses, if possible without either changing the function Union or introducing a function with a name different from Union for this purpose. However, this can also be rephrased as asking why Union is a function and not an operation -- if it would be an operation, the solution would be very simple: install a method for this operation.

[fingolfin]

Operations cannot be variadic in GAP. So Union cannot be an operation.

I guess that's why we have UnionBlist and IntersectionBlist ...

[ChrisJefferson]

Yes, I was thinking the same as Max, while in practice most people probably union a bunch of the same things (ranges, lists, whatever), there isn't really a way of union hooking into that. I had a similar problem with efficiently intersecting a list of permutation groups. I don't have a good solution unfortunately.

[Stefan-Kohl]

Doing the same for Union (and then maybe also Intersection) seems to me like a good idea. Would this come with any serious drawbacks / was there a reason for not implementing Union in this way?

[fingolfin]

One serious drawback is method dispatch overhead which is especially bad for lists, which are a common argument type for union and intersection.

However, that could be avoided via a suitable "early method" provided via InstallEarlyMethod

[ThomasBreuer]

My understanding is that the idea is as follows:

• Introduce a new operation UnionOp that takes two arguments, first the list of objects whose union is required, second an "example" object from this list.
• Install an "early method" for UnionOp that deals with the case that the first argument is a plain list whose entries are plain lists, by iterating via Union2, and leaves other cases to the method selection.
• Install a generic UnionOp method that does the same as the "early method".
• Delegate from Union to UnionOp. At this point, the current GAP code using Union should work as before.
• Install special UnionOp methods, for example for the situation described by Stefan.

The hope is that the method dispatch overhead for UnionOp is small; still a type computation for the first argument is needed, which is expected to be a plain list, but this list should not be deeply nested.

(The same holds for Intersection, which is in fact more interesting because the result can have a nice structure in many cases.)

[fingolfin]

Sounds good to me. @Stefan-Kohl would you like to tackle implementing this?

[Stefan-Kohl]

@fingolfin In principle yes -- though I fear since my last contribution to core GAP, various procedures have changed.