From: Craig Henderson (cdm.henderson_at_[hidden])
Date: 2002-09-19 03:13:24
"Baptiste Lepilleur" <blepctc_at_[hidden]> wrote in message
> > A brief discussion over the class or function interface has already
> > place on the list. I concluded that the class interface was preferable
> > Baptiste Lepilleur provided a nice justification for it. "it keeps the
> > algorithm interface as simple as possible and mesh very well with
> > STL algorithm. It makes it less clumsy to add functions to extend the
> > interface, and allows
> > for automatic type deduction. It also keep the algorithm apart from
> > coat functions like apply_diff ".
> Actually, I was refering to the templatized function interface !!!
Baptiste, I'm sorry I misunderstood your original post, and mis-representing
> I've done an attempt at converting the algorithm to a template function
> some refactoring to hopefully improve readability). You can get the result
> at: http://gaiacrtn.free.fr/temp/.
> It should convince you of how much simple and
> flexible it makes thing. Feel free to use it as you see fit.
> The inteface look like this:
> template<typename size_type, typename InIt1, typename InIt2, typename
> compute_lcs( InIt1 first_begin,
> InIt1 first_end,
> InIt2 second_begin,
> InIt2 second_end,
> OutIt result );
Thanks for that. I've taken a brief look at it and is very similar to my
(unpublished) function interface.
> size_type need to be explicitly specified. It is the storage type used by
> the intermediate array. To go further, I would replace size_type with a
> used as a 2d-array abstraction. This would solve memory allocation and
> cell size issues.
Not sure I understand this, sorry. "replace size_type with a type used as a
2d-array abstraction"? Do you mean to require that the size_type be large
enough to use as a 2d array, so
typedef short my_lcs_array;
> Input iterators must be random access iterators, as performance penality
> would be to great otherwise (with the current implementation). Looking
> at the code, it seems that it should be possible to implement the main
> using only pre-decrementation on the iterator, lowering the constraint to
> bidirectional iterator.
I have made some significant improvements to the algorithm implementation.
Some bug fixes (!), speed optimisations, processing row,column instead of
column,row and reduced the iterator requirement to bidirectional.
> A test application is provided which show how to reconstruct the original
> input and pinpoint the difference without storing anything other than a
> sequence of change_type.
I like this a lot. Thanks.
> Though, while the interface is generic, the algorithm itself is still a
> way from being all purpose. Memory usage grow very quickly: computing lcs
> two 256 characters string requires 64ko (assuming that can use a byte as
> size_type, I haven't looked at the algorithm closely enough to see if an
> array cell value can be greater than the length of an input sequence).
> Now, what's really need to be done to make this algorithm general purpose
> to implement the array slicing algorithm you talked about. ;-)
Thanks for all you input. I'll incorporate some of you ideas in to my new,
improved algorithm implementation.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk