Boost logo

Boost :

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

> 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:
> 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
> OutIt>
> size_type
> 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[100];

> 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. ;-)
Yes :-)

> Regards,
> Baptiste.
Thanks for all you input. I'll incorporate some of you ideas in to my new,
improved algorithm implementation.

-- Craig

Boost list run by bdawes at, gregod at, cpdaniel at, john at