#17693: mutable poset: a data structure for asymptotic expressions
-------------------------------------+-------------------------------------
Reporter: dkrenn | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.9
Component: asymptotic | Resolution:
expansions | Merged in:
Keywords: asymptotics | Reviewers: Benjamin Hackl,
Authors: Daniel Krenn | Clemens Heuberger
Report Upstream: N/A | Work issues:
Branch: u/cheuberg/asy | Commit:
/mutable-poset | f7bce7e8aff4e25a23b57d1052ff13df302120e5
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by cheuberg):
* status: needs_review => needs_work
* commit: 3b3b2fb607a6fe8b20419170bf935d494af1efca =>
f7bce7e8aff4e25a23b57d1052ff13df302120e5
* reviewer: Benjamin Hackl => Benjamin Hackl, Clemens Heuberger
* milestone: sage-6.5 => sage-6.9
Comment:
Replying to [comment:34 behackl]:
> This concludes my review; [comment:8 cheuberg] is in the process of
reading the code. I'll leave setting this to `positive_review` to him.
I read the documentation and the code. I pushed a few reviewer commits. 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.
1. Please add `.. seealso::` blocks between corresponding methods of shell
and poset as well as between the accessor methods (keys, elements, shells)
2. there is an empty "Introduction" section at the beginning of the module
documentation, the next heading "Example" is on the same level.
3. 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.
4. `MutablePoset.__init__` accepts a list of elements. This could be used
in several doctests (in particular, in the set operations) as an
abbreviation.
5. `MutablePosetShell.__init__`: shall we check that `element is not
None`? Otherwise, handling of special elements would probably be affected.
6. `MutablePosetShell.key`: I do not understand the sentence "The element
is converted by the poset to the key".
7. `MutablePosetShell.key`: I am surprised that the key is not cached. I
imagine that many comparisons will be needed in the lifetime of a
`MutablePoset`, and in every case, the property key has to be resolved,
which calls the property poset, which calls `get_key` of the poset.
8. `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 from `is_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.
9. `MutablePosetShell.__repr__`: The code replicates the behaviour of
`is_null` and `is_oo`. As the `__repr__` method is hardly time critical,
I'd prefer using `is_null` and `is_oo`, here and thus hiding the internal
convention.
10. `MutablePosetShell.le`: the note box could be simplified by
suppressing implementation details and speaking about the special
elements.
11. `MutablePosetShell.le`: `right <= left`: neither `right` nor `left`
are defined here.
12. `MutablePosetShell.le`: the part `if other.element is None` could be
simplified to `return not other.successors()` as `self` is already known
not to be special here.
13. `MutablePosetShell.le`: If this is time critical,
`self._predecessors_` could be used instead of `self.predecessors()`.
14. `MutablePosetShell.eq`: note box, see above.
15. `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.
16. `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.
17. `MutablePosetShell._copy_all_linked_`: the interplay between this
method and `MutablePoset._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.
18. `MutablePosetShell._copy_all_linked_`: I do not understand why you
test `oo == P.oo`: I think that `oo` is an element of the new poset `Q`.
So `oo is Q.oo` would be more interesting? The current test demonstrates
that the poset is not used in comparison, so that would rather belong to
`.eq`?
19. `MutablePosetShell._search_covers_`: what is the role of `self` in
this method? It trivially influences the return value, but what else?
20. `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 if `reverse` is set?
21. `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 and
`sage.combinat.posets.posets.FinitePoset.upper_covers` defines the notion.
22. `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.
23. `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.
24. `MutablePosetShell.covers`: "originate" is somewhat foreign to the
description of the poset.
25. `MutablePosetShell.covers`: "which are at most the given shell":
should that be "which are less than the given shell"?
26. `MutablePosetShell.covers` see comments on
`MutablePosetShell._search_covers_`.
27. `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`)
28. `MutablePosetShell._iter_depth_first_visit_`: document the role of
self in this method (only shells `>=` this shell are visited).
29. `MutablePosetShell.iter_depth_first`: document the role of self in
this method (only shells `>=` this shell are visited).
30. `MutablePosetShell._iter_topological_visit_`: document the role of
self in this method (only shells `<=` this shell are visited, emphasize
the contrast to depth first.).
31. `MutablePosetShell.iter_topological_first`: document the role of self
in this method (only shells `<=` this shell are visited, emphasize the
contrast to depth first.).
32. `MutablePosetShell.iter_topological_sort`, last example: function `C`
is defined, but not used.
33. `MutablePosetShell.merge`: explain what merge is, in particular, that
this is defined when constructing the poset.
34. `MutablePosetShell.merge`: I am surprised that `check=True` leads to a
silent failure instead of an exception and that `poset._merge_ is None`
does not raise an exception. Document and test this behaviour?
35. `MutablePosetShell.merge`: what is the difference between
`poset.remove` and `poset.discard`?
36. `MutablePosetShell.merge`: document that the merge function resulting
in `None` leads to deletion of the element.
37. `MutablePosetShell.merge`: document that the merge function must not
change the position of the element in the poset.
38. `MutablePoset.__init__`: Clarify the role of `key`: in particular,
`key` does not only influence sorting, but that no two elements are
allowed to have the same key.
39. `MutablePoset.__len__`: Clarify that `null` and `oo` are not counted.
40. `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.
41. `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.
42. `MutablePoset.repr`: INPUT section is incomplete.
43. `MutablePoset.repr_full`: INPUT section is incomplete.
44. `MutablePoset.add`: the loop `for reverse in (False, True)` simplifies
in the second iteration: as all pairs of elements `(s, l)` with `new`
covering `s` and `l` covering `new` have already been broken up while
`reverse=False`. Thus it might be more straightforward to do it only once,
not using `reverse` 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`)
45. `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`)
46. `MutablePoset.remove`, `MutablePoset.discard`: add "see also blocks",
but also an explanation of the difference between `discard` and `remove`.
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 removing `discard`, removing the parameter
`raise_key_error` and let the user catch the exception.
47. `MutablePoset.pop`: remove `key=lambda c: -c` from this example as it
is not pertinent to `pop`.
48. `MutablePoset.pop`: mention that special elements cannot be popped.
49. `MutablePoset.pop`: IMHO you can remove the first four line (the
`try:` block deleting `kwargs['include_special']`) because setting
`kwargs['include_special'] = False` should result in the same result.
50. `MutablePoset.union`: The doctest `P.union(P, Q, Q, P)` neither fits
the description "a poset" or "an iterable of future elements".
51. `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.
52. `MutablePoset.union`: the TODO box from `union_update` also applies
here.
53. `MutablePoset.union_update`: why is the semantics of `other` different
w.r.t `union`, but has the same description? It would seem more logical to
me if `union` would simply call copy and then pass its argument to
`update_union` and let the latter function sort out the iterators?
54. `MutablePoset.difference` and `MutablePoset.difference_update`: see
comments on `union` and `union_update`
55. `MutablePoset.intersection` and `MutablePoset.intersection_update`:
see comments on `union` and `union_update`
56. `MutablePoset.intersection_update`: how can the `AttributeError`
occur? After all, `self` is a `MutablePoset`, so the method `keys` will be
available unless something very strange happens ...
57. `MutablePoset.merge`: documentation of `reverse`: what is the default
direction?
58. `MutablePoset.merge`: add doctest for `RuntimeError`.
59. `MutablePoset.merge`: document that `can_merge` is applied in the
sense of the condition of depth first iteration, i.e., once `can_merge`
fails, the successors are no longer tested. This is some kind of
monotonicity condition on `can_merge`.
60. `MutablePoset.merge`: it should be mentioned somewhere that this (at
first sight strange) merge magic is motivated by asymptotic expansions.
61. `MutablePoset.map`: IMHO the example does alter the keys, because the
key was the identity map here.
62. `MutablePoset.mapping`: does the map have to be key preserving as in
the method `map`? Is this method actually needed, see also the recent
discussion on inplace vs. non-inplace operations on sage-devel?
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=8de4188efff6b534e881dbe8e7071f026f47a317
8de4188]||{{{Trac #17693: minor language adjustments}}}||
||[http://git.sagemath.org/sage.git/commit/?id=740852e2897cfb1e4903150f110c8c242ba153f3
740852e]||{{{Trac #17693: command instead of description for short
descriptions}}}||
||[http://git.sagemath.org/sage.git/commit/?id=347656c7dec2fef3ed8f43c5f24e5ade977b35f3
347656c]||{{{Trac #17693: language adjustment: whether instead of if}}}||
||[http://git.sagemath.org/sage.git/commit/?id=4774baac95a8490280253fc3de41a12c896fc6b4
4774baa]||{{{Trac #17693: corrections in documentation}}}||
||[http://git.sagemath.org/sage.git/commit/?id=fe5d2f1dec3f35eeaf2a4e525e4fe3e9807d17a7
fe5d2f1]||{{{Trac #17693: additional doctest}}}||
||[http://git.sagemath.org/sage.git/commit/?id=e4f1fea624a794d32d2e3380a8eb42ee6888af4f
e4f1fea]||{{{Trac #17693: fix indentations and whitespace}}}||
||[http://git.sagemath.org/sage.git/commit/?id=254951dad86ad94fa55c91f3f811497614490493
254951d]||{{{Trac #17693: add keyword in doctest for clarity}}}||
||[http://git.sagemath.org/sage.git/commit/?id=f7bce7e8aff4e25a23b57d1052ff13df302120e5
f7bce7e]||{{{Trac #17693: remove superfluous doctest}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/17693#comment:36>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
