Opened 4 years ago
Last modified 4 years ago
#18055 new enhancement
Improve lookahead in IntegerListsLex — at Version 3
Reported by: | nthiery | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.6 |
Component: | combinatorics | Keywords: | |
Cc: | bgillespie | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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, in non degenerate cases, 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 bothmin_slope
andmax_slope
conditions between1
andk
), and have appropriate algorithmic and caching so that the overall complexity of computing allarea(k)
fork<=l
is linear inl
.
- 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 abovearea
method of the envelopes, it should be possible to detect most dead branches.
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).
Change History (3)
comment:1 Changed 4 years ago by
- Description modified (diff)
comment:2 Changed 4 years ago by
- Description modified (diff)
comment:3 Changed 4 years ago by
- Description modified (diff)