Il giorno 24/ott/08, alle ore 00:52, Dario Laera ha scritto:
It is clear why long paragraphs make a difference. Why does one- or two-column layout make a large difference? Simply due to the twice larger number of pages? I do not understand the left-aligned case. Is this not just the same as a first-fit layout?Nice questions... I'm trying to understand this behavior too, the first time I've implemented the pruning on prototype was for another reason and I accidentally noticed the performance boost :) About one or two columns, or better, long or short lines: again, I don't know why, maybe it's just because the double number of breaks; I thing I noted is that for the same number of active node with shorter lines the gap between startLine and endLine is wider than with long lines. I don't know if this is meaningful.
I managed to get some graphs and now I'm more convinced that line width matters. I've compared the file left-aligned, single block and single column with the analogous file in two columns but with nearly half of its words: in other words, they produce in the final layout nearly the same number of breaks. The pruning was deactivated. You can see the graph attached (startLine and endLine refers to the left scale while activeNodeCount to the right scale): with the same number of knuth elements (x axis) the short lines data grows much faster than long lines data.
A really strange thing: is it theoretically possible that the amount of active nodes is greater than the number of knuth elements? As you can see in the graph, for short lines there are >14000 active nodes but only ~7000 knuth elements...