# Changes between Version 7 and Version 10 of Ticket #18055

Ignore:
Timestamp:
04/16/15 02:52:42 (4 years ago)
Comment:

Unmodified
Added
Removed
Modified
• ## Ticket #18055

• Property Dependencies changed from to `#18109`
• ## Ticket #18055 – Description

 v7 The purpose of this ticket is to improve the lookahead algorithm in two directions: - Detect more branches that can be cut. - Detect more (all?) branches that can be cut. - Better time complexity; this probably will involve identifying important invariants and caching them. }}} One could hope that one could reach an average complexity roughly linear in `O(log(max_n), max_length)` per list generated. 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`""" }}} - If we want the floor function to satisfy the `max_slope` constraint, we need to do "reverse smoothing", and the floor function then depends on the interval `[0,...,k)` over which we want to consider it. The same holds for the ceiling function if we want it to satisfy the `min_slope` constraint. Let thus `f_k` and `c_k` be respectively the floor and ceiling functions for the interval `[0,...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`. Let's ignore the constraints on the length and on `n` for now. Then, `f_k` and `c_k` are valid lists. Prove the following remark: - Replace: {{{ def _possible_m(self, m, ...): }}} by: {{{ def lookahead(self): }}} For any `n` between `sum(f_k)` and `sum(c_k)` there exists a valid list of length `k` and sum `n`. 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. Putting back the length and sum constraints, there exists a valid list if and only if the interval `I_k = [sum(f_k), sum(c_k)]` intersects the interval `[min_n, max_n]` for some `k` between `min_length` and `max_length`. - Extend `Envelope` with a method `.sum(k)` which computes `sum(f_k)`. It should have appropriate algorithmic and caching so that the overall time complexity of computing `sum(f_k)` for all `k<=l` is linear in `l`. Trick: store, for each `j`, the smallest `i<=j` such that between `i` and `j` the slope is exactly `max_slope`. The point is that computing the sum of the parts of `f_k` between `i` and `j` is constant time. Use that incrementally to derive quickly `sum(f_k)` from `sum(f_j)` for some `j<=k`. Suggestion for a faster development cycle: experiment with this by extracting the current code for `Envelope` in a separate file. - Use the above characterization and the `.sum(k)` methods to implement a method `IntegerListsLex.is_empty` which terminates with guaranteed result on non degenerate cases. This is essentially what the current `lookahead` method does, but starting from `0` and with guaranteed results thanks to the reverse smoothing. Determine precisely the degenerate cases where `is_empty` may take an arbitrarily long time (something like: the ceiling can be `0` for an arbitrary long time, without a known `limit=0` and `limit_start`). Decide on appropriate metrics to bound tightly the complexity in the other cases (something around `max_length`, `max_n`, `limit_start`). As a side product, we probably want to store for later usage the information of which `n` admit a valid list, as a collection of non overlapping intervals. Then, deciding whether there exists a valid list of sum `n` for a given `n` can be achieved efficiently by dichotomy. - Assuming that `l` is a prefix of a valid list, find out how to determine for which `i` `l+[i]` is still a prefix of a valid list. Potential building block: the choice of a prefix imposes more constraints on the floor and ceiling later on (our former `adapt` method), and we want to keep track of that. Given a prefix `l`, write `f_k(l)` be the list obtained by extending `l` to a list of length `k` using the floor `f_k`, with appropriate forward smoothing. Same for `c_k(l)`. Write `I_k(l) = [sum(f_k(l)), sum(c_k(l))]`. Now, `l` is a prefix of a valid list if one of the `I_k(l)` intersect `[min_sum, max_sum]`. So, while increasing the length of `l` we want to do something like incrementally adapting the sequence of intervals `I_k(l)` to always make sure we stay within one of them. - Use this to reimplement `lookahead(self)` implementing the above, with a guaranteed result and good complexity. And if at all possible a constant time complexity when the constraints are simple (e.g. `floor=0`, ...). 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). - If not implemented elsewhere: let the constructor accept a prefix as input, to start the iteration from there. Derive a `next` method as a side effect. - Remove `integer_list_old` at the final stage.