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

<pre><code>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)
</code></pre>

<p>(Prints zeroes, as expected.)</p>

CC BY-SA 2.5
2010-09-30T21:54:49.130Z
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.
BCS
CC BY-SA 2.5
2010-09-30T22:11:44.473Z
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$".
Jukka Suomela
CC BY-SA 2.5
2010-09-30T21:27:04.220Z
2010-09-30T21:27:04.220Z
Jukka Suomela
<p>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).</p>

<p>An easy example:</p>

<pre><code>1 @ ~1/2
2 @ ~1/4
3 @ ~1/8

1,2,1,3,1,2,1,1,2,1,3,1,2,1,2,...
</code></pre>

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

<hr>

<p>Edit: in reply to Jukka:</p>

<pre><code>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)
</code></pre>

<p>output (skipping a few that are close to the right frequency):</p>

<pre><code> 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
</code></pre>

<p>average error 8%</p>

CC BY-SA 2.5
2010-09-30T17:47:32.450Z
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?
Jukka Suomela
CC BY-SA 2.5
2010-09-30T18:09:39.757Z
@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?
BCS
CC BY-SA 2.5
2010-09-30T18:49:50.333Z
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.
Jukka Suomela
CC BY-SA 2.5
2010-09-30T20:46:52.220Z
@Jukka: See edit.
BCS
CC BY-SA 2.5
2010-09-30T21:33:51.490Z
Using math and pseudocode might be a better idea than Python here.
Jukka Suomela
CC BY-SA 2.5
2010-09-30T22:33:32.863Z
I don't understand your problem statement. Do the jobs have lengths? What's your objective function?
Warren Schudy
CC BY-SA 2.5
2010-10-01T00:53:36.397Z
@Warren: the objective function is to minimize the variation in intervals between suspensive runs of the same job while holding the average frequency at the given point.
BCS
CC BY-SA 2.5
2010-10-01T21:38:25.530Z
@BCS: can you formulate your objective function mathematically?
Warren Schudy
<ds.algorithms><scheduling>
Event scheduling.
BCS
# Event scheduling.

(Asked by: username_0 on 2010-09-30)

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%

**Tags:** ds.algorithms, scheduling

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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?  
> **username_1**: 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.  
> **username_0**: @Jukka: See edit.  
> **username_1**: Using math and pseudocode might be a better idea than Python here.  
> **username_2**: I don't understand your problem statement. Do the jobs have lengths? What's your objective function?  
> **username_0**: @Warren: the objective function is to minimize the variation in intervals between suspensive runs of the same job while holding the average frequency at the given point.  
> **username_2**: @username_0: can you formulate your objective function mathematically?  

---

## 1 answers

### Answer by username_1 on 2010-09-30. Score: 1

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.)

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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$".  

---

