search

gap-packages / NautyTracesInterface

Interface from GAP to Nauty
https://gap-packages.github.io/NautyTracesInterface/
Other
6 stars 6 forks source link

Speed up constructors in NautyTracesInterface.gi #7

Closed markusbaumeister closed 6 years ago

markusbaumeister commented 6 years ago

This concerns two changes: 1) The two list commands in NautyGraphFromEdges are combined into one loop. Therefore the list "edges" is only traversed once. Furthermore the function call i->i[1] is replaced in both cases, which gives another factor of 2. 2) The combination SortedList(DuplicateFreeList()) is replaced by Set(), which gives a huge speedup, as shown in this example:

gap> L := List( [1..10^4], Phi );;
gap> Set(L);; time;
6
gap> SortedList(DuplicateFreeList(L));; time;
15
gap> L := List( [1..10^6], Phi );;
gap> Set(L);; time;
192
gap> SortedList(DuplicateFreeList(L));; time;
53843
sebasguts commented 6 years ago

Thank you :)