Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!ecngs!feeder2.ecngs.de!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Thu, 20 Dec 2012 20:17:04 -0500
From: Dave Angel <d@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:16.0) Gecko/20121011 Thunderbird/16.0.1
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: help with making my code more efficient
References: <bd5ae6b7-2440-42e4-a93c-eb877feebcfe@googlegroups.com>
In-Reply-To: <bd5ae6b7-2440-42e4-a93c-eb877feebcfe@googlegroups.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Precedence: list
Reply-To: d@davea.name
Newsgroups: comp.lang.python
Message-ID: <mailman.1126.1356052648.29569.python-list@python.org>
Lines: 73
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:35252

On 12/20/2012 07:19 PM, Larry.Martell@gmail.com wrote:
> 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:

No, it's not.  This is a fragment of code, without enough clues as to
what else is going.  We can guess, but that's likely to make a mess.

First question is whether this code works exactly correctly?  Are you
only concerned about speed, not fixing features?  As far as I can tell,
the logic that includes the time comparison is bogus.  You don't do
anything there to worry about the value of tup[2], just whether some
item has a nearby time.  Of course, I could misunderstand the spec.

Are you making a global called 'self' ?  That name is by convention only
used in methods to designate the instance object.  What's the attribute
self?

Can cdata have duplicates, and are they significant?  Are you including
the time building that as part of your 2 hour measurement?  Is the list
sorted in any way?

Chances are your performance bottleneck is the doubly-nested loop.  You
have a list comprehension at top-level code, and inside it calls a
function that also loops over the 600,000 items.  So the inner loop gets
executed 360 billion times.  You can cut this down drastically by some
judicious sorting, as well as by having a map of lists, where the map is
keyed by the tool.

>
> # record time for each message matching the specified message for each tool
> messageTimes = {}

You're building a dictionary;  are you actually using the value (1), or
is only the key relevant?  A set is a dict without a value.  But more
importantly, you never look up anything in this dictionary.  So why
isn't it a list?  For that matter, why don't you just use the
messageTimes list?

> 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)]

As the code exists, there's no need to copy the list.  Just do a simple
bind.

>
> 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. 
>
> Can anyone give me some suggestions on speeding this up?
>
> TIA!


-- 

DaveA