Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
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??


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

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.


Comment on Re: Split range 0 to M into N non-overlapping (roughly equal) ranges.
Select or Download Code
Replies are listed 'Best First'.
Re^2: Split range 0 to M into N non-overlapping (roughly equal) ranges.
by BrowserUk (Pope) 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.

Log In?
Username:
Password:

What's my password?
Create A New User
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 studying the Monastery: (8)
As of 2015-07-28 05:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (252 votes), past polls