Re: Algorithm Help Needed

[Jeff 'japhy' Pinyan]

On Sep 13, Bob Showalter said:


I need help with an algorithm. I'm writing a program that sends a repeated
pattern of requests to a service. Each request has a "weight" that controls
the relative frequency with which I need to send that particular request.

  foo => 1
  bar => 1
  qux => 6


  foo
  qux qux qux
  bar
  qux qux qux

Now I have only intervals of 0 or 1 between successive "qux", instead of an
interval of 2 as in the previous case.

As an extreme example, if I had a dozen requests with a weight of 1 and a
final request with a weight of 12, I would "starve" the highly-weighted
request until the first 12 had been sent.


The extreme cases are the easy ones, though.  What I'd like to see are 
cases like:


  foo => 1
  bar => 2
  qux => 3
  baz => 4
  zip => 5

Once I know what the algorithm's outcome should be for something like 
that, I think I can develop it.


--
Jeff "japhy" Pinyan%  How can we ever be the sold short or
RPI Acacia Brother #734%  the cheated, we who for every service
http://www.perlmonks.org/  %  have long ago been overpaid?
http://princeton.pm.org/   %-- Meister Eckhart

--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
 

Re: Algorithm Help Needed

[Eric Walker]

On Tuesday 13 September 2005 09:55 am, Jeff 'japhy' Pinyan wrote:
> On Sep 13, Bob Showalter said:
> > I need help with an algorithm. I'm writing a program that sends a
> > repeated pattern of requests to a service. Each request has a "weight"
> > that controls the relative frequency with which I need to send that
> > particular request.
> >
> >   foo => 1
> >   bar => 1
> >   qux => 6
> >
> >
> >   foo
> >   qux qux qux
> >   bar
> >   qux qux qux
> >
> > Now I have only intervals of 0 or 1 between successive "qux", instead of
> > an interval of 2 as in the previous case.
> >
> > As an extreme example, if I had a dozen requests with a weight of 1 and a
> > final request with a weight of 12, I would "starve" the highly-weighted
> > request until the first 12 had been sent.
>
> The extreme cases are the easy ones, though.  What I'd like to see are
> cases like:
>
>foo => 1
>bar => 2
>qux => 3
>baz => 4
>zip => 5
>
> Once I know what the algorithm's outcome should be for something like
> that, I think I can develop it.
>
> --
> Jeff "japhy" Pinyan%  How can we ever be the sold short or
> RPI Acacia Brother #734%  the cheated, we who for every service
> http://www.perlmonks.org/  %  have long ago been overpaid?
> http://princeton.pm.org/   %-- Meister Eckhart

yes, how would you want to split zip which is odd..  Also, with your extreme 
case you said you would do all the singles first and do the 12 weighted one 
last. that goes against your primary objective which is to distribute the 
service request evenly . In that case I would expect the one with weight of 
12 to be distributed among the single weighted request..
if foo=1 and bar = 12 then
foo
bar
foo
bar
etc... 



-- 
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
 

Re: Algorithm Help Needed

[Jay Savage]

On 9/13/05, Eric Walker <[EMAIL PROTECTED]> wrote:
> On Tuesday 13 September 2005 09:55 am, Jeff 'japhy' Pinyan wrote:
> > On Sep 13, Bob Showalter said:
> > > I need help with an algorithm. I'm writing a program that sends a
> > > repeated pattern of requests to a service. Each request has a "weight"
> > > that controls the relative frequency with which I need to send that
> > > particular request.
> > >
> > >   foo => 1
> > >   bar => 1
> > >   qux => 6
> > >
> > >
> > >   foo
> > >   qux qux qux
> > >   bar
> > >   qux qux qux
> > >
> > > Now I have only intervals of 0 or 1 between successive "qux", instead of
> > > an interval of 2 as in the previous case.
> > >
> > > As an extreme example, if I had a dozen requests with a weight of 1 and a
> > > final request with a weight of 12, I would "starve" the highly-weighted
> > > request until the first 12 had been sent.
> >
> > The extreme cases are the easy ones, though.  What I'd like to see are
> > cases like:
> >
> >foo => 1
> >bar => 2
> >qux => 3
> >baz => 4
> >zip => 5
> >
> > Once I know what the algorithm's outcome should be for something like
> > that, I think I can develop it.
> >
> > --
> > Jeff "japhy" Pinyan%  How can we ever be the sold short or
> > RPI Acacia Brother #734%  the cheated, we who for every service
> > http://www.perlmonks.org/  %  have long ago been overpaid?
> > http://princeton.pm.org/   %-- Meister Eckhart
> 
> yes, how would you want to split zip which is odd..  Also, with your extreme
> case you said you would do all the singles first and do the 12 weighted one
> last. that goes against your primary objective which is to distribute the
> service request evenly . In that case I would expect the one with weight of
> 12 to be distributed among the single weighted request..
> if foo=1 and bar = 12 then
> foo
> bar
> foo
> bar
> etc...

This sort of thing is unfortunately application specific, and depends
a lot on what your goal is. If you do a web search for wieghted round
robin or load balancing, you'll get a lot of food for thought. If you
really need to do careful scheduling--say for load balancing--you'll
need to take into account not just requests but open connections, and
the (unfortunately C, I think) code in the wikipedia weighted round
robin entry is reasonable.

On the other hand, if all you just need to ensure an *average*
response time over a significant number of iterations, and your goal
is statistical distribution not real-world load managment, randomizing
will serve you just as well and be much easier to implement:

#!/usr/bin/perl

use warnings;
use strict;
use List::Util qw(shuffle);

my %weights = ( 'foo' => 12,
'bar' => 7,
'baz' => 2,
'quux' => 6,
'zip' => 1);

my @a;

while (1) {
while (my($k, $v) = each %weights) {
push(@a, $k) for 1..$v;
}

foreach (shuffle(@a)) {
# do something
}
}

HTH,

-- jay
--
This email and attachment(s): [  ] blogable; [ x ] ask first; [  ]
private and confidential

daggerquill [at] gmail [dot] com
http://www.tuaw.com  http://www.dpguru.com  http://www.engatiki.org

values of β will give rise to dom!

RE: Algorithm Help Needed

[Bob Showalter]

Jeff 'japhy' Pinyan wrote:
> The extreme cases are the easy ones, though.  What I'd like to see are
> cases like:
> 
>foo => 1
>bar => 2
>qux => 3
>baz => 4
>zip => 5
> 
> Once I know what the algorithm's outcome should be for something like
> that, I think I can develop it.

Here's what I've come up with so far, which is extremely simple and seems to
work reasonably well:

1. Compute total weight as sum of individual weights
2. For each item in the list compute an "interval" as (total weight) /
(individual weight)
3. Write an entry for "weight" times, adding "interval" each time

So, for the example above, total weight is 15.

Start with foo: interval = 15 / 1 = 15. We need 1 foo, so:

   foo 15

bar: interval = 15 / 2 = 7.5. We need 2 bar's, so:

   bar 7.5
   bar 15

qux: interval = 15 / 3 = 5. Need 3 qux, so:

   qux 5
   qux 10
   qux 15

Final list is:

   foo 15
   bar 7.5
   bar 15
   qux 5
   qux 10
   qux 15
   baz 3.75
   baz 7.5
   baz 11.25
   baz 15
   zip 3
   zip 6
   zip 9
   zip 12
   zip 15

Now sort the list by column 2, then by column 1:

   zip 3
   baz 3.75
   qux 5
   zip 6
   bar 7.5
   baz 7.5
   zip 9
   qux 10
   baz 11.25
   zip 12
   bar 15
   baz 15
   foo 15
   qux 15
   zip 15

Column 1 becomes the round-robin sequence, with the right number of each
request, and farily evenly distributed.

The sequence starts and ends with a "zip", so I have between 0 and 4 non-zip
entries between pairs of zip's. 6 of every 15 requests should be a zip, so
there should be an average of 1.5 non-zip's between zip's. Maybe I should
could tweak my algorithm to better smooth the distribution of zip's.

-- 
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
 

Re: Algorithm Help Needed

[John W. Krahn]

Jay Savage wrote:
> 
> This sort of thing is unfortunately application specific, and depends
> a lot on what your goal is. If you do a web search for wieghted round
> robin or load balancing, you'll get a lot of food for thought. If you
> really need to do careful scheduling--say for load balancing--you'll
> need to take into account not just requests but open connections, and
> the (unfortunately C, I think) code in the wikipedia weighted round
> robin entry is reasonable.
> 
> On the other hand, if all you just need to ensure an *average*
> response time over a significant number of iterations, and your goal
> is statistical distribution not real-world load managment, randomizing
> will serve you just as well and be much easier to implement:
> 
> #!/usr/bin/perl
> 
> use warnings;
> use strict;
> use List::Util qw(shuffle);
> 
> my %weights = ( 'foo' => 12,
> 'bar' => 7,
> 'baz' => 2,
> 'quux' => 6,
> 'zip' => 1);
> 
> my @a;
> 
> while (1) {
> while (my($k, $v) = each %weights) {
> push(@a, $k) for 1..$v;

Or without the for modifier:

  push @a, ( $k ) x $v;


> }
> 
> foreach (shuffle(@a)) {
> # do something
> }
> }


John
-- 
use Perl;
program
fulfillment

-- 
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]