Find the highest frequency of messages inside a time slot of 24 hours 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.

I have code that gives me this frequency, but the problem is that the running time of this is just too large - and I guess thats partly because of my not-optimal code, and too high complexity. How can I optimize this?

    con = lite.connect(databasepath)
    userID = []
    messages = []
    messageFrequency = []
    with con:
        cur = con.cursor()
        #Get all UserID
        cur.execute('SELECT DISTINCT userid FROM MessageType1')
        userID = cur.fetchall()
        userID = [x[0] for x in userID]
        #For each UserID
        for user in userID:
            messageFrequency.append(0)
            #Get all MSG with UserID = UserID sorted by UNIXTIME
            cur.execute('SELECT unixtime FROM MessageType1 WHERE userID ='+str(user)+' ORDER BY unixtime asc')
            Messages = cur.fetchall()
            Messages = [x[0] for x in Messages]
            length = len(Messages)
            #Loop through every MSG
            for message in Messages:
                index = Messages.index(message)
                nextmessage = Messages[index+1]
                frequency = 0
                #Loop through every message that is within 24 hours
                while nextmessage &lt; message+(24*60*60) and index&lt;length-1:
                    #Count the number of occurences
                    frequency += 1
                    index += 1
                    nextmessage = Messages[index]
                #Add best benchmark for every message to a list
                if messageFrequency[-1]&lt;frequency:
                    messageFrequency[-1] = frequency
First of all: python has not native array. 

In other words Message is a list and every time you type Message[n] you will pay O(n) computational cost to execute it. 

The worst case analysis of your code computational complexity is O(n^3) where n is total number of messages. 

Avoid the use of list index in python for cycle and use iterators or dictionary instead. In your case you scan the list item per item so my first try is to use iterator that should give to you an O(n) computational complexity.

Now after took in account that use lists as array in python is the best way to increase computational complexity, we can take a look to the alternatives:


Use list as list by and rewrite the code by use Iterators and itertools
Use dictionary instead lists
Use numpy.array instead lists


numpy.array maybe is little bit overkill approach; in this case iterators are always the best because in your algorithm you scan the message as list, but use dictionary can be implemented without change your algorithm.

The Dictionary way

First of all replace Messages list by a dictionary where keys are the list index. To do it just replace 

Messages = [x[0] for x in Messages]


by

Messages = {index:x[0] for index,x in enumerate(Messages)}


Messages now is a dictionary where access to Messages[k] have an amortized constant cost. So the same syntax that you used to get elements from your list now can be used on dictionary but its cost doesn't depend from the number of messages at all.

The only thing that we must fix now is the cycle that should follow index order (key array are not ordered for standard dictionary). To do it replace the list iteration for message in Messages by a cycle for each index from 0 to len(Messages) and message variable become Messages[index]. In other words instead of for message in Messages: write

for index in range(len(Messages)):
    message = Messages[index]


By that simple trick you algorithm become O(n)... Is it magic? No. Dictionary are amortized O(1) for access, inserting and delete operation and in python are very well optimized because almost everything in python is based on dictionary.

What do you pay by use dictionary is memory and constants. So your next step could be rewrite it by use iterator but just dictionary should decrease execution time drastically. 

Use iterator means change your algorithm deeply and maybe you don't really need it even I think it could be a very good exercise.