Boost logo

Boost :

Subject: Re: [boost] [algorithm] Review Request: edit_distance
From: Erik Erlandson (eje_at_[hidden])
Date: 2014-02-21 23:22:22

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

I wrote up a blog post that describes the various ideas I applied to get this result:

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