Algorithm Help Needed
Guys, 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. So given: foo = 1 bar = 3 I would send four requests, one of which is a 'foo', and the other three are 'bar'. So my requests would look like: foo, bar, bar, bar, foo, bar, bar, bar, ... If I have a case like: foo = 1 bar = 1 qux = 6 I can easily send one foo, followed by a bar, followed by 6 qux: foo bar qux qux qux qux qux qux However, what I need to do is to distribute the requests so that the intervals between instances of a given request are distributed as equally as possible. For example: 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. How can I generalize this for any given set of requests and weights? Is anyone aware of any general literature on this kind of problem? (Sounds like a scheduling algorithm maybe?) Thanks, Bob -- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] http://learn.perl.org/ http://learn.perl.org/first-response
Re: Algorithm Help Needed
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] http://learn.perl.org/ http://learn.perl.org/first-response
Re: Algorithm Help Needed
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 foon=1 and bar = 12 then foon bar foon bar etc... -- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] http://learn.perl.org/ http://learn.perl.org/first-response
Re: Algorithm Help Needed
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 foon=1 and bar = 12 then
foon
bar
foon
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
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] http://learn.perl.org/ http://learn.perl.org/first-response
Re: Algorithm Help Needed
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]
http://learn.perl.org/ http://learn.perl.org/first-response
