0
$\begingroup$

Given a set of actions (that are performed at a rate of one action per unit time) where each must be performed at an assigned frequency (assume the frequencies add up so things can work) and at approximately uniform intervals, derive a scheduling function who's execution uses as few a resources as possible (that is the cost of calling the function is to be minimized).

An easy example:

1 @ ~1/2
2 @ ~1/4
3 @ ~1/8

1,2,1,3,1,2,1,1,2,1,3,1,2,1,2,...
  • The highest frequency and the lowest may differ by a factor of 100-1000.
  • The frequencies are approximately exponential distributed, but not exactly and with an arbitrary ratio (e.g. 1.12 or 1.373)
  • The function must generate an infinite sequence but may be repeating or non-repeating.
  • The function should get as close to exact as possible.
  • Real time constraints apply so
    • The function must have a deterministic runtime
    • The function must provide hard (tight) bounds on the intervals between values.

Edit: in reply to Jukka:

minf = 10
base = 1.17724
frq = [int(minf * base**i) for i in range(36)]
print sum(frq)  # prints 20000
seen = dict((i,0) for i in frq)
start  = [(0,a) for a in frq]
at = 1.0
for _ in range(20000):
  step = [((a-at)*b, a, b) for (a, b) in start]
  step.sort()
  seen[step[0][2]] = seen[step[0][2]] + 1
  step[0] = (0, at, step[0][2])
  start = [(a,b) for (_,a,b) in step]
  at = at + 1

for (k,v) in seen.iteritems():
  print "%5d %5d    %g" % (k, v, v-k)

output (skipping a few that are close to the right frequency):

 2180  2130    -50
  261   278    17
 2566  2489    -77
  136   148    12
  307   325    18
  819   834    15
  160   174    14
 1573  1552    -21
  426   449    23
  695   713    18
  188   203    15
 1852  1818    -34
 3021  2898    -123
  591   612    21
  222   239    17
   98   109    11
  362   384    22
  115   127    12
  502   525    23

average error 8%

$\endgroup$
  • $\begingroup$ A trivial solution is that at each point of time, you simply generate an event that has been generated too rarely so far, breaking ties arbitrarily, but I guess you have already considered that. Perhaps you could explain what problems this approach has in your application? $\endgroup$ – Jukka Suomela Sep 30 '10 at 17:47
  • $\begingroup$ @Jukka: Can you prove that it will give reasonable hard bounds on the intervals? To elaborate can you show it will never end up with everything wanting to run right now? $\endgroup$ – BCS Sep 30 '10 at 18:09
  • $\begingroup$ Well, if everything wants to run right now, then you have managed to run everything exactly in the right proportions (if nobody is "ahead", then nobody is "behind", either). You can then reset your counters and repeat; if your algorithm is deterministic, you will produce the same sequence repeatedly. In the large scale, everything should be fine, but I guess you are worried of what might happen in the small scale. $\endgroup$ – Jukka Suomela Sep 30 '10 at 18:49
  • $\begingroup$ @Jukka: See edit. $\endgroup$ – BCS Sep 30 '10 at 20:46
  • 2
    $\begingroup$ I don't understand your problem statement. Do the jobs have lengths? What's your objective function? $\endgroup$ – Warren Schudy Sep 30 '10 at 22:33
1
$\begingroup$

Slightly editing your code, the "trivial" solution that I referred to in my comment would be something like this:

minf = 10
base = 1.17724
frq = [int(minf * base**i) for i in range(36)]
total = sum(frq)
seen = dict((i,0) for i in frq)
for at in range(total):
  step = [(c-at*f/float(total), f, c) for (f, c) in seen.iteritems()]
  step.sort()
  chosenf = step[0][1]
  seen[chosenf] += 1

for (k,v) in seen.iteritems():
  print "%5d %5d    %g" % (k, v, v-k)

(Prints zeroes, as expected.)

$\endgroup$
  • $\begingroup$ I guess I showed the wrong stats. It's not the count of occurrences I care about near as much as the interval between occurrence. The original code beast the modified code by about a factor of 2 in that regard. $\endgroup$ – BCS Sep 30 '10 at 21:54
  • 3
    $\begingroup$ Exactly what would you like to minimise, subject to what constraints? I think you should try to come up with a mathematically precise formulation like "if $a_i$ is the longest interval between consecutive events of type $i$, and $b_i$ is the shortest interval, then I'd like to minimise the maximum of $a_i - b_i$ over all event types $i$". $\endgroup$ – Jukka Suomela Sep 30 '10 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.