Changes between Version 2 and Version 3 of Ticket #18055


Ignore:
Timestamp:
04/03/15 05:08:43 (5 years ago)
Author:
nthiery
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #18055 – Description

    v2 v3  
    1919average complexity roughly linear in `O(log(max_n), max_length)` per
    2020list generated.
     21
     22Concrete steps:
     23
     24- Extend `Envelope` with a function:
     25  {{{
     26      def area(k):
     27          """Return the area under the envelope between `0` and `k`"""
     28  }}}
     29
     30  This functions should handle the "reverse smoothing" from position
     31  `k` (so that the envelope satisfies both `min_slope` and `max_slope`
     32  conditions between `1` and `k`), and have appropriate algorithmic
     33  and caching so that the overall complexity of computing all
     34  `area(k)` for `k<=l` is linear in `l`.
     35
     36- Replace:
     37  {{{
     38      def _possible_m(self, m, ...):
     39  }}}
     40  by:
     41  {{{
     42      def lookahead(self):
     43  }}}
     44
     45  which shall detect whether `_current_list` has a chance to be a
     46  prefix of some valid list. Using the above `area` method of the
     47  envelopes, it should be possible to detect most dead branches.
     48
     49  This method should support `_current_list=[]` as well.
     50
     51  This method should store as much information as relevant to avoid
     52  later recomputation for lower nodes in the tree. A minima, this
     53  could possibly return/store a range for the next value, removing the
     54  need for a separate `_m_interval` method.
     55
     56- Update `next` accordingly (the logic should be slightly simpler
     57  thanks to the handling of the empty prefix).