http://www.perlmonks.org?node_id=882284

in reply to Near equal partitions.

Yup. Your brain is definitely on fry :-) Think %.

```sub part {
my (\$n, \$m) = @_;
my \$r = \$n%\$m;                  # <==
my @parts = ((\$n-\$r)/\$m) x \$m;  # <==
my \$i=0;
\$parts[\$i++]++ while \$r--;
return @parts;
}

Update: code sample to reflect outcome of Q&A with ikegami.

Using ikegami's elegant list generation, but without risk of floating point rounding errors:

```sub part {
my (\$n, \$m) = @_;
my \$r = \$n%\$m;
my \$q = (\$n-\$r)/\$m; # avoid int(\$n/\$m) to prevent fp rounding errors
return (\$q+1) x \$r, (\$q) x (\$m-\$r);
}

Replies are listed 'Best First'.
Re^2: Near equal partitions.
by ELISHEVA (Prior) on Jan 14, 2011 at 07:17 UTC

The efficiency of ikegami's solution appears to be due to the efficiency of its list generation. The second code sample above using ikegami's list generation + integer division is only marginally slower than ikegami's code. I presume this is due to the 4 vs. 5 ops for int(\$n/\$m) vs. (\$n-\$r)/\$m mentioned in ikegami's explanation of the performance differences between these two expression.

```# using Benchmark::cmpthese(-1, ...) on input (10,3)
# Debian (Etch) Linux, Perl 5.8.8

Rate   syp   buk eli_1 eli_2   ike
syp   146161/s    --  -23%  -50%  -65%  -66%
buk   189150/s   29%    --  -35%  -54%  -56%
eli_1 289616/s   98%   53%    --  -30%  -32%
eli_2 412559/s  182%  118%   42%    --   -3%
ike   425821/s  191%  125%   47%    3%    --

I also note that the comparison results for syp, buk, eli don't seem quite the same as BrowserUK's results. The iterations per second are much higher and the comparison % quite different.

For example,in BrowserUK's results buk is 42% faster than syp, but here only 23%. In BrowserUK's benchmark, buk & eli_1 are roughly comparable (9% difference) and ike is 106% faster than eli. But here, eli_1 is 53% faster than buk and ike is only 47% faster than eli_1.

Any thoughts on why? Differences in Perl implementations? Inputs? Number of iterations? Just noise due to OS or machine differences?

Update: The results do seem dependent on input. Changing the input to (10000,3) makes no real difference in benchmarks, but changing the input to (10000, 9999) results in this benchmark. The ranking is still the same, but the results clearly break into two clusters based on list construction: (syp, buk,eli_1) and (ike,eli_2).

```        Rate    syp    buk  eli_1  eli_2    ike
syp    63.9/s     --   -70%   -89%  -100%  -100%
buk     212/s   231%     --   -62%  -100%  -100%
eli_1   560/s   776%   164%     --   -99%   -99%
eli_2 61265/s 95828% 28846% 10847%     --    -3%
ike   63015/s 98569% 29673% 11160%     3%     --

It is probably because I'm using a 64-bit build? For reference, here is my benchmark code:

```#! perl -slw
use strict;
use Benchmark qw[ cmpthese ];
use POSIX qw(ceil);

sub buk{
my( \$n, \$m ) = @_;
my @parts = (int( \$n / \$m )) x \$m;
\$n -= \$_ for @parts;
my \$i =0;
\$parts[ \$i++ ]++ while \$n--;
return @parts;
}

sub eli {
my (\$n, \$m) = @_;
my \$r = \$n%\$m;                  # <==
my @parts = ((\$n-\$r)/\$m) x \$m;  # <==
my \$i=0;
\$parts[\$i++]++ while \$r--;
return @parts;
}

sub syp {
my (\$n, \$m) = @_;
my @parts;
for(0 .. \$m - 1) {
\$n -= \$parts[\$_] = ceil(\$n / \$m);
\$m -= 1;
}
return @parts;
}

sub ike {
my (\$n, \$m) = @_;
my \$q = int(\$n / \$m);
my \$r = \$n % \$m;
return (\$q+1) x \$r, (\$q) x (\$m-\$r);
}

printf "buk: 97/\$_ [%s]\n", join ' ', buk( 97, \$_ ) for 2 .. 9;
printf "eli: 97/\$_ [%s]\n", join ' ', eli( 97, \$_ ) for 2 .. 9;
printf "syp: 97/\$_ [%s]\n", join ' ', syp( 97, \$_ ) for 2 .. 9;
printf "ike: 97/\$_ [%s]\n", join ' ', ike( 97, \$_ ) for 2 .. 9;

cmpthese -1, {
buk => q[
for my \$n ( 2 .. 100 ) {
for my \$m ( 3 .. 50 ) {
my @n = buk( \$n, \$m );
}
}
],
eli => q[
for my \$n ( 2 .. 100 ) {
for my \$m ( 3 .. 50 ) {
my @n = eli( \$n, \$m );
}
}
],
syp => q[
for my \$n ( 2 .. 100 ) {
for my \$m ( 3 .. 50 ) {
my @n = syp( \$n, \$m );
}
}
],
ike => q[
for my \$n ( 2 .. 100 ) {
for my \$m ( 3 .. 50 ) {
my @n = ike( \$n, \$m );
}
}
],

}