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<n>=1 and bar = 12 then > foo<n> > bar > foo<n> > 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!