[squeak-dev] [ANN] [Cuis] Cuis 2.1 is available. Lots of cool stuff inside!

Leandro caniglia at dm.uba.ar
Sat Feb 13 15:43:30 UTC 2010


Levente,

Thank you for remarking this. Could you please suggest a reference where 
I can learn more about the O(n+m) algorithm? (Note however that our 
"trick" could also be useful with the fast algorithm because it avoids 
comparing individual words of lines that are common).

/Leandro

Levente Uzonyi wrote:
> On Fri, 12 Feb 2010, Leandro wrote:
>
>>
>> Levente Uzonyi wrote:
>>
>>       You can also get the word based diff using TextDiffBuilder by 
>> subclassing it and overriding #split:. Actually ClassDiffBuilder does 
>> exactly
>>       this, so using ClassDiffBuilder instead of TextDiffBuilder will 
>> give you the expected result.
>>
>>
>> I think that the difference with the implementation Valeria and I did 
>> is that ours switches from lines to words automatically. It also 
>> defines "words"
>> as Smalltalk words, meaning that it understands keyword limits, which 
>> gives better results. The differentiator starts comparing lines, and 
>> if the
>> proportion of line differences isn't too high, then it reutilizes the 
>> work already done (with lines) and refines it to get differences in 
>> between
>> keywords. The refining strategy was crucial for achieving good 
>> performance.
>
> If you subclass ClassDiffBuilder (let's call the subclass 
> KeywordDiffBuilder)
> and implement KeywordDiffBuilder >> #split: just like DifferenceFinder 
> >> #keywordsAndBlanksFrom: you get even better results.
>
> DifferenceFinder has to use such tricks/hacks to have good 
> performance, because it uses the simplest lcs algorithm which requires 
> n*m time and space in all cases, while for practical cases 
> TextDiffBuilder requires O(n+m) time and space.
>
>
> Levente
>
>>
>> Not sure if the full functionality I'm describing here is in the last 
>> Cuis version though.
>>
>> /Leandro
>>
>>
>



More information about the Squeak-dev mailing list