Dear Robert,
you might want to combine Python with GAP using Sage
(www.sagemath.org).
Then you can benefit from the Python's (or even Cython's)
speed and a fast interface to GAP for things
you need to do in GAP.
HTH,
Dmitrii
On Fri, Jan 17, 2014 at 09:23:43AM +0000, Wolstenholme, Robert wrote:
> Thanks, this is what I wanted.
> However, I timed it this morning and found it to actually be slower than the
> method I previously mentioned (currently speed is of significant importance
> for what I'm doing). I've included the test script below. You can vary the
> values of `n` (number of lists) and `k` (size of lists). Note for `n=6` and
> `k=9` I am getting,
>
> IteratorOfCartesianProduct Method: 452ms
> My Mentioned Method : 203ms
> Python for Reference : 066ms
>
> I was hoping for something nearer the speed of the Python implementation.
>
> Code (can be copied and pasted)
> ####################################################################################
> n := 6;
> k := 9;
>
> ############################
> #IteratorOfCartesianProduct Method#
> ############################
> lol := [];
> for i in [1..n] do
> lol[i] := [1..k];
> od;
>
> a := 1;
>
> start := Runtime();
>
> for x in IteratorOfCartesianProduct(lol) do
> #a := a + 1;
> #Print("x: ", x, "\n");
> od;
>
> total1 := Runtime() - start;
>
>
> ###################
> #My Mentioned Method#
> ###################
> size_rc := List([1..n], x -> k);
> base := List([1..n], x -> 1); #We store the iteration step state in base
> a := 1;
>
> start := Runtime();
> repeat
>
> #Perform whatever list[i][base[i]] calculations here
> #a := a + 1;
> #Print("Base: ", base, "\n");
>
> #Execute the incrementor
> base[1] := base[1] + 1;
> for j in [2..n] do
> if base[j-1] = size_rc[j-1] + 1 then
> base[j] := base[j] + 1;
> base[j-1] := 1;
> fi;
> od;
> until base[n] = size_rc[n] + 1;
>
> total2 := Runtime() - start;
>
> Print("\nTotal1: ", total1, "\nTotal2: ", total2);
> ####################################################################################
>
> Thanks,
> Rob
>
> ________________________________________
> From: Alexander Konovalov [alexander.konova...@gmail.com]
> Sent: 16 January 2014 22:19
> To: Wolstenholme, Robert
> Cc: forum@mail.gap-system.org
> Subject: Re: [GAP Forum] Iteration Over Lists of Lists
>
> Very briefly (sorry, don't have time for a larger explanation today)
> - in this case, see IteratorOfCartesianProduct. For example, after
>
> lists := [];
> lists[1] := [1,2,3];
> lists[2] := [4,5];
>
> try this:
>
> gap> for x in IteratorOfCartesianProduct(lists) do Print(x,"\n");od;
> [ 1, 4 ]
> [ 1, 5 ]
> [ 2, 4 ]
> [ 2, 5 ]
> [ 3, 4 ]
> [ 3, 5 ]
>
> This iterates over the cartesian product without generating the list of all
> tuples from it, and should work fast enough.
>
> Best wishes
> Alexander
>
>
>
> On 16 Jan 2014, at 22:13, "Wolstenholme, Robert"
> <robert.wolstenholm...@imperial.ac.uk> wrote:
>
> > Thanks for the reply. I don't think I was clear enough with my initial
> > question though so have given the example below:
> >
> > ###################################################################################
> > Consider
> >
> > lists := []
> > lists[1] := [1,2,3]
> > lists[2] := [4,5]
> >
> > I would now like to iterate over the cartesian product of `lists[1]` and
> > `lists[2]` i.e. `[[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]]`.
> >
> > For an example this small, you could simply store the cartesian product
> > itself in a list and iterate over that. This obviously becomes very
> > inefficient if we have more lists with a larger number of values.
> >
> >
> > A better way is, if we have `n` lists and `size_rc[i] := Size(list[i])`, we
> > can avoid storing/calculating the Cartesian product with
> >
> > base := List([1..n], x -> 1); #We store the iteration step state in base
> > while base <> size_rc do
> >
> > #Perform whatever list[i][base[i]] calculations here
> >
> > #Execute the incrementor
> > base[1] := base[1] + 1;
> > for j in [2..n] do
> > if base[j-1] = size_rc[j-1] + 1 then
> > base[j] := base[j] + 1;
> > base[j-1] := 1;
> > fi;
> > od;
> > od;
> >
> > then at each loop of the while `base` contains the values we need.
> >
> > However this is still far slower than the Python implementation I mentioned
> > before. I was wondering if there was a way in GAP to speed up this
> > iteration (maybe by pointing to the memory locations of the lists)?
> >
> > Thanks,
> > Rob
> >
> > ________________________________________
> > From: Alexander Konovalov [alexander.konova...@gmail.com]
> > Sent: 16 January 2014 22:01
> > To: Wolstenholme, Robert
> > Cc: forum@mail.gap-system.org
> > Subject: Re: [GAP Forum] Iteration Over Lists of Lists
> >
> > On 16 Jan 2014, at 20:03, "Wolstenholme, Robert"
> > <robert.wolstenholm...@imperial.ac.uk> wrote:
> >
> >> Is there a way in GAP to 'quickly' iterate of lists of lists i.e. like the
> >> Python itertools.product() function?
> >>
> >
> > Yes, see `21.20 Operations for Lists' from the GAP Reference Manual. You
> > may enter `?Operations for Lists' in GAP or see it online at
> >
> >
> > http://www.gap-system.org/Manuals/doc/ref/chap21.html#X7DF510F7848CBBFD
> >
> > A random example just to expose the syntax and some functions:
> >
> > gap> l:=List([1..10],i -> [1..i]);
> > [ [ 1 ], [ 1, 2 ], [ 1 .. 3 ], [ 1 .. 4 ], [ 1 .. 5 ], [ 1 .. 6 ],
> > [ 1 .. 7 ], [ 1 .. 8 ], [ 1 .. 9 ], [ 1 .. 10 ] ]
> > gap> Sum( List( l, x -> Product( List( x, Fibonacci ) ) ) );
> > 124819000
> >
> >
> > HTH,
> > Alexander
> >
> >
> >
> >
>
>
> _______________________________________________
> Forum mailing list
> Forum@mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
