# Optimizing the performance of a nested for loop over millions of messages from SQLite Query - v2

I've posted and gotten help to optimize my code before here and here. Now I have implemented the following changes, after very helpful advice:

• I have implemented a Dictionary instead of using list when looking into the extracted messages.
• I have implemented index on the userid and unixtime tables in my database.

Both these changes combined has sped up this program a tenfold, but I still need to make it quicker.

I have a very large number (millions) of messages, each labeled with the unixtime it was sent in a SQLite database. Each message has its own userid, for the user that have sent it. I want to know what's the max number of messages that is sent within an 24hr timeslot for each user. The 24hr timeslot is defined as the time from one message to another. So if there are five messages, where the 5th one is sent 24 hours after the first one, 5 is the number I want.

After these changes the query time of my code is small compared to the total runtime of the program, so I think the biggest gains is in optimizing the algorithm itself.

con = lite.connect(databasepath)
messageFrequency = []
start = time.time()
with con:
cur = con.cursor()
#Get all UserID
distincttime = time.time()
cur.execute('SELECT DISTINCT userid FROM MessageType1 limit 100000')
userID = cur.fetchall()
userID = {index:x[0] for index,x in enumerate(userID)}
#For each UserID
for index in range(len(userID)):
messageFrequency.append(0)
#Get all MSG with UserID = UserID sorted by UNIXTIME
cur.execute('SELECT unixtime FROM MessageType1 WHERE userID ='+str(userID[index])+' ORDER BY unixtime asc')
AISmessages = cur.fetchall()
AISmessages = {index:x[0] for index,x in enumerate(AISmessages)}
#Loop through every MSG
for messageIndex in range(len(AISmessages)):
frequency = 0
message = AISmessages[messageIndex]
for nextMessageIndex in range(messageIndex+1, len(AISmessages)):
#Loop through every message that is within 24 hours
nextmessage = AISmessages[nextMessageIndex]
if  nextmessage < message+(86400):
#Count the number of occurences
frequency += 1
else:
break
#Add best benchmark for every message to a list that should be plotted.
if messageFrequency[-1]<frequency:
messageFrequency[-1] = frequency


What I think can be done:

• Instead of looping through every message in the third loop, I can implement some kind of binary-search to find the first message that is 24hours away.

• Instead of looping through every message in the second loop, I can loop through every message that is $x$ seconds/minutes away; but maybe the gain is lost by trying to skip forward $x$ seconds?

When I run with 2000 userID's the total running time is 8.1 seconds, the cumulative time of the innermost loop is 6.9 seconds. Most optimal I will run this code with 80 000 userIDs and 200M messages. I would love other suggestions on what to be done to bettering the performance of this code.