Subject: [boost] [algorithm] Interface for longest_increasing_subsequence (proposal)
From: Curdeius Curdeius (curdeius_at_[hidden])
Date: 2014-08-17 12:54:04
I want to propose a new algorithm to Boost.Algorithm: a well-known longest
<https://en.wikipedia.org/wiki/Longest_increasing_subsequence> (LIS for
Just for a short info: given a sequence like ( 7 )( 2 )( 8 )( 1 )( 3 )( 4
)( 10 )( 6 )( 9 )( 5 ), the result will be a subsequence ( 1 )( 3 )( 4 )( 6
)( 9 ).
The proposed algorithm has O(n log n) time and O(n) complexity, where n -
I have created a pull request https://github.com/boostorg/algorithm/pull/7.
I have however some questions.
I am not sure what should be the exposed interface.
For the moment, I propose (I base it on the existing interface from
- class longest_increasing_subsequence with methods
- *compute_length* (a better name may be needed)
- free function longest_increasing_subsequence_length returning the
length of the LIS and taking as arguments:
- a pair of iterators (first, last)
- or a range
- and (optionally) a comparison predicate
- *free function longest_increasing_subsequence_search taking the same
arguments as _length function and an Output Iterator or a tag.*
- free function make_longest_increasing_subsequence taking a range and
optionally a comparison predicate and returning
corresponding longest_increasing_subsequence object
The problematic part is the
underlined longest_increasing_subsequence_search function and the way in
which I should return the resulting LIS.
I see possibilities like the following:
1. taking an OutputIterator argument:
the best for me, generic and the most flexible solution, but there
is a performance hit as we cannot reserve the memory for the output LIS.
2. returning a container with the subsequence, e.g.
no performance hit with small objects or if the user needs a vector
of values. However, not really generic as the user would be obliged to use
a vector (in the aforementioned example).
3. returning a container with iterators, e.g. std::vector<InputIter>:
good if a container of iterators is acceptable, it has a benefit of
avoiding possibly expensive copies of sequence elements. As 2., not really
4. -taking a container as an argument:
the worst solution in my eyes, there is no way nice way to write
generic code that handles all containers.
I have coded possibilities 1-3.
Thank you in advance for all the comments, corrections etc.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk