Welcome to the Monastery PerlMonks

Re: Split range 0 to M into N non-overlapping (roughly equal) ranges.

by ELISHEVA (Prior)
 on Mar 12, 2011 at 19:40 UTC ( #892856=note: print w/replies, xml ) Need Help??

Why not adapt the solution ikegami suggested a few weeks back on the Near equal partitions. thread?

sub ranges_beth2 { my (\$M, \$N) = @_; my \$r = (\$M+1)%\$N; my \$q = (\$M+1-\$r)/\$N; my \$iEnd=0; return [ map { my \$iStart=\$iEnd; [\$iStart, (\$iEnd+=\$_) - 1] } ((\$q+1) x \$r, (\$q) x (\$N-\$r)) ]; }

Sample output

--------------------------- 0 : from 0 to 9999997 (9999998) --------------------------- 0 : from 0 to 4999998 (4999999) 1 : from 4999999 to 9999997 (4999999) --------------------------- 0 : from 0 to 3333332 (3333333) 1 : from 3333333 to 6666665 (3333333) 2 : from 6666666 to 9999997 (3333332) --------------------------- 0 : from 0 to 2499999 (2500000) 1 : from 2500000 to 4999999 (2500000) 2 : from 5000000 to 7499998 (2499999) 3 : from 7499999 to 9999997 (2499999)

It ensures that partitions never differ by more than 1 in size and avoids rounding errors. On benchmark results it is also marginally faster (4-8%) than the code in the OP (actual result varies between runs)

s/iter buk eli_ik buk 1.01 -- -8% eli_ik 0.923 9% -- Rate buk eli_ik buk 1.02/s -- -4% eli_ik 1.06/s 4% --

Benchmark code

use Benchmark qw(cmpthese); sub testRanges { my \$cr=\$_[0]; for my \$M (1..1e2) { for my \$N (1..\$M) { \$cr->(\$M,\$N); } } } cmpthese(10 , { 'buk' => sub { testRanges(\&ranges_buk) } , 'eli_ik' => sub { testRanges(\&ranges_beth2) } } );

Update: added that it avoids rounding errors.

Update: minor revision to account for OP desiring range to go from 0..\$M (\$M+1 values) not 0..(\$M-1), i.e. \$M values.

Replies are listed 'Best First'.
Re^2: Split range 0 to M into N non-overlapping (roughly equal) ranges.
by BrowserUk (Patriarch) on Mar 12, 2011 at 21:10 UTC

I don't find that to be particularly clean. It uses more intermediate variables and terms.

Efficiency isn't a consideration here as this usually precedes the spawning of N threads that each iterate over \$M/\$N elements of data.

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
Domain Nodelet?
Node Status?
node history
Node Type: note [id://892856]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (2)
As of 2023-03-27 00:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Which type of climate do you prefer to live in?

Results (63 votes). Check out past polls.

Notices?