# Choose random instants in a day with a low memory footprint

I'm looking for a way to plan a list of X events at the start of the day...

## What I did before:

At 02:00 every day, choose X timestamps from "now" to 01:59 the next day. That worked well but I had to "remember" X timestamps

## What I did to optimize:

Each day, create a counter events_planned = X Each second, in the loop, make the event if random(0, seconds_left_before_0200) <= events_planned

If the event was made, remove 1 from events_planned

It seems to be working well, but when you graph the number of events in a day, you get

As you can see, each time we approch 02:00, more events are created (And that's not a single occurence)

## Minimal exemple:

import time
import random

def planifie():
now = int(time.time())
this_day = now - (now % 86400)
seconds_left = 86400 - (now - this_day)
multiplicator = round(seconds_left / 86400, 5) # In case we restarted, and it's not 02:00. That's not used in the graph before
return round(getPref("events_per_day") * multiplicator)

def mainloop():
planday = 0
is_closed = False
while not is_closed:
now = int(time.time())
this_day = now - (now % 86400)
seconds_left = int(86400 - (now - this_day))
if int(now / 86400) != planday:
planday = int(now / 86400)
events_planned = planifie()

if random.randrange(0, seconds_left) < events_planned:
events_planned -= 1
do_event()
time.sleep(1)

def do_event(): #Dummy def for do_event()
print("Ping")

def getPref(_): # Dummy def for getpref, as it is only used in planifie(). We will assume 20 000 events a day
return 20000
mainloop()


(The code is much more complicated than that, so if you might need it in full, here is planifie() and here is mainloop())

• I would just generate X random timestamps in the time range you desire. You then sort them, execute them one after the other and each time sleep till the next event is due (which could even be a negative delta due to clock issues but that's not a problem for the algorithm). – usr Jul 5 '17 at 15:19
• @usr That's the first paragraph in my answer. But it means I have to strore all of this timestamps, and it consume memory... – WayToDoor Jul 5 '17 at 15:56
• How many points will there be? – usr Jul 5 '17 at 19:50
• @usr It's user defined, there can be up to 2500 "accounts", at maximum 400 events per account. So our worst case senario is 1000000 events per day. Not something i'd like to store in memory ^^ – WayToDoor Jul 5 '17 at 22:03
• Should be ~4MB of data. Is that for all uses combined? Should fit into memory. Is it feasible to store this to some cheap database and every 5 minutes load the next 5 minutes from it to cache? 1M numbers might be hard to keep around for a long time but it should be very fast to handle them just once. – usr Jul 8 '17 at 9:03

### 1. Review

1. There's a lot of repetition, especially of the number 86400. This can be avoided by defining a global constant, for example:

_DAY_SECONDS = 24 * 60 * 60  # Seconds in a day.


or alternatively:

import datetime
_DAY_SECONDS = datetime.timedelta(1).total_seconds()


and then in mainloop:

day, partday = divmod(int(time.time()), _DAY_SECONDS)
seconds_left = _DAY_SECONDS - partday
if day != planday:
planday = day
events_planned = round(getPref('events_per_day') * seconds_left
/ _DAY_SECONDS)


(This avoids the need for the function planifie.)

2. If time.time happens to return a number less than 86,400 (perhaps because the computer's clock has not been set correctly) then events_planned will not get set on the first loop. It's better to ensure that the initial value of planday can never equal day, for example by initializing planday to None.

### 2. The problem

The chance of emitting an event on each loop is events_planned / seconds_left. This would be correct if there each loop iteration took exactly one second. But that's not the case — each loop iteration takes more than a second. That's because (i) some time is taken by do_event (on the iterations where there is an event); (ii) sleep(1) generally takes a little more than 1 second because of the granularity of operating system scheduler, and (iii) as it says in the specification of the sleep function,

The suspension time may be longer than requested due to the scheduling of other activity by the system.

So each loop takes more than a second, but emits events based on the probability of an event occurring in a period of exactly one second. So there is a small but systematic deficit in the number of emitted events, leading to a rush to catch up at the end.

To have a fair schedule, you need to measure the time actually taken by each iteration of the loop, and adjust the probability accordingly, something like this:

planday = None
prev = time.time()
while not is_closed:
now = time.time()
time_passed = now - prev
day, partday = divmod(now, _DAY_SECONDS)
seconds_left = _DAY_SECONDS - partday
if day != planday:
planday = day
events_planned = round(getPref('events_per_day') * seconds_left
/ _DAY_SECONDS)
if random.random() < events_planned * time_passed / seconds_left:
events_planned -= 1
do_event()
time.sleep(1)


(Note that this doesn't actually ensure that the exact number of events occur in each day — an unlucky scheduling of the last sleep of the day could cause some events to be dropped. But the code in the post has the same problem, and I'm guessing that you don't mind if the number of events per day is short by one or two.)

### 3. Worked example

You expressed some skepticism about this in the comments, so let's take a simple worked example. Suppose we start out with $20$ seconds remaining and $10$ events remaining. Then there should be on average one event every 2 seconds. But let's also suppose that the sleep(1) actually takes 2 seconds.

On the first iteration we emit an event with probability $1\over 2$, and so after 2 seconds we have emitted on average $1\over 2$ an event, so we are 0.5 events behind schedule.

On the second iteration we emit an event with probability $1\over2$ if we emitted an event in the first iteration, or $5\over9$ if we didn't. So after two iterations we have emitted on average $${1\over2}\left(1 + {1\over2}\right) + {1\over2}{5\over9} = {37 \over 36}$$ events, and so we are on average almost 1 event behind schedule.

You can see that in this example, the deficit goes up to start with because although the probability goes up, it doesn't go up fast enough to compensate. Towards the end, the probability catches up, hence the rush to finish.

### 4. Alternative approach

If the number of events is substantially less than the number of seconds in a day, then most of the loop iterations will be pointless — no event happens and the program just goes to sleep again.

An alternative approach is to emit exactly one event in each loop, and then choose how long to sleep until the next event. If events are distributed uniformly at random, then the time to the next event is given by the exponential distribution and this can be sampled by calling random.expovariate.

(The same problem with over-sleeping will arise here, so you would have to compensate for it, for example by measuring the actual time taken by the loop iteration, subtracting the intended iteration time, and holding over any surplus and subtracting it from the time for the next iteration.)

• Thanks for your review. I have a question regarding point number 2. Let's say the loop takes for some reason 1 minute of sleep instread of 1 second (just one time, as if the time.sleep was set to 60.) Wouldn't random.randrange(0, seconds_left) correct it by allowing more events to appear ? – WayToDoor Jul 5 '17 at 12:01
• I mean, it shouldn't stack the "missed" events until it's 02:00, right ? – WayToDoor Jul 5 '17 at 12:02
• @WayToDoor: See updated answer for a worked example. (You could do this kind of analysis yourself, or if you are still not sure, you could easily write a simulation.) – Gareth Rees Jul 5 '17 at 12:18