Closed dkrenn closed 8 years ago
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
34e34dc | Trac #17693, comment 36, 19--23: improve docstring of covers (former `_search_covers_`) |
490c223 | Trac #17693, comment 36, 28--31: document role of self |
3de0a1d | Trac #17693, comment 36, 33: explicitly mention merge and can_merge at top of docstring |
485b46f | Trac #17693, comment 36, 34: raise exceptions when merge is not possible |
d5d6bec | check=False in MutablePoset.merge since checked already before |
6da3db1 | Trac #17693, comment 36, 37: extend doc to mention more explicitly that merge is not allowed to change keys |
f1e9f9e | Trac #17693, comment 36, 38: clarify parameter key |
ae0cad9 | Trac #17693, comment 36, 60: mention motivation asymptoic expansions in merge method |
ec15597 | Trac #17693: alternative implementation add |
3c69f6b | Merge remote-tracking branch 'origin/u/cheuberg/asy/mutable-poset-add' into t/17693/asy/mutable-poset |
Replying to @cheuberg:
I read the documentation and the code. I pushed a few reviewer commits.
Cross-reviewed. One commit added.
I have a number of rather minor issues with the documentation which I ask you to fix in order facilitate future maintainance of the code. In three instances, I propose alternative implementations, which might be more readable or slightly more efficient.
Thanks; see my comments below.
- Please add
.. seealso::
blocks between corresponding methods of shell and poset as well as between the accessor methods (keys, elements, shells)
Done.
- there is an empty "Introduction" section at the beginning of the module documentation, the next heading "Example" is on the same level.
Deleted.
- this module was written as part of the asymptotic expansion effort. In contrast to the asymptotic expansion, it does not have the "experimental" decorator. I'd feel more comfortable having it, at least until a larger portion of the asymptotic expansions have been merged.
Activated it; it seems (for some (to me) unknown reason) the warning appears now in every doctest and not only once in the file. Thus, deactivated it again; and I am for keeping it this way.
MutablePoset.__init__
accepts a list of elements. This could be used in several doctests (in particular, in the set operations) as an abbreviation.
Good idea. Done.
MutablePosetShell.__init__
: shall we check thatelement is not None
? Otherwise, handling of special elements would probably be affected.
MutablePosetShell is typically used by the MutablePoset; and there, adding a None
-element is forbidden (see :meth:add
).
MutablePosetShell.key
: I do not understand the sentence "The element is converted by the poset to the key".
Rewritten.
MutablePosetShell.key
: I am surprised that the key is not cached. I imagine that many comparisons will be needed in the lifetime of aMutablePoset
, and in every case, the property key has to be resolved, which calls the property poset, which callsget_key
of the poset.
Now it is cached (see also follow up ticket #19281).
MutablePosetShell.__repr__
: The note box in the docstring is surprising at this point: reading the source file from the top, this is the first point where the representation of the data is explained, after guessing it fromis_special
,is_oo
,is_null
above. I think that it would be better to document these conventions closer to the top, perhaps in the__init__
method or perhaps only as a comment in the source code.
Added a note in the class description.
MutablePosetShell.__repr__
: The code replicates the behaviour ofis_null
andis_oo
. As the__repr__
method is hardly time critical, I'd prefer usingis_null
andis_oo
, here and thus hiding the internal convention.
Rewritten.
MutablePosetShell.le
: the note box could be simplified by suppressing implementation details and speaking about the special elements.
Done.
MutablePosetShell.le
:right <= left
: neitherright
norleft
are defined here.
Rewritten.
MutablePosetShell.le
: the partif other.element is None
could be simplified toreturn not other.successors()
asself
is already known not to be special here.
True; rewritten.
MutablePosetShell.le
: If this is time critical,self._predecessors_
could be used instead ofself.predecessors()
.
Changed.
MutablePosetShell.eq
: note box, see above.
Simplified.
MutablePosetShell.eq
: emphasize that elements with equal keys are considered equal? Currently, this information is somewhat hidden in the note box which at first glance only seems to explain handling of special elements.
Rewritten note box.
MutablePosetShell._copy_all_linked_
: Short description: "Return a copy of all shells" does not correspond to the actual return value, which is only the copy of this shell.
Rewritten.
MutablePosetShell._copy_all_linked_
: the interplay between this method andMutablePoset._copy_shells_
is not well documented: in particular,poset
in_copy_all_linked_
is only used for setting the containing poset, but not for actual inserting into this poset.
Extended description of parameter poset
.
MutablePosetShell._copy_all_linked_
: I do not understand why you testoo == P.oo
: I think thatoo
is an element of the new posetQ
.
oo == P.oo
tests that Q.oo
is mapped to P.oo
.
So
oo is Q.oo
would be more interesting?
oo is Q.oo
is False
since oo
is not in Q
, but just a copy of the oo
in P
with parent-poset Q
. Inserting this into Q
is done in _copy_shells_
.
The current test demonstrates that the poset is not used in comparison, so that would rather belong to
.eq
?
I do not understand what you mean (but it is already late...).
MutablePosetShell._search_covers_
: what is the role ofself
in this method? It trivially influences the return value, but what else?
_search_covers_
does not exist anymore (see 27).
MutablePosetShell._search_covers_
: The explanation of the return value is unclear to me. Is the sentence "Note that..." meant to be a complete description? Does it change ifreverse
is set?
_search_covers_
does not exist anymore (see 27).
MutablePosetShell._search_covers_
: I think that the notions of "upper cover" and "lower cover" need a brief definition; I did not find them in Wikipedia andsage.combinat.posets.posets.FinitePoset.upper_covers
defines the notion.
_search_covers_
does not exist anymore (see 27). Incooperated in covers
.
MutablePosetShell._search_covers_
: According to Wikipedia, a cover is what is called an upper cover here. This is in contrast to the default behaviour here.
_search_covers_
does not exist anymore (see 27).
MutablePosetShell._search_covers_
: what is the difference between this method and.predecessors
? Is the shell necessarily an element of the poset? If not, then there should be a doctest covering this case.
_search_covers_
does not exist anymore (see 27). Incooperated in covers
.
MutablePosetShell.covers
: "originate" is somewhat foreign to the description of the poset.
Rewritten.
MutablePosetShell.covers
: "which are at most the given shell": should that be "which are less than the given shell"?
Rewritten.
MutablePosetShell.covers
see comments onMutablePosetShell._search_covers_
.
Rewritten.
MutablePosetShell.covers
: I think that the following would be an equivalent implementation of this method, which does not need a helper function with side effects.if self == shell: return set() covers = set().union(*(e.covers(shell, reverse) for e in self.successors(reverse) if e.le(shell, reverse))) if covers: return covers else: return set([self])
(pushed as branch
u/cheuberg/asy/mutable-poset-cover
)
Merged and minor simplification.
MutablePosetShell._iter_depth_first_visit_
: document the role of self in this method (only shells>=
this shell are visited).
Documented.
MutablePosetShell.iter_depth_first
: document the role of self in this method (only shells>=
this shell are visited).
Documented.
MutablePosetShell._iter_topological_visit_
: document the role of self in this method (only shells<=
this shell are visited, emphasize the contrast to depth first.).
Documented.
MutablePosetShell.iter_topological_first
: document the role of self in this method (only shells<=
this shell are visited, emphasize the contrast to depth first.).
Documented.
MutablePosetShell.iter_topological_sort
, last example: functionC
is defined, but not used.
Deleted.
MutablePosetShell.merge
: explain what merge is, in particular, that this is defined when constructing the poset.
Documented.
MutablePosetShell.merge
: I am surprised thatcheck=True
leads to a silent failure instead of an exception and thatposet._merge_ is None
does not raise an exception. Document and test this behaviour?
Behavior changed.
MutablePosetShell.merge
: what is the difference betweenposet.remove
andposet.discard
?
See Python's set.
MutablePosetShell.merge
: document that the merge function resulting inNone
leads to deletion of the element.
Done.
MutablePosetShell.merge
: document that the merge function must not change the position of the element in the poset.
Mentioned this more explicitly in docs
MutablePoset.__init__
: Clarify the role ofkey
: in particular,key
does not only influence sorting, but that no two elements are allowed to have the same key.
Done.
MutablePoset.__len__
: Clarify thatnull
andoo
are not counted.
Done.
MutablePoset.shells_topological
: The sentence "If this is None, no sorting according to the representation string occurs." is unclear to me, in particular the role of the representation string.
Rewritten.
MutablePoset.keys_topological
: Due to the chosen key, some of the elements added to the poset are ignored. I do not know why this is demonstrated here.
Removed.
MutablePoset.repr
: INPUT section is incomplete.
Completed.
MutablePoset.repr_full
: INPUT section is incomplete.
Completed.
MutablePoset.add
: the loopfor reverse in (False, True)
simplifies in the second iteration: as all pairs of elements(s, l)
withnew
coverings
andl
coveringnew
have already been broken up whilereverse=False
. Thus it might be more straightforward to do it only once, not usingreverse
at all and saving a few intersections:new._predecessors_ = self.null.covers(new, reverse=False) new._successors_ = self.oo.covers(new, reverse=True) for s in new.predecessors(): for l in s.successors().intersection(new.successors()): l.predecessors().remove(s) s.successors().remove(l) s.successors().add(new) for l in new.successors(): l.predecessors().add(new)
(pushed as branch
u/cheuberg/asy/mutable-poset-add
)
Merged and cross-reviewed....ok.
MutablePoset.remove
: the loop over all (not necessarily direct) successors via the depth first search iterator seems to be rather inefficient, especially if the poset is large. I propose an alternative based on the order relation and not based on the data structure:for upper in shell.successors(): upper.predecessors().remove(shell) for lower in shell.predecessors(): lower.successors().remove(shell) for upper in shell.successors(): if not any(s <= upper for s in lower.successors()): lower.successors().add(upper) upper.predecessors().add(lower)
(pushed as branch
u/cheuberg/asy/mutable-poset-remove
)
This needs comparisons of the elements, but one of the main ideas of this data structure is that comparisions are only needed for inserting an element into the poset and none needed once it is inside. Thus I am for keeping the current solution. However, I am fine with introducing (now or at any point later) an algorithm option which makes it possible to select different removing algorithms depending on the situation.
MutablePoset.remove
,MutablePoset.discard
: add "see also blocks", but also an explanation of the difference betweendiscard
andremove
. I guess that both methods are available due to some compatibility concern (in that case, please add a remark in the code or the docstring). Otherwise, I'd suggest removingdiscard
, removing the parameterraise_key_error
and let the user catch the exception.
Python's set has both, remove
and discard
. Thus this mutable poset should have it as well.
Note-block added. Seealso added.
MutablePoset.pop
: removekey=lambda c: -c
from this example as it is not pertinent topop
.
Done.
MutablePoset.pop
: mention that special elements cannot be popped.
Done.
MutablePoset.pop
: IMHO you can remove the first four line (thetry:
block deletingkwargs['include_special']
) because settingkwargs['include_special'] = False
should result in the same result.
Deleted.
MutablePoset.union
: The doctestP.union(P, Q, Q, P)
neither fits the description "a poset" or "an iterable of future elements".
Rewritten INPUT-block
MutablePoset.union
: the word "union" sounds symmetric, however, due to keys and merge functions, it might not be commutative. The note box is not helpful for me.
Note added/changed.
MutablePoset.union
: the TODO box fromunion_update
also applies here.
Copied.
MutablePoset.union_update
: why is the semantics ofother
different w.r.tunion
, but has the same description? It would seem more logical to me ifunion
would simply call copy and then pass its argument toupdate_union
and let the latter function sort out the iterators?
Indeed. Code rewritten.
MutablePoset.difference
andMutablePoset.difference_update
: see comments onunion
andunion_update
Done.
MutablePoset.intersection
andMutablePoset.intersection_update
: see comments onunion
andunion_update
Done.
MutablePoset.intersection_update
: how can theAttributeError
occur? After all,self
is aMutablePoset
, so the methodkeys
will be available unless something very strange happens ...
True. Code simplified.
MutablePoset.merge
: documentation ofreverse
: what is the default direction?
Documented.
MutablePoset.merge
: add doctest forRuntimeError
.
Added.
MutablePoset.merge
: document thatcan_merge
is applied in the sense of the condition of depth first iteration, i.e., oncecan_merge
fails, the successors are no longer tested. This is some kind of monotonicity condition oncan_merge
.
Added note.
MutablePoset.merge
: it should be mentioned somewhere that this (at first sight strange) merge magic is motivated by asymptotic expansions.
Mentioned.
MutablePoset.map
: IMHO the example does alter the keys, because the key was the identity map here.
Example changed.
MutablePoset.mapping
: does the map have to be key preserving as in the methodmap
? Is this method actually needed, see also the recent discussion on inplace vs. non-inplace operations on sage-devel?
Added a note on key-order preservation.
I think having MutablePoset.mapping
is useful (from a ui point of view) since one would not naturally thinks that the copy
method has a parameter for applying a mapping function.
Changed branch from u/dkrenn/asy/mutable-poset to u/cheuberg/asy/mutable-poset
Thank you for your changes. I added three commits. See my remaining comments below.
Replying to @dkrenn:
Replying to @cheuberg:
- this module was written as part of the asymptotic expansion effort. In contrast to the asymptotic expansion, it does not have the "experimental" decorator. I'd feel more comfortable having it, at least until a larger portion of the asymptotic expansions have been merged.
Activated it; it seems (for some (to me) unknown reason) the warning appears now in every doctest and not only once in the file. Thus, deactivated it again; and I am for keeping it this way.
ok.
MutablePosetShell.key
: I am surprised that the key is not cached. I imagine that many comparisons will be needed in the lifetime of aMutablePoset
, and in every case, the property key has to be resolved, which calls the property poset, which callsget_key
of the poset.Now it is cached (see also follow up ticket #19281).
I rather thought about calling key
in __init__
as I guess that the key will be needed at least once in the lifetime of every MutablePosetShell
.
MutablePosetShell._copy_all_linked_
: I do not understand why you testoo == P.oo
: I think thatoo
is an element of the new posetQ
.
oo == P.oo
tests thatQ.oo
is mapped toP.oo
.
wouldn't oo.is_oo
do it without comparing shells of different posets, which might be confusing?
So
oo is Q.oo
would be more interesting?
oo is Q.oo
isFalse
sinceoo
is not inQ
, but just a copy of theoo
inP
with parent-posetQ
.
that would be good to test (and comment on).
Inserting this into
Q
is done in_copy_shells_
.The current test demonstrates that the poset is not used in comparison, so that would rather belong to
.eq
?I do not understand what you mean (but it is already late...).
I mean that shells e
and f
might be equal even if they do belong to different posets; this might be an interesting doctest or example for equality.
MutablePosetShell._search_covers_
: According to Wikipedia, a cover is what is called an upper cover here. This is in contrast to the default behaviour here.
_search_covers_
does not exist anymore (see 27).
This does not solve the problem.
What about renaming the method covers
to lower_covers
(and adapting the docstring slightly, removing "upper " from the one-sentence-description as well as from the definition?) For symmetry, a method upper_covers
would be nice.
MutablePoset.remove
: the loop over all (not necessarily direct) successors via the depth first search iterator seems to be rather inefficient, especially if the poset is large. I propose an alternative based on the order relation and not based on the data structure:for upper in shell.successors(): upper.predecessors().remove(shell) for lower in shell.predecessors(): lower.successors().remove(shell) for upper in shell.successors(): if not any(s <= upper for s in lower.successors()): lower.successors().add(upper) upper.predecessors().add(lower)
(pushed as branch
u/cheuberg/asy/mutable-poset-remove
)This needs comparisons of the elements, but one of the main ideas of this data structure is that comparisions are only needed for inserting an element into the poset and none needed once it is inside. Thus I am for keeping the current solution. However, I am fine with introducing (now or at any point later) an algorithm option which makes it possible to select different removing algorithms depending on the situation.
This should be discussed when more benchmarking results are available. I opened #19300 for that.
MutablePoset.difference
andMutablePoset.difference_update
: see comments onunion
andunion_update
Done.
removed comment on non-commutativity because difference
is non-commutative by definition.
MutablePoset.intersection
andMutablePoset.intersection_update
: see comments onunion
andunion_update
Done.
Remove comment on non-commutativity? merge does not play a role here, and keys might be covered in the previous sentence?
MutablePoset.update_union
: "Due to keys and a merge function... this operation might not be commutative": This method is non-commutative by definition, as self
is changed and other
is not. So perhaps: "left.update_union(right)
" and "right.update_union(left)
might result in different posets"? The same for other update_...
methods where non-commutativity might be surprising.Changed branch from u/cheuberg/asy/mutable-poset to u/dkrenn/asy/mutable-poset
Replying to @cheuberg:
Thank you for your changes. I added three commits. See my remaining comments below.
Cross-review...ok.
MutablePosetShell.key
: I am surprised that the key is not cached. I imagine that many comparisons will be needed in the lifetime of aMutablePoset
, and in every case, the property key has to be resolved, which calls the property poset, which callsget_key
of the poset.Now it is cached (see also follow up ticket #19281).
I rather thought about calling
key
in__init__
as I guess that the key will be needed at least once in the lifetime of everyMutablePosetShell
.
Oh...yes, I agree; changed.
MutablePosetShell._copy_all_linked_
: I do not understand why you testoo == P.oo
: I think thatoo
is an element of the new posetQ
.
oo == P.oo
tests thatQ.oo
is mapped toP.oo
.wouldn't
oo.is_oo
do it without comparing shells of different posets, which might be confusing?
True. Changed.
So
oo is Q.oo
would be more interesting?
oo is Q.oo
isFalse
sinceoo
is not inQ
, but just a copy of theoo
inP
with parent-posetQ
.that would be good to test (and comment on).
Inserted.
Inserting this into
Q
is done in_copy_shells_
.The current test demonstrates that the poset is not used in comparison, so that would rather belong to
.eq
?I do not understand what you mean (but it is already late...).
I mean that shells
e
andf
might be equal even if they do belong to different posets; this might be an interesting doctest or example for equality.
Now I understand what you mean. Inserted a doctest there.
MutablePosetShell._search_covers_
: According to Wikipedia, a cover is what is called an upper cover here. This is in contrast to the default behaviour here.
_search_covers_
does not exist anymore (see 27).This does not solve the problem.
What about renaming the method
covers
tolower_covers
(and adapting the docstring slightly, removing "upper " from the one-sentence-description as well as from the definition?) For symmetry, a methodupper_covers
would be nice.
Good idea; changed and inserted upper_covers
.
MutablePoset.intersection
andMutablePoset.intersection_update
: see comments onunion
andunion_update
Done.
Remove comment on non-commutativity? merge does not play a role here, and keys might be covered in the previous sentence?
Removed.
MutablePoset.update_union
: "Due to keys and a merge function... this operation might not be commutative": This method is non-commutative by definition, asself
is changed andother
is not. So perhaps: "left.update_union(right)
" and "right.update_union(left)
might result in different posets"? The same for otherupdate_...
methods where non-commutativity might be surprising.
Changed.
New commits:
f7bd83a | Trac #17693, comment 43, 7: do caching of key in __init__ |
a554d69 | rac #17693, comment 43, 18: use .is_oo to test for oo in doctest |
3ac7ed1 | rac #17693, comment 43, 18: add a doctest "oo is Q.oo" |
2f675b3 | Trac #17693, comment 43, 18: add a doctest in eq (comparing elements in different posets) |
f064a3b | Trac #17693, comment 43, 22: covers --> lower_covers, upper_covers |
bea925c | Trac #17693, comment 43, 55: remove comment on non-commutativity |
4e73b45 | Trac #17693, comment 43, 63: extend/rewrite non-commutativity note |
Changed branch from u/dkrenn/asy/mutable-poset to u/cheuberg/asy/mutable-poset
Added three final reviewer commits.
Doctests pass, documentation builds, documentation seems to be fine, code seems to be fine.
Replying to @cheuberg:
Added three final reviewer commits.
Thanks; checked.
Doctests pass, documentation builds, documentation seems to be fine, code seems to be fine.
:)
Changed branch from u/cheuberg/asy/mutable-poset to a0b3d7b
The aim of this ticket is to implement a data structure which is to be used within an asymptotic expression (see Meta-Ticket #17601). This mutable poset stores elements together with its successors and predecessors. Those data is updated when a new element is inserted or an element is removed. It offers a couple of efficient routines for manipulations (all of which will be needed for the asymptotic expression).
CC: @behackl @cheuberg @jm58660
Component: asymptotic expansions
Author: Daniel Krenn
Branch/Commit:
a0b3d7b
Reviewer: Benjamin Hackl, Clemens Heuberger
Issue created by migration from https://trac.sagemath.org/ticket/17693