CODEWITHSUNDEEP
python
Larry Martell
Larry Martell

Reputation: 3756

How can I make my code more efficient?

I have a list of tuples that contains a tool_id, a time, and a message. I want to select from this list all the elements where the message matches some string, and all the other elements where the time is within some diff of any matching message for that tool.

Here is how I am currently doing this: 

# record time for each message matching the specified message for each tool 
messageTimes = {} 
for row in cdata:   # tool, time, message 
    if self.message in row[2]: 
        messageTimes[row[0], row[1]] = 1 

# now pull out each message that is within the time diff for each matched message 
# as well as the matched messages themselves 

def determine(tup): 
    if self.message in tup[2]: return True      # matched message 

    for (tool, date_time) in messageTimes: 
        if tool == tup[0]: 
            if abs(date_time-tup[1]) <= tdiff: 
               return True 

    return False 


cdata[:] = [tup for tup in cdata if determine(tup)]

This code works, but it takes way too long to run - e.g. when cdata has 600,000 elements (which is typical for my app) it takes 2 hours for this to run.

This data came from a database. Originally I was getting just the data I wanted using SQL, but that was taking too long also. I was selecting just the messages I wanted, then for each one of those doing another query to get the data within the time diff of each. That was resulting in tens of thousands of queries. So I changed it to pull all the potential matches at once and then process it in python, thinking that would be faster. Maybe I was wrong.

Can anyone give me some suggestions on speeding this up?

Updating my post to show what I did in SQL as was suggested.

What I did in SQL was pretty straightforward. The first query was something like:

SELECT tool, date_time, message 
FROM event_log
WHERE message LIKE '%foo%'
AND other selection criteria

That was fast enough, but it may return 20 or 30 thousand rows. So then I looped through the result set, and for each row ran a query like this (where dt and t are the date_time and tool from a row from the above select):

SELECT date_time, message
FROM event_log
WHERE tool = t 
AND ABS(TIMESTAMPDIFF(SECOND, date_time, dt)) <= timediff

That was taking about an hour.

I also tried doing in one nested query where the inner query selected the rows from my first query, and the outer query selected the time diff rows. That took even longer.

So now I am selecting without the message LIKE '%foo%' clause and I am getting back 600,000 rows and trying to pull out the rows I want from python.

Upvotes: 3

Views: 291

Answers (4)

Larry Martell
Larry Martell

Reputation: 3756

I made 2 more changes and now that 20 minute query is taking 3 minutes:

found = defaultdict(int)
def determine(tup):
    if self.message in tup[3]: return True      # matched message

    times = messageTimes[tup[0]]
    idx = found[tup[0]]
    le = bisect.bisect_right(times, tup[1], idx)
    idx = le
    return (le and tup[1]-times[le-1] <= tdiff) or (le != len(times) and times[le]-tup[1] <= tdiff)

Upvotes: 0

Larry Martell
Larry Martell

Reputation: 3756

I fixed this by changing my code as follows:

-first I made messageTimes a dict of lists keyed by the tool:

messageTimes = defaultdict(list)    # a dict with sorted lists

for row in cdata:   # tool, time, module, message
    if self.message in row[3]:
        messageTimes[row[0]].append(row[1])

-then in the determine function I used bisect:

 def determine(tup):
    if self.message in tup[3]: return True      # matched message

    times = messageTimes[tup[0]]
    le = bisect.bisect_right(times, tup[1])
    ge = bisect.bisect_left(times, tup[1])
    return (le and tup[1]-times[le-1] <= tdiff) or (ge != len(times) and times[ge]-tup[1] <= tdiff)

With these changes the code that was taking over 2 hours took under 20 minutes, and even better, a query that was taking 40 minutes took 8 seconds!

Upvotes: 0

abarnert
abarnert

Reputation: 365627

The way to optimize the SQL is to do it all in one query, instead of iterating over 20K rows and doing another query for each one.

Usually this means you need to add a JOIN, or occasionally a sub-query. And yes, you can JOIN a table to itself, as long as you rename one or both copies. So, something like this:

SELECT el2.date_time, el2.message 
FROM event_log as el1 JOIN event_log as el2
WHERE el1.message LIKE '%foo%'
AND other selection criteria
AND el2.tool = el1.tool
AND ABS(TIMESTAMPDIFF(SECOND, el2.datetime, el1.datetime)) <= el1.timediff

Now, this probably won't be fast enough out of the box, so there are two steps to improve it.

First, look for any columns that obviously need to be indexed. Clearly tool and datetime need simple indices. message may benefit from either a simple index or, if your database has something fancier, maybe something fancier, but given that the initial query was fast enough, you probably don't need to worry about it.

Occasionally, that's sufficient. But usually, you can't guess everything correctly. And there may also be a need to rearrange the order of the queries, etc. So you're going to want to EXPLAIN the query, and look through the steps the DB engine is taking, and see where it's doing a slow iterative lookup when it could be doing a fast index lookup, or where it's iterating over a large collection before a small collection.

Upvotes: 7

Andrew Walker
Andrew Walker

Reputation: 42440

For tabular data, you can't go past the Python pandas library, which contains highly optimised code for queries like this.

Upvotes: 2

Related Questions