Opened 4 years ago
Last modified 4 years ago
#18055 new enhancement
Improve lookahead in IntegerListsLex — at Version 7
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 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. 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.
Change History (7)
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)
comment:4 Changed 4 years ago by
- Description modified (diff)
comment:5 follow-up: ↓ 6 Changed 4 years ago by
- Description modified (diff)
comment:6 in reply to: ↑ 5 Changed 4 years ago by
Replying to jdemeyer:
Can we please stop talking about "degenerate cases" without specifying what that means?
This ticket involves some research, which includes in particular defining precisely what "degenerate" is. Until this research is done, we can't do anything but remain vague.
comment:7 Changed 4 years ago by
- Description modified (diff)
Can we please stop talking about "degenerate cases" without specifying what that means?