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 nthiery)

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 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.

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 aschilling

  • Description modified (diff)

comment:2 Changed 4 years ago by aschilling

  • Description modified (diff)

comment:3 Changed 4 years ago by nthiery

  • Description modified (diff)
Note: See TracTickets for help on using tickets.