#5844: [with patch, needs review] Improvement of
{{{PermutationGroup_generic.has_element()}}} and {{{is_subgroup}}}
--------------------------+-------------------------------------------------
Reporter: SimonKing | Owner: SimonKing
Type: defect | Status: new
Priority: minor | Milestone: sage-3.4.2
Component: group_theory | Keywords: PermutationGroup has_element
is_subgroup
--------------------------+-------------------------------------------------
The old version of {{{PermutationGroup_generic.has_element(self,item)}}}
is
{{{
item = PermutationGroupElement(item, self, check=False)
return item in self.list()
}}}
Hence, the whole list of elements must be created! Instead, I suggest to
invoke {{{PermutationGroup_generic.__contains__()}}}, hence:
{{{
item = PermutationGroupElement(item, self, check=False)
return item in self
}}}
The only difference between {{{has_element}}} and {{{__contains__}}} then
is that the former may raise an error if one can not make a
{{{PermutationGroupElement}}} out of the item.
The performance considerably improves. Here are indirect. The method
{{{is_subgroup()}}} calls {{{has_element}}}.
With the patch, one has:
{{{
sage: G=SymmetricGroup(7)
sage: H=SymmetricGroup(6)
sage: H.is_subgroup(G)
True
sage: timeit('H.is_subgroup(G)')
625 loops, best of 3: 50.5 µs per loop
}}}
To my surprise, Gap is slower:
{{{
sage: timeit('gap(H).IsSubgroup(gap(G))')
5 loops, best of 3: 1.55 ms per loop
}}}
Without the patch, the computation is ''very'' slow:
{{{
sage: time H.is_subgroup(G)
CPU times: user 3.94 s, sys: 0.51 s, total: 4.45 s
Wall time: 4.80 s
True
}}}
Last, I'd like to demonstrate the difference between {{{has_element()}}}
and {{{__contains__()}}}:
{{{
sage: 1 in G
True # since G(1) is the trivial permutation
sage: G.has_element(1)
ERROR: An unexpected error occurred while tokenizing input
...
TypeError: 'sage.rings.integer.Integer' object is not iterable
}}}
The latter is what happens when trying conversion of 1 into a
{{{PermutationGroupElement}}}.
__Conclusion__:[[BR]]
The change that I made is very small but yields a huge improvement.
However, what was the original reason to write {{{has_element}}} in that
way? Does {{{g in G}}} sometimes return an answer different from {{{g in
G.list()}}}, if g is a {{{PermutationGroupElement}}}?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5844>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
