Re: [boost] [algorithm] Review Request: edit_distance
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@lists.boost.org 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/a...
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...
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
----- 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@lists.boost.org 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/a...
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...
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (2)
-
Ahmed Charles -
Erik Erlandson