1
\$\begingroup\$

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')
        deltadistincttime = time.time()-distincttime
        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.

\$\endgroup\$
2
\$\begingroup\$

You could save a lot of comparisons if you wouldn't throw away the information where the last comparison ended (at 'break'). What you do is a sort of sliding window: you start at msg[k] and compare at index k+1, k+2,...k+f until the timestamp leaves the 24h range. You do this sequentially, or you could do that with a binary search - the time reduction depends on how big the 'frequency' is on average.

My suggestion to improve deals with the next iteration: instead of comparing at least f-1 values again, do this:

  • drop the last starting point, i.e. frequency -= 1
  • skip all the values k+1...k+f as you have counted them already in the last iteration
  • start comparing at index k+f+1, either sequentially or with binary search. Increment the last value of 'frequency' for each valid comparison.

f in this case is available in 'frequency'. Think of a sliding window where you advance the window by 1 to the right: drop the leftmost and start comparing one after the rightmost element. This should save you a lot of time (the more, the higher the frequency is on average).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ That is a great suggestion actually! Right now I added a binary search, but I really liked the logic behind this one. It makes a lot of sense and it's intuitive. Thank you! \$\endgroup\$ – bjornasm Mar 9 '15 at 13:10

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.