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

comment:4 Changed 4 years ago by nthiery

  • Description modified (diff)

comment:5 follow-up: Changed 4 years ago by jdemeyer

  • Description modified (diff)

Can we please stop talking about "degenerate cases" without specifying what that means?

comment:6 in reply to: ↑ 5 Changed 4 years ago by nthiery

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 nthiery

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