Hi all,
Sorry to bug you again with this (I already did so a few months back), but I
still have qualms with Sage's built-in Set type. For starters, it does not
offer the same interface that Python's frozenset offers (example: the
issubset() method).
But my more serious concern is speed. I would love to use the
sage.combinat.subset.Subsets_s class to check matroid axioms. For quick
reference:
Def. The function r: E -> Z is the rank function of a matroid if and only if,
for all subsets X, Y of E:
1) r(X) <= |X|
2) if Y is a subset of X then r(Y) <= r(X)
3) r(X union Y) + r(X intersect Y) <= r(X) + r(Y)
This is implemented in a method is_valid() of my Matroid class. I also
implemented a method is_valid2() that uses a class Subsets_s2 in which I
replaced all "Set" occurrences by "set" and otherwise circumvented Sage's
functions. In the following two tests, M had a groundset E of 8 elements (which
is fairly small for a matroid).
sage: %time M.is_valid()
CPU times: user 17.25 s, sys: 0.01 s, total: 17.26 s
Wall time: 17.26 s
True
sage: %time M.is_valid2()
CPU times: user 0.43 s, sys: 0.00 s, total: 0.43 s
Wall time: 0.43 s
True
This may sound harsh, but if this class is so slow to be unusable, what good is
it to have it in Sage?
Cheers,
Stefan.
P.S. Here's the output of
sage: %prun M.is_valid()
Note the almost 15 seconds spent in some __init__ method of set.py.
10806705 function calls (10151090 primitive calls) in 20.788 CPU seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
196865 5.741 0.000 14.824 0.000 set.py:194(__init__)
393730/196865 4.329 0.000 6.109 0.000 lazy_attribute.py:493(__get__)
595225 1.518 0.000 4.966 0.000 {hasattr}
590600 0.939 0.000 0.939 0.000 {method 'fix_to_pos' of
'sage.misc.function_mangling.ArgumentFixer' objects}
398360/398355 0.793 0.000 2.086 0.000
classcall_metaclass.py:116(__call__)
590599 0.776 0.000 1.715 0.000 cachefunc.py:147(__call__)
1 0.747 0.747 20.788 20.788 matroid.pyx:502(is_valid)
275522 0.672 0.000 1.488 0.000 matroid.pyx:127(_wrap)
526336/67591 0.666 0.000 0.738 0.000 combination.py:298(_iterator)
2035283 0.600 0.000 1.170 0.000 set.py:631(__iter__)
669508 0.596 0.000 0.874 0.000 set.py:697(set)
196866 0.362 0.000 0.911 0.000 dynamic_class.py:122(dynamic_class)
275522 0.328 0.000 0.522 0.000 <ipython console>:1(<lambda>)
669508 0.278 0.000 0.278 0.000 set.py:563(object)
275522 0.269 0.000 2.299 0.000 matroid.pyx:933(rank)
393730 0.257 0.000 0.257 0.000 {getattr}
196865 0.256 0.000 15.080 0.000 set.py:600(__init__)
65793 0.226 0.000 5.474 0.000 set.py:40(Set)
65536 0.195 0.000 5.407 0.000 set.py:787(intersection)
65536 0.189 0.000 5.355 0.000 set.py:768(union)
66049 0.146 0.000 6.603 0.000 subset.py:217(__iter__)
330509 0.145 0.000 0.145 0.000 {isinstance}
275522 0.144 0.000 0.144 0.000 {min}
196865 0.127 0.000 4.970 0.000
sets_cat.py:254(_element_constructor_)
65792 0.103 0.000 5.576 0.000 subset.py:233(<lambda>)
65535 0.078 0.000 0.078 0.000 subword.py:270(<lambda>)
265738 0.074 0.000 0.074 0.000 {range}
284773 0.052 0.000 0.052 0.000 {len}
65536 0.038 0.000 0.038 0.000 {method 'union' of 'set' objects}
65793 0.036 0.000 0.087 0.000 set.py:155(is_Set)
65536 0.026 0.000 0.026 0.000 {method 'intersection' of 'set'
objects}
275523 0.023 0.000 0.023 0.000 matroid.pyx:268(groundset)
275522 0.020 0.000 0.020 0.000 matroid.pyx:213(_unwrap)
2056 0.015 0.000 0.034 0.000 combination.py:26(Combinations)
2313 0.009 0.000 0.050 0.000 subword.py:253(__iter__)
16448 0.004 0.000 0.004 0.000 {method 'index' of 'list' objects}
2056 0.004 0.000 0.004 0.000 combination.py:329(__iter__)
257 0.003 0.000 0.011 0.000 subword.py:161(__iter__)
2056 0.002 0.000 0.002 0.000 combination.py:223(__init__)
2056 0.002 0.000 0.006 0.000 {iter}
2313 0.002 0.000 0.002 0.000 subword.py:175(__init__)
257 0.000 0.000 0.002 0.000 subword.py:56(Subwords)
513 0.000 0.000 0.001 0.000 set.py:612(cardinality)
513 0.000 0.000 0.002 0.000 set.py:621(__len__)
257 0.000 0.000 0.000 0.000 subword.py:92(__init__)
1 0.000 0.000 0.000 0.000 combinat.py:964(__init__)
1 0.000 0.000 0.001 0.001 subset.py:122(__init__)
1 0.000 0.000 0.000 0.000 category.py:713(or_subcategory)
1 0.000 0.000 0.000 0.000 cachefunc.py:505(__call__)
1 0.000 0.000 20.788 20.788 <string>:1(<module>)
1 0.000 0.000 20.788 20.788 {method 'is_valid' of
'matroids.matroid.Matroid' objects}
1 0.000 0.000 0.000 0.000
unique_representation.py:514(__hash__)
1 0.000 0.000 0.000 0.000 cachefunc.py:559(get_key)
1 0.000 0.000 0.000 0.000 {id}
1 0.000 0.000 0.000 0.000 {method 'disable' of
'_lsprof.Profiler' objects}
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" 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-combinat-devel?hl=en.
