Menu
▾
▴
Re: [Kdiff3-user] Alignment algorithm improvements! (was: Large set of testdata for alignmenttest)
|
From: Joachim E. <Joa...@gm...> - 2014-08-24 01:21:05
|
<html><head></head><body><div style="font-family: Verdana;font-size: 12.0px;"><div> <div>Hi Maurice,</div> <div> </div> <div>This looks very promising.</div> <div>I also looked into the moveup changes but can't yet tell what implications it might have.</div> <div>But I'll do some tests myself too.</div> <div> </div> <div>Yet I must warn you that I currently find very little time to work on kdiff3.</div> <div> </div> <div>Best regards,</div> <div>Joachim</div> <div> </div> <div> </div> <div> </div> <div> <div name="quote" style="margin:10px 5px 5px 10px; padding: 10px 0 10px 10px; border-left:2px solid #C3D9E5; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"> <div style="margin:0 0 10px 0;"><b>Gesendet:</b> Donnerstag, 21. August 2014 um 02:07 Uhr<br/> <b>Von:</b> "Maurice van der Pot" <gri...@kf...><br/> <b>An:</b> "Joachim Eibl" <Joa...@gm...><br/> <b>Cc:</b> kdi...@li...<br/> <b>Betreff:</b> Alignment algorithm improvements! (was: Large set of testdata for alignmenttest)</div> <div name="quoted-content">On Tue, Aug 19, 2014 at 07:27:35PM +0200, Maurice van der Pot wrote:<br/> > 3) generate test data systematically<br/> > Disadvantage: the data set gets big really quickly if you cover all<br/> > possible combinations of lines, even for small fragments<br/> > 4) generate test data from real-life merges<br/> > Disadvantage: the data gets big even more quickly than with 3,<br/> > because there is a lot of overlap in which merged file tests which<br/> > behaviour of kdiff3 and each file contains many lines that are<br/> > irrelevant to the test<br/> <br/> I went ahead and implemented both 3 and 4. Both scripts are included in<br/> the merge request I created on sourceforge:<br/> <a href="https://sourceforge.net/p/kdiff3/code/merge-requests/2/" target="_blank">https://sourceforge.net/p/kdiff3/code/merge-requests/2/</a><br/> <br/> <br/> This test set was a prerequisite for some improvements on the alignment<br/> algorithm that I have done and which I am pretty excited about!<br/> (see my moveup branch on sourceforge:<br/> <a href="https://sourceforge.net/u/griffon26/kdiff3/ci/moveup/tree/" target="_blank">https://sourceforge.net/u/griffon26/kdiff3/ci/moveup/tree/</a>)<br/> <br/> <br/> The test sets have allowed me to not only catch mistakes I made during<br/> the implementation of the improvements, but also found one or two<br/> deficiencies in the existing code. Once I fixed those the alignment<br/> even improved a little more.<br/> <br/> <br/> The testdata I used was generated with:<br/> generate_testdata_from_permutations.py -r 7 -s 0<br/> <br/> The differences became:<br/> <a href="http://www.kfk4ever.com/~griffon26/alignment_changes_after_moveup.txt" target="_blank">http://www.kfk4ever.com/~griffon26/alignment_changes_after_moveup.txt</a><br/> In this output the actual result is the output of the code with my improvements<br/> (my moveup branch), while 'expected result' is the output of the original code<br/> (my alignmenttest branch).<br/> <br/> I have obviously not checked the results of all test cases, but the<br/> samples I took looked like pure improvements. One example:<br/> <br/> Running test with testdata/permutations/perm_02739_*.txt... NOK<br/> Actual result (written to testdata/permutations/perm_02739_actual_result.txt):<br/> ----------------------------------------------------------------------------------------------<br/> 0 aaa 0 aaa 0 aaa<br/> 1 bbb 1 bbb<br/> 2 ccc 1 ccc<br/> 2 ddd 3 xxxddd 2 ddd<br/> 4 eee<br/> 3 5 3<br/> ----------------------------------------------------------------------------------------------<br/> Expected result:<br/> ----------------------------------------------------------------------------------------------<br/> 0 aaa 0 aaa 0 aaa<br/> 1 bbb 1 bbb<br/> 2 ddd 2 ccc 1 ccc<br/> 3 xxxddd 2 ddd<br/> 4 eee<br/> 3 5 3<br/> ----------------------------------------------------------------------------------------------<br/> <br/> As you can see in the old version ddd in file A was not aligned with ddd in file C.<br/> The new version fixes this.<br/> <br/> I also ran the new code against test data generated from the linux kernel git repo.<br/> I checked a handful of the differences there and they were also either<br/> improvements or neutral changes.<br/> <br/> <br/> Hoping to hear from you soon,<br/> <br/> Maurice.<br/> <br/> --<br/> Maurice van der Pot<br/> <br/> Gnome Planner Developer gri...@kf... <a href="http://live.gnome.org/Planner" target="_blank">http://live.gnome.org/Planner</a><br/> </div> </div> </div> </div></div></body></html> |
