Benchmarks for the Perl easy question #2005-2
Chris Charley <charley-UXds4KHJg9RWk0Htik3J/[email protected]> Sat, 26 Feb 2005 16:47:56 +0000 (UTC)
| Newsgroups | gmane.comp.lang.perl.qotw.discuss |
|---|---|
| Message-ID | <[email protected]> |
I benchmarked the different solutions. They are at the end.
This table shows the performance results for a width of 80 characters.
Net % is the sum of per cents divided by 2.
Author % Advantage Over closest Net %
(if top result)
or negative diff. from
fastest
(95 words) (16 words)
----------- -------------- ------------ ---------
Sanderson 142 -30
56
West mod -59 -40
-50
Christer -80 7
-37
Chris -78 -7
-43
Christian -79 -17
-48
West -97 -29
-63
Some of the solutions conserved computer cycles.
1 Sanderson: not checking a possible arrangement if it would result
in trailing blank columns.
2. Christian: limiting the upper limit of columns to test by reducing the
limit to the number of columns that would be needed if the length of every
word was the length of the shortest word on the list.
3. Christer: if the line length exceeds the width while constructing
the output format, retry with the column depth increased by 1.
4. West_mod: the same approach as Sanderson.
I'll email the benchmark program to anyone who asks.
The various solutions are:
A: Increment (or decrement) the number of columns until a fit is found.
Dan Sanderson (incr)
Christian (decr)
R B West (decr)
R B West (decr) (with my 2 modifications)
B: Increment rows per column until the number of columns fit the width.
Chris Charley
Christer
In the Cook Book solution, the column widths are not individually
computed depending on the length of the longest string in each column.
Instead, all the columns are assigned a width determined by the longest
string in the entire dataset.
###---###---###---###---###---###---###---###---###---###---###---###
###---###---###---###---###---###---###---###---###---###---###---###
Dan Sanderson
Fastest solution for large datasets.
Starts with 2 columns. If their width is less than the display
width, increase columns until either one column too many has been
reached to fit the display width, (Then go to the saved previous
columns and print) or, the number of columns equals the number
of words (and print).
For some solution that would require a 4 column output, this
algorithm counting up would perform tests on 2 to 5 columns, 4 tests.
This statement:
next if !defined($lengths[($colcount-1) * $collength]);
avoids testing for widths if the last column is empty (empty colunms
would be: 13, 15, 17-18, 20-23, 25-31, 33-47, 49-94). (See data below
for a 95 word list).
West_modified counts down. Compare the 16 tests it takes for it to
reach
4 columns, (counting from the top), to the 4 tests it takes D
Sanderson's
when counting up.
columns: 95 -- depth: 1
columns: 48 -- depth: 2
columns: 32 -- depth: 3
columns: 24 -- depth: 4
columns: 19 -- depth: 5
columns: 16 -- depth: 6
columns: 14 -- depth: 7
columns: 12 -- depth: 8
columns: 11 -- depth: 9
columns: 10 -- depth: 10
columns: 9 -- depth: 11
columns: 8 -- depth: 12
columns: 7 -- depth: 14
columns: 6 -- depth: 16
columns: 5 -- depth: 19
columns: 4 -- depth: 24
columns: 3 -- depth: 32
columns: 2 -- depth: 48
columns: 1 -- depth: 95
ERRORS:
1. my $collength = int(@strings / $colcount) + @strings % $colcount;
should be: my $collength = int(@strings / $colcount + .999999);
The 'ceiling' of this division should be used to determine $collength.
It appears twice: once in the main loop once in and the print code.
2. $colcount--; where it appears in the if-else decision code in the
main loop.
$colcount = $last_column; instead
Though not an error, the print code catches this, I don't think this
statement is giving the results intended.
For an example, use the test sequence above (for a 95 word list).
With a very wide display width :-) , suppose the right number of
columns is 48. So, the program would perform a test, beginning at 2
columns, progressing up to 48 columns. Then it would progress once
more,
from colcount=48 to colcount=95 - one beyond the desired fit at 48.
Then the program would decrement $colcount to 94 and exit the loop
and do the print statements. But, the last test before a colcount of
95 was with colcount=48, not 94.
$last_column could be set when @last_colwidths is set:
@last_colwidths = (@colwidths);
$last_column = $colcount;
###---###---###---###---###---###---###---###---###---###---###---###
###---###---###---###---###---###---###---###---###---###---###---###
Christian
my $colmax = int( $width / ($minl + 1) );
my $colmin = int( $width / ($maxl + 1) );
$colmax = $colmin = 1 if $colmax < 1;
It is possible to have $colmax >= 1 and $colmin == 0, so that
you will get a division by 0 error at this line:
my $row = int( scalar @$list / $col);
$colmin provides no help. Counting down from colmax,
the loop always exits at the first possible solution. Having
a minimum less than or equal to that number does nothing to save
loop iterations.
These are the lines I would use.
my $colmax = int( $width / ($minl + 1) ) || 1;
$colmax = @list if @list < $colmax;
my $colmin = 1;
Assuming a list of 3 words, with the shortest word length being
3 characters, $colmax would equal 80/4 = 20 maximum columns. But,
3 should be the value for $colmax. That is what the second line does.
###---###---###---###---###---###---###---###---###---###---###---###
###---###---###---###---###---###---###---###---###---###---###---###
Chris
Beginning with 1 row, ads a row at a time, until the number of columns
fit the width.
###---###---###---###---###---###---###---###---###---###---###---###
###---###---###---###---###---###---###---###---###---###---###---###
Christer
Constructs 2 arrays, one with indexes in column order, and one in row
order. If that format doesn't fit the width, adds a row and
reconstructs
the 2 arrays. Repeat until the number of columns fit the width.
###---###---###---###---###---###---###---###---###---###---###---###
###---###---###---###---###---###---###---###---###---###---###---###
R B West
Beginning with 1 word per column, (1 row), decreases the number of
columns by 1 each time through the loop until the number of columns
fit. Does not skip over formats that would include empty columns like
Dan Sanderson does.
###---###---###---###---###---###---###---###---###---###---###---###
###---###---###---###---###---###---###---###---###---###---###---###
Luke
Prints alphabetically in rows instead of columns.
###---###---###---###---###---###---###---###---###---###---###---###
###---###---###---###---###---###---###---###---###---###---###---###
West_modified
Adds the test (below) to eliminate tests on formats with empty columns.
--$columns, next # unless the final column is a non-empty column
unless defined $list[($columns-1) * $col_depth];
Does this test to quit building columns early if columns so far exceed
the width.
last if sum(@colsize, $spacing * (@colsize-1)) > $width;
C:\perlp\qotw\2005_02>perl bench.pl
WIDTH=20 VALUES=95
Rate west c_ster chris west_mod c_tian cookbook dan
west 34.1/s -- -37% -66% -95% -95% -98% -98%
c_ster 54.2/s 59% -- -46% -92% -93% -96% -97%
chris 99.9/s 193% 84% -- -85% -86% -93% -95%
west_mod 662/s 1844% 1122% 563% -- -9% -52% -69%
c_tian 727/s 2034% 1241% 628% 10% -- -47% -65%
cookbook 1371/s 3925% 2429% 1273% 107% 89% -- -35%
dan 2105/s 6080% 3783% 2008% 218% 190% 54% --
WIDTH=80 VALUES=95
Rate west c_ster c_tian chris west_mod dan cookbook
west 34.6/s -- -85% -86% -86% -93% -97% -98%
c_ster 226/s 553% -- -7% -8% -52% -80% -85%
c_tian 242/s 600% 7% -- -1% -48% -79% -84%
chris 245/s 608% 8% 1% -- -48% -78% -83%
west_mod 467/s 1251% 107% 93% 91% -- -59% -68%
dan 1133/s 3176% 401% 368% 363% 142% -- -23%
cookbook 1468/s 4144% 549% 506% 499% 214% 30% --
WIDTH=20 VALUES=16
Rate west chris c_ster west_mod c_tian dan cookbook
west 975/s -- -55% -58% -64% -76% -87% -87%
chris 2152/s 121% -- -7% -21% -47% -71% -72%
c_ster 2319/s 138% 8% -- -15% -43% -69% -69%
west_mod 2731/s 180% 27% 18% -- -32% -63% -64%
c_tian 4045/s 315% 88% 74% 48% -- -45% -47%
dan 7403/s 659% 244% 219% 171% 83% -- -2%
cookbook 7575/s 677% 252% 227% 177% 87% 2% --
WIDTH=80 VALUES=16
Rate west_mod dan west c_tian chris c_ster cookbook
west_mod 2605/s -- -15% -16% -28% -36% -40% -66%
dan 3078/s 18% -- -1% -15% -25% -30% -60%
west 3109/s 19% 1% -- -14% -24% -29% -59%
c_tian 3615/s 39% 17% 16% -- -12% -17% -53%
chris 4087/s 57% 33% 31% 13% -- -7% -47%
c_ster 4373/s 68% 42% 41% 21% 7% -- -43%
cookbook 7670/s 194% 149% 147% 112% 88% 75% --
C:\perlp\qotw\2005_02>