### Re: Near equal partitions.

by ELISHEVA (Prior)
 on Jan 14, 2011 at 04:58 UTC ( #882284=note: print w/replies, xml ) Need Help??

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 ); } } ], }

With regard to the integer/float division performance. Regardless of any raw machine-level differences in integer/double division--which these days are far less pronounced than previously--the cost of Perl math is always dominated by the number of Perl opcodes to perform the calculation, not the raw machine code performance.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Create A New User
Node Status?
node history
Node Type: note [id://882284]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (6)
As of 2020-01-26 20:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The worst excuse I have ever heard is:

Results (110 votes). Check out past polls.

Notices?