I've been playing around with the knuth line breaking code and made a
slight refactoring of it. The result is 38% faster for START align,
78% faster for CENTER align and 12% for JUSTIFY align.

Meassured using 'time' command, jdk1.4.2_03, -Xmx200000000 and a rough edition of Sherlock Holmes from the the Gutenberg project:


(s=start, c=center, j=justify alignment)

The patch is here:


The performance improvement comes from: - Using -INFINITE_RATIO when there is too little shrink in a line for an element to fit. - Reuse the BestRecords instance instead of creating an instance for each line * for each element. - Using ArrayList instead of LinkedList. - Avoiding the indexOf calls on Paragraph. - Use '*' instead of Math.pow() for calculating demerit. - Split activeList into an array indexed by line and nodes within a line linked together.

These improvements could also be applied to the existing code, so I
think the more interesting point is the quality of the refactoring
job. I guess that I have moved away from a faithful implementation of
Knuth's algorithm, but I think the result is more in line with common
java code.



Reply via email to