Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much

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.

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?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://892856]
[holli]: You see, I have a friend whose daughter has been damaged seriously because she wasn't vaccinated against measles. (Her mother being anti-vaxx).
[LanX]: Contrary to Olivia newton John I don't like physical confrontations ...
[LanX]: Oh, you spread measles in your saliva?
[LanX]: ... and why did you bite hos daughter?
[LanX]: *his
[holli]: And this guy was also Anti-Vaxx and I just snapped. I shoed him all over the yard
[james28909]: biting between the legs? now thats my kind of religion.
[holli]: and back into the building, saw him later peeking out of the window looking scared. It was hilarious.
[LanX]: Let's get physical...
[james28909]: wish i could stay and chat. i have an unsuspecting client to give an estimate to. muhhahaha

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (12)
As of 2017-12-13 18:04 GMT
Find Nodes?
    Voting Booth?
    What programming language do you hate the most?

    Results (373 votes). Check out past polls.