Re: [boost] [algorithm] Review Request: edit_distance

Subject: Re: [boost] [algorithm] Review Request: edit_distance
From: Erik Erlandson (eje_at_[hidden])
Date: 2014-05-19 12:09:21

----- Original Message -----
> Marshall will probably be busy for the next few weeks. Have you asked Ron
> about review manager approval?

I have not.  Since I was put onto the O(NP) paper, I've been spending my copious spare time on studying that.  It has been even more damnably hard to get working both correctly *and* fast than the classic O(ND), however I am nearly finished with my experiments there.  

At any rate, I haven't been specifically pushing for review because I thought it would be nice to bring a finished O(NP) back to the table, and for that matter address some of the other feedback I've already had.

> ________________________________
> From: Erik Erlandson
> Sent: 4/14/2014 7:20 PM
> To: boost_at_[hidden]
> Subject: Re: [boost] [algorithm] Review Request: edit_distance
> 
> 
> 
> ----- Original Message -----
> > > > > - Have you looked at the supposedly better algorithm "An O(NP)
> > > > > Sequence Comparison Algorithm" by Sun Wu, Udi Manber, and Gene
> > > > > Myers ?
> >
> > >
> > > I've been doing more cross-testing and benchmarking against the current
> > > O(ND)
> > > version.   The latest O(NP) prototype is passing randomized cross-testing
> > > and is now about 25% faster than the O(ND) baseline.
> 
> 
> My latest prototype code based on O(NP) is now running about 35% faster than
> O(ND) in my benchmarking:
> 
> https://github.com/erikerlandson/algorithm/blob/order_np_alg/include/boost/algorithm/sequence/detail/edit_distance.hpp#L355
> 
> 
> >
> > I wrote up a blog post that describes the various ideas I applied to get
> > this
> > result:
> >
> > http://erikerlandson.github.io/blog/2014/02/20/a-bi-directional-variation-of-the-o-np-edit-distance-algorithm/
> 
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
> 
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>