Dear posets fan,
I was trying to use the subposet method of posets and I find it extremely
slow. I'll post a ticket together with a patch when I'll connect to a network
(I'm currently on the sea shore ;-).
The main reason why it is slow is because to construct a subposet of
cardinality 23 of a poset of cardinality 24 (I'm just removing the lower
element) the code has to perform no less that 38679 equality comparison !
At the end most of the time (0.216s out of 0.237s) was spent inside
_element_to_vertex for the following reason: the poset P is a non facade poset
for a set W. But before my patch the code was comparing element of W and not
P. Here is what happen if you call P.is_less_that(x,y) when x and y are in W
and not in P:
def is_less_than(self, x, y):
return self.compare_elements(x,y) == -1
then
def compare_elements(self, x, y):
i, j = map(self._element_to_vertex,(x,y))
[...]
And that's where things start to go crazy:
def _element_to_vertex(self,x):
if x in self:
return self(x).vertex
else:
raise ValueError, "element (=%s) not in poset"%x
So there is a call to contains:
def __contains__(self,x):
if isinstance(x,self.element_class):
[...]
return x in self._elements # list search 1 here
So x is compared to the each element of self._elements until it is found.
Then there is a call to self(x).vertex:
def __call__(self,element):
if isinstance(element, self.element_class) and element.parent() == self:
return element
elif element in self._elements: # list search 2 here
return self.element_class(self, element,
self._elements.index(element)) # list search 3 here
Once again in elif element in self._elements element=x is compared to the
element of self._element... and then:
self._elements.index(element))
if two times where not enough it is seached again just to be sure that
element=x is really in self._elements...
I fixed subposet not to call this anymore but I think this should definitely
be fixed... I suggest the following fix:
1 - _element_to_vertex should'nt do any check. This is the responsibility of
__call__
def _element_to_vertex(self,x):
return self(x).vertex
2 - use exception properly to handle the case where the element is not in the
poset, without to search for it in the list.
I'll put a second patch on trac for this one. Comments are mostly welcome !
Cheers,
Florent
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
