Subject: Re: [boost] [algorithm] Review Request: edit_distance
From: Erik Erlandson (eje_at_[hidden])
Date: 2014-04-14 21:20:10
----- 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:
> I wrote up a blog post that describes the various ideas I applied to get this
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk