1
\$\begingroup\$

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 < message+(24*60*60) and index<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]<frequency:
                    messageFrequency[-1] = frequency
\$\endgroup\$
  • \$\begingroup\$ Can't this just be done directly in SQLite, with a group by and a window function? \$\endgroup\$ – reptilicus Mar 6 '15 at 21:34
  • \$\begingroup\$ The messages are called AISmessages, but I edited that to messages to have less confusion as it isn't really relevant, sorry that i missed that one. I've lated removed the index incrementing. Will update the post with those with the most time using time.time(). In the ultimate script I have shy of 200 million messages on shy of 80000 users - so i'm getting a bit worried when 1000 messages has a running time of 50s. \$\endgroup\$ – bjornasm Mar 8 '15 at 15:10
  • 1
    \$\begingroup\$ I have rolled back Rev 13 → 4. Please read What to do when someone answers. \$\endgroup\$ – 200_success Mar 8 '15 at 18:55
  • \$\begingroup\$ For future reference, please note that we prefer to review code with your real identifiers, rather than generic ones. Please see Why is hypothetical example code off-topic for CR? \$\endgroup\$ – 200_success Mar 8 '15 at 19:00
  • \$\begingroup\$ Thank you for your help. Should I make a new question where I post my own improvements, and ask for further help? \$\endgroup\$ – bjornasm Mar 8 '15 at 19:02
3
\$\begingroup\$

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:

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you again. I got one question regarding the iterator - how should I work with when i have nested loops? Since I will loop all the messages from the i'th element where i is in range 0->N, i cannot find how I would to that. \$\endgroup\$ – bjornasm Mar 6 '15 at 22:18
  • \$\begingroup\$ @bjornasm I'd write a dictionary based solution that should be enough. \$\endgroup\$ – Michele d'Amico Mar 7 '15 at 11:23
  • \$\begingroup\$ @michele-damico How would I implement a dictionary based solution in this case? \$\endgroup\$ – bjornasm Mar 7 '15 at 15:11
  • \$\begingroup\$ @bjornasm I'm little bit confused. Maybe my answer is not clear. I'll edit it to make more explicit, but it already explain how you can do that. \$\endgroup\$ – Michele d'Amico Mar 7 '15 at 20:09
  • \$\begingroup\$ I saw that you had edited it now - I am very grateful for your contribution, it means a lot to me! \$\endgroup\$ – bjornasm Mar 7 '15 at 22:27

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.