#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 | 4deddbd1a09e0e60273797cb89becdc651325b9c
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by cheuberg):
* status: needs_review => needs_work
Comment:
Thank you for your changes. I added three commits. See my remaining
comments below.
Replying to [comment:39 dkrenn]:
> Replying to [comment:36 cheuberg]:
> > 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.
>
> 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.
> > 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.
>
> 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`.
> > 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`.
>
> `oo == P.oo` tests that `Q.oo` is mapped to ``P.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` is `False` since `oo` is not in `Q`, but just a copy of the
`oo` in `P` with parent-poset `Q`.
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.
> > 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.
>
> `_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.
> > 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`)
>
> 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.
> > 54. `MutablePoset.difference` and `MutablePoset.difference_update`:
see comments on `union` and `union_update`
>
> Done.
removed comment on non-commutativity because `difference` is non-
commutative by definition.
>
> > 55. `MutablePoset.intersection` and
`MutablePoset.intersection_update`: see comments on `union` and
`union_update`
>
> Done.
Remove comment on non-commutativity? merge does not play a role here, and
keys might be covered in the previous sentence?
63. `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.
--
Ticket URL: <http://trac.sagemath.org/ticket/17693#comment:43>
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.
