Subject: Re: [boost] [algorithm] Review Request: edit_distance
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2014-02-04 06:09:56
Erik Erlandson <eje_at_[hidden]> wrote:
>> > *) Runs of 'equal' dominate the script in most larger-scale applications
>> > of interest. Actual insertions, deletions, etc, are relatively small.
>> I can't agree with that; for me, a common case is where the two inputs
>> are entirely different.
> Something of a tangent, but I'm curious how that works for you. When
> two strings are entirely different, the algorithm cost is O(NxM). On
> larger data, say a million elements, that's terabytes of working data,
> and tera-ops.
This is what the max-cost / max-memory / max-time is useful for. I just
give up and return the "trivial" output.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk