[GAP Forum] Iteration Over Lists of Lists

Wolstenholme, Robert robert.wolstenholme08 at imperial.ac.uk
Fri Jan 17 12:12:19 GMT 2014


Great, results for `n=6`, `k=9` on my machine,

IteratorOfCartesianProduct Method  : 452ms
Initial Mentioned Method                 : 203ms
Burkhard's Method                          : 047ms
Python                                            : 066ms

Many thanks everyone,
Rob


________________________________________
From: Burkhard Höfling [burkhard at hoefling.name]
Sent: 17 January 2014 11:57
To: forum at mail.gap-system.org
Cc: Wolstenholme, Robert; Alexander Konovalov; Dmitrii Pasechnik
Subject: Re: [GAP Forum] Iteration Over Lists of Lists

Dear Robert,

>> 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,

Iterators cause a lot of overhead per call. If you just modify your code a bit, you should get close to Python speed with GAP. On my machine, I get

teratorOfCartesianProduct Method: 915 ms
Your Mentioned Method                  : 493 ms
variant below:                                 : 125 ms

(didn’t try Python).

Cheers

Burkhard.



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();
stop := false;
repeat

        #Perform whatever list[i][base[i]] calculations here
        #a := a + 1;
        #Print("Base: ", base, "\n");

        #Execute the incrementor
        base[1] := base[1] + 1;
        j := 1;
        while base[j] > size_rc[j] and j < n do
                base[j] := 1;
                j := j + 1;
                base[j] := base[j] + 1;
        od;
until j = n and base[n] > size_rc[n];

total2 := Runtime() - start;




More information about the Forum mailing list