Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

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

by mr_mischief (Monsignor)
on Mar 12, 2011 at 20:09 UTC ( #892858=note: print w/replies, xml ) Need Help??


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

I'm not sure if you care where the larger portions end up. My way defers taking the integer portion to avoid the errors. It equally spaces the larger and smaller bins along the ranges array. That makes sense compared to sticking them at the end or the beginning if your intent is to spread out utilization of resources evenly anyway.

Here's some output:

[chris@pineapple ranges-892828]$ perl ranges -M=9999997 -N=1 0 : from 0 to 9999997 (9999998) [chris@pineapple ranges-892828]$ perl ranges -M=9999997 -N=2 0 : from 0 to 4999998 (4999999) 1 : from 4999999 to 9999997 (4999999) [chris@pineapple ranges-892828]$ perl ranges -M=9999997 -N=3 0 : from 0 to 3333331 (3333332) 1 : from 3333332 to 6666664 (3333333) 2 : from 6666665 to 9999997 (3333333) [chris@pineapple ranges-892828]$ perl ranges -M=9999997 -N=4 0 : from 0 to 2499998 (2499999) 1 : from 2499999 to 4999998 (2500000) 2 : from 4999999 to 7499997 (2499999) 3 : from 7499998 to 9999997 (2500000) [chris@pineapple ranges-892828]$ perl ranges -M=9999997 -N=5 0 : from 0 to 1999998 (1999999) 1 : from 1999999 to 3999998 (2000000) 2 : from 3999999 to 5999997 (1999999) 3 : from 5999998 to 7999997 (2000000) 4 : from 7999998 to 9999997 (2000000) [chris@pineapple ranges-892828]$ perl ranges -M=9999997 -N=6 0 : from 0 to 1666665 (1666666) 1 : from 1666666 to 3333331 (1666666) 2 : from 3333332 to 4999998 (1666667) 3 : from 4999999 to 6666664 (1666666) 4 : from 6666665 to 8333330 (1666666) 5 : from 8333331 to 9999997 (1666667) [chris@pineapple ranges-892828]$ perl ranges -M=9999997 -N=7 0 : from 0 to 1428570 (1428571) 1 : from 1428571 to 2857141 (1428571) 2 : from 2857142 to 4285712 (1428571) 3 : from 4285713 to 5714283 (1428571) 4 : from 5714284 to 7142854 (1428571) 5 : from 7142855 to 8571425 (1428571) 6 : from 8571426 to 9999997 (1428572) [chris@pineapple ranges-892828]$ perl ranges -M=9999997 -N=8 0 : from 0 to 1249998 (1249999) 1 : from 1249999 to 2499998 (1250000) 2 : from 2499999 to 3749998 (1250000) 3 : from 3749999 to 4999998 (1250000) 4 : from 4999999 to 6249997 (1249999) 5 : from 6249998 to 7499997 (1250000) 6 : from 7499998 to 8749997 (1250000) 7 : from 8749998 to 9999997 (1250000) [chris@pineapple ranges-892828]$ perl ranges -M=9999997 -N=9 0 : from 0 to 1111109 (1111110) 1 : from 1111110 to 2222220 (1111111) 2 : from 2222221 to 3333331 (1111111) 3 : from 3333332 to 4444442 (1111111) 4 : from 4444443 to 5555553 (1111111) 5 : from 5555554 to 6666664 (1111111) 6 : from 6666665 to 7777775 (1111111) 7 : from 7777776 to 8888886 (1111111) 8 : from 8888887 to 9999997 (1111111)

Here's some output from smaller inputs for sanity checking:

[chris@pineapple ranges-892828]$ perl ranges -M=9 -N=1 0 : from 0 to 9 ( 10) [chris@pineapple ranges-892828]$ perl ranges -M=9 -N=2 0 : from 0 to 4 ( 5) 1 : from 5 to 9 ( 5) [chris@pineapple ranges-892828]$ perl ranges -M=9 -N=3 0 : from 0 to 2 ( 3) 1 : from 3 to 5 ( 3) 2 : from 6 to 9 ( 4) [chris@pineapple ranges-892828]$ perl ranges -M=9 -N=4 0 : from 0 to 1 ( 2) 1 : from 2 to 4 ( 3) 2 : from 5 to 6 ( 2) 3 : from 7 to 9 ( 3) [chris@pineapple ranges-892828]$ perl ranges -M=9 -N=5 0 : from 0 to 1 ( 2) 1 : from 2 to 3 ( 2) 2 : from 4 to 5 ( 2) 3 : from 6 to 7 ( 2) 4 : from 8 to 9 ( 2) [chris@pineapple ranges-892828]$ perl ranges -M=9 -N=6 0 : from 0 to 0 ( 1) 1 : from 1 to 2 ( 2) 2 : from 3 to 4 ( 2) 3 : from 5 to 5 ( 1) 4 : from 6 to 7 ( 2) 5 : from 8 to 9 ( 2) [chris@pineapple ranges-892828]$ perl ranges -M=4 -N=0 N < 1 makes no sense. [chris@pineapple ranges-892828]$ perl ranges -M=4 -N=1 0 : from 0 to 4 ( 5) [chris@pineapple ranges-892828]$ perl ranges -M=4 -N=2 0 : from 0 to 1 ( 2) 1 : from 2 to 4 ( 3) [chris@pineapple ranges-892828]$ perl ranges -M=4 -N=3 0 : from 0 to 0 ( 1) 1 : from 1 to 2 ( 2) 2 : from 3 to 4 ( 2) [chris@pineapple ranges-892828]$ perl ranges -M=4 -N=4 0 : from 0 to 0 ( 1) 1 : from 1 to 1 ( 1) 2 : from 2 to 2 ( 1) 3 : from 3 to 4 ( 2) [chris@pineapple ranges-892828]$ perl ranges -M=4 -N=5 M must be equal to N or larger than N.

I'm not sure you'd call the code clean or elegant, but it does seem to work.

#! perl -slw use strict; our $N //= 2; our $M //= 1e6; die "N < 1 makes no sense.\n\n" if $N < 1; die "M must be equal to N or larger than N.\n\n" if $M < $N; my $size = ( $M + 1 ) / $N; my @ranges; for ( my $i = 0; $i < $M; $i += $size ) { my ( $j, $k ) = ( int $i, int ($i + $size) ); push @ranges, [ $j, $k - 1, $k - $j ]; } ( printf "%2d : from %7d to %7d (%7d)\n", $_, @{ $ranges[ $_ ] } ) for 0 .. $#ranges; __END__

I chose to use a for loop and lexical variables with small scopes rather than maps. I realize this may translate a little less cleanly to some languages that parallelize maps automatically and eschew iteration. Oh well. It's a small enough task anyway. Do the parallelization when using the ranges to determine targets later. Besides, if making full use of implementation details not present in the language at hand is a necessary consideration, it should have been in the spec. ;-)

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://892858]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (6)
As of 2021-10-26 12:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My first memorable Perl project was:







    Results (90 votes). Check out past polls.

    Notices?