taking Product() of a very long list of transpositions blows up memory

[dimpase]

Multiplying 370656 transpositions, with disjoint support, in a list s, using Product(s), blows up memory
No matter how big (I went to 10GB!) I set -o, I get (with GAP 4.8.3)

 Error, reached the pre-set memory limit (change it with the -o command line option) in
 res[i] := func( C[i] ); at /home/scratch/dimpase/gap/latest/lib/coll.gi:743 called from
 <function "List">( <arguments> )
 called from read-eval loop at line 24  of x.g

here is how I get there:
x.g.txt

PS. I wish there was a function to convert list of lists into a permutation. Of course I can create a list, presenting the permutation I need, and convert it into permutation (or just multiplying 370656 permutations one by one - this took 30 min or so of wall clock time).

[frankluebeck]

The first problem is that you probably cannot hold these transposition in memory:

gap> MemoryUsage( (300000,300001) );
1200020

And, multiplying these permutations is very inefficient (GAP has no data type for sparse partitions (maybe it should?):

gap> # instead of:   w:=Product(List(s,y->(y[1],y[2]))); you can avoid the memory problem with:
gap> w := ();;
gap> for y in s do w := w*(y[1],y[2]); od; time;  # will probably take hours
???
gap> # but:
gap> w := [1..741312];;
gap> for y in s do w[y[1]] := y[2]; w[y[2]] := y[1]; od; time;
64
gap> w := PermList(w);; time;
4

[dimpase]

Ah, OK, thanks, it has not crossed my mind that permutations are never sparse in GAP. Although this kind of usage is a good example of usefulness of sparse permutations.

[markuspf]

For science, I ran the for loop, it took 3604669 milliseconds (so, almost exactly an hour), according to GAP's time on my laptop (Core i5 mobile of some description).

[markuspf]

Sparse permutations might be a nice project to instruct a beginner (student or otherwise) in GAP programming (in case noone gets frustrated quickly enough to do it).

[dimpase]

I guess it depends upon how far one is willing to take it. There is a
potential advantage of switching over to sparse representation
automatically - the question is how often in practice such a setup arises.

On Mon, Apr 11, 2016 at 10:52 AM, Markus Pfeiffer notifications@github.com
wrote:

Sparse permutations might be a nice project to instruct a beginner
(student or otherwise) in GAP programming (in case noone gets frustrated
quickly enough to do it).

—
You are receiving this because you authored the thread.
Reply to this email directly or view it on GitHub
#723 (comment)

[fingolfin]

Besides sparse permutations (see issue #724), another thing that would help here is a permutation accumulator storing the result of the product computation; see issue #550 and PR #567

[fingolfin]

Closing this, as there is no actual bug here, and all the ideas for enhancements one might derive from it seem to be already logged in various issues.