[GAP Forum] New (in development) package : gapcpp

[Alexander Hulpke]

Dear Forum,

> On Apr 1, 2015, at 4/1/15 5:32, Sandeep Murthy <s.murthy at mykolab.com> wrote:
> 
> This could be useful for optimising sorting and search, since GAP is very slow.

I don't think that is true for the sort routine itself. However if you put complicated objects (say groups) in a list and sort it, the individual element comparisons can become expensive, as these objects are not represented in a ``canonical form'' (i.e. a group can have many different generating sets), and GAP guarantees that the ordering used will be independent of the internal representation.

So for example for comparing groups, GAP has to compute a lexicographically minimal generating set, and then will compare these generating sets. The time spent in in computing these, not in the sort algorithm, and coding it in C will not speed it up.

The solution to this is basically to avoid, if possible, having to sort lists of groups, but to use other data structures.

Best,

    Alexander Hulpke

> 
> Can it deal with lists of GAP objects, like groups and tuples?
> 
> Sandeep Murthy
> s.murthy at mykolab.com
> 
>> On 1 Apr 2015, at 12:20, Christopher Jefferson <caj21 at st-andrews.ac.uk> wrote:
>> 
>> Ever wish you could just write C and C++ code in GAP? Well now you can,
>> with the gapcpp package from: https://github.com/ChrisJefferson/gapcpp
>> 
>> After running './configure' in the packages directory and loading it, you
>> will find one method, 'CompileMethod', which accepts C++ (or C) code, the
>> name of your function and it's number of arguments. The function is then
>> automatically linked into GAP, and GAP types turned into C++ types (and
>> vice versa).
>> 
>> Here's an easy example:
>> 
>> gap> fun := CompileMethod("int f(int X) { return X; }", "f", 1);;
>> gap> fun(3);
>> 3
>> 
>> That's fairly boring however. Let's consider something more interesting!
>> 
>> Perhaps we want to sort a list of integers by their last digit:
>> 
>> gap> SortBy([1..1000000], x -> x mod 10);;
>> gap> time;
>> 548
>> 
>> Hmm.. Lets give that 'mod' function some C++ power!
>> 
>> gap> m := CompileMethod("int f(int X) { return X % 10; }", "f", 1);;
>> gap> SortBy([1..1000000], m);;
>> gap> time
>> 487
>> 
>> Hmm, a little speedup, but not as much as we would like. Let's push the
>> whole thing into C++, using new 'triple quotes'  to make the code easier
>> to write (in the master branch of GAP, not package specific!)
>> 
>> gap> x := CompileMethod("""
>> bool comp(int i, int j)
>> { return i%10 < j%10; }
>> std::vector<int> sb(std::vector<int> i)
>> { std::sort(i.begin(), i.end(),comp); return i; }""", "sb", 1);
>> gap> x([1..1000000]);;
>> gap> time;
>> 48
>> 
>> Wow, 10x speedup!
>> 
>> Of course, C++ lets us do new things. Perhaps we really wish we had a
>> stable sort? No problem!
>> 
>> gap> x := CompileMethod("""
>> bool comp(int i, int j)
>> { return i%10 < j%10; }
>> std::vector<int> sb(std::vector<int> i)
>> { std::stable_sort(i.begin(), i.end(),comp); return i; }""", "sb", 1);
>> gap> x([1..1000000]);;
>> gap> time;
>> 124
>> 
>> A little slower, but with the bonus of being stable!
>> 
>> Let's try some more things:
>> 
>> gap> PartialSums([1..50000]);;
>> gap> time;
>> 26021
>> 
>> gap> x := CompileMethod("""
>> #include <numeric>
>> std::vector<int> sums(std::vector<int> v)
>> {
>> std::vector<int> out(v.size());
>> // r means 'reverse', we do this to agree with GAP's order
>> std::partial_sum(v.rbegin(), v.rend(), out.rbegin());
>> return out;
>> }""", "sums", 1);;
>> gap> PartialSums([1..50000]);;
>> gap> time;
>> 1
>> 
>> The following C++ types are currently supported (recursively). More types
>> can be added on request!
>> 
>> std::vector
>> std::list
>> std::deque
>> std::pair
>> std::string
>> int
>> Bool
>> vec1 (a custom vector type which is 1-indexed, for each GAP<->C++
>> integration)
>> 
>> optional (a way of marking missing values, so std::vector<optional<int> >
>> supports lists with missing values, unlike std::vector<int>)
>> 
>> If you understand GAP, You can also use Obj and all the normal GAP method
>> to access objects. There is also initial support for gap records (see the
>> tests for examples).
>> 
>> 
>> I am interested in any requests for improvements, or usage of this package
>> (or wished usages of this package).
>> 
>> 
>> Chris
>> 
>> 
>> _______________________________________________
>> Forum mailing list
>> Forum at mail.gap-system.org
>> http://mail.gap-system.org/mailman/listinfo/forum
> 
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum