#18055: Improve lookahead in IntegerListsLex
---------------------------------+------------------------
Reporter: nthiery | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.6
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------------+------------------------
Description changed by nthiery:
Old description:
> `IntegerListsLex` uses a depth first search in a prefix tree, with
> lookahead to prune branches.
> The purpose of this ticket is to improve the lookahead algorithm in two
> directions:
>
> - Detect more branches that can be cut.
> - Better time complexity; this probably will involve identifying
> important invariants and caching them.
>
> Example:: even just for n=1000 this is taking a long time:
> {{{
> sage: n = 100
> sage: IntegerListsLex(binomial(n,2)-1, length=n, min_slope=1).list()
> }}}
> The following also take a long time, which should be optimized:
> {{{
> sage: IntegerListsLex(10^100, max_length=1).list()
> sage: IntegerListsLex(499499, length=1000, min_slope=1).list()
> }}}
>
> One could hope that one could reach an
> average complexity roughly linear in `O(log(max_n), max_length)` per
> list generated.
>
> Concrete steps:
>
> - Extend `Envelope` with a function:
> {{{
> def area(k):
> """Return the area under the envelope between `0` and `k`"""
> }}}
>
> This functions should handle the "reverse smoothing" from position
> `k` (so that the envelope satisfies both `min_slope` and `max_slope`
> conditions between `1` and `k`), and have appropriate algorithmic
> and caching so that the overall complexity of computing all
> `area(k)` for `k<=l` is linear in `l`.
>
> - Replace:
> {{{
> def _possible_m(self, m, ...):
> }}}
> by:
> {{{
> def lookahead(self):
> }}}
>
> which shall detect whether `_current_list` has a chance to be a
> prefix of some valid list. Using the above `area` method of the
> envelopes, it should be possible to detect most dead branches.
> Using dichotomy on the area / parts, it should be possible to
> achieve good complexity in most cases.
>
> This method should support `_current_list=[]` as well.
>
> This method should store as much information as relevant to avoid
> later recomputation for lower nodes in the tree. A minima, this
> could possibly return/store a range for the next value, removing the
> need for a separate `_m_interval` method.
>
> - Update `next` accordingly (the logic should be slightly simpler
> thanks to the handling of the empty prefix).
New description:
`IntegerListsLex` uses a depth first search in a prefix tree, with
lookahead to prune branches.
The purpose of this ticket is to improve the lookahead algorithm in two
directions:
- Detect more branches that can be cut.
- Better time complexity; this probably will involve identifying important
invariants and caching them.
Example:: even just for n=1000 this is taking a long time:
{{{
sage: n = 100
sage: IntegerListsLex(binomial(n,2)-1, length=n, min_slope=1).list()
}}}
The following also take a long time, which should be optimized:
{{{
sage: IntegerListsLex(10^100, max_length=1).list()
sage: IntegerListsLex(499499, length=1000, min_slope=1).list()
}}}
One could hope that one could reach an
average complexity roughly linear in `O(log(max_n), max_length)` per
list generated.
Concrete steps:
- Extend `Envelope` with a function:
{{{
def area(k):
"""Return the area under the envelope between `0` and `k`"""
}}}
This functions should handle the "reverse smoothing" from position
`k` (so that the envelope satisfies both `min_slope` and `max_slope`
conditions between `1` and `k`), and have appropriate algorithmic
and caching so that the overall complexity of computing all
`area(k)` for `k<=l` is linear in `l`.
- Replace:
{{{
def _possible_m(self, m, ...):
}}}
by:
{{{
def lookahead(self):
}}}
which shall detect whether `_current_list` has a chance to be a
prefix of some valid list. Using the above `area` method of the
envelopes, it should be possible to detect most dead branches.
Using dichotomy on the area / parts, it should be possible to
achieve good complexity in most cases.
This method should support `_current_list=[]` as well.
This method should store as much information as relevant to avoid
later recomputation for lower nodes in the tree. A minima, this
could possibly return/store a range for the next value, removing the
need for a separate `_m_interval` method.
- Update `next` accordingly (the logic should be slightly simpler
thanks to the handling of the empty prefix).
- Remove `integer_list_old` at the final stage.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/18055#comment:7>
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.
