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

Subject: Re: [boost] [algorithm] Review Request: edit_distance
From: Ahmed Charles (acharles_at_[hidden])
Date: 2014-05-17 19:15:54

Marshall will probably be busy for the next few weeks. Have you asked Ron about review manager approval?
________________________________
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