Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
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
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 wandering the Monastery: (5)
As of 2014-10-21 01:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (94 votes), past polls