dmd 1.060 and 2.045 release

[Lionello Lunesu]

On 6-5-2010 22:37, Michel Fortin wrote:
> On 2010-05-05 23:45:50 -0400, Walter Bright <newshound1 at digitalmars.com>
> said:
> 
>> Walter Bright wrote:
>>> Alex Makhotin wrote:
>>>> It takes ~40 seconds 50% load on the dual core processor(CentOS 5.3
>>>> kernel 2.6.32.4), to get the actual error messages about the
>>>> undefined identifier.
>>>
>>> Definitely there's a problem.
>>
>> The problem is the spell checker is O(n*n) on the number of characters
>> in the undefined identifier.
> 
> That's an algorithm that can't scale then.
> 
> Checking the Levenshtein distance for each known identifier within a
> small difference in length would be a better idea. (Clang is said to use
> the Levenshtein distance, it probably does something of the sort.)
> 
> http://en.wikipedia.org/wiki/Levenshtein_distance
> 
and especially this line:

# If we are only interested in the distance if it is smaller than a
threshold k, then it suffices to compute a diagonal stripe of width 2k+1
in the matrix. In this way, the algorithm can be run in O(kl) time,
where l is the length of the shortest string.