Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Newsgroups: comp.lang.python
Date: Mon, 24 Dec 2012 09:57:34 -0800 (PST)
In-Reply-To: <mailman.1185.1356158853.29569.python-list@python.org>
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=207.66.36.162; posting-account=aFD2wgkAAACT3OnBYoNKQGBzyOZ_PB2h
References: <bd5ae6b7-2440-42e4-a93c-eb877feebcfe@googlegroups.com> <mailman.1126.1356052648.29569.python-list@python.org> <d6aaa5b5-7d21-4018-ba9a-ea354b15b6c5@googlegroups.com> <mailman.1134.1356060700.29569.python-list@python.org> <mailman.1163.1356112649.29569.python-list@python.org> <b334fb0c-0e76-400d-90e4-1ecde1cc2090@googlegroups.com> <mailman.1183.1356146412.29569.python-list@python.org> <81a9e131-3fab-438e-8799-5aa5bd0e1559@googlegroups.com> <mailman.1185.1356158853.29569.python-list@python.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Subject: Re: help with making my code more efficient
From: "Larry.Martell@gmail.com" <Larry.Martell@gmail.com>
To: comp.lang.python@googlegroups.com
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Cc: python-list@python.org, d@davea.name
Precedence: list
Message-ID: <mailman.1261.1356371863.29569.python-list@python.org>
Lines: 200
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:35476

On Friday, December 21, 2012 11:47:10 PM UTC-7, Dave Angel wrote:
> On 12/21/2012 11:47 PM, Larry.Martell@gmail.com wrote:=20
> > On Friday, December 21, 2012 8:19:37 PM UTC-7, Dave Angel wrote:
> >> On 12/21/2012 03:36 PM, Larry.Martell@gmail.com wrote:
> >>
> >>>> <snip=20
> > I think you're misunderstanding what I need to do. I have a set of rows=
 from the database with tool, time, and message. The user has specified a s=
tring and a time threshold. From that set of rows I need to return all the =
rows that contain the user's string and all the other rows that match the t=
ool from the matched rows and have a time within the threshold.=20
> >
> > cdata has all the rows. messageTimes has the times of all the matched m=
essages, keyed by tool. In determine() I don't look though cdata - it gets =
one element from cdata and I see if that should be selected because it eith=
er matches the user's message, or it's within the threshold of one that did=
 match.
> >=20
> > Here's my original code:=20
> >
> > # record time for each message matching the specified message for each =
tool=20
> > messageTimes =3D {}=20
> > for row in cdata:   # tool, time, message =20
> >     if self.message in row[2]: =20
> >         messageTimes[row[0], row[1]] =3D 1=20
> >=20
> > # now pull out each message that is within the time diff for each match=
ed message =20
> > # as well as the matched messages themselves =20
> >
> > def determine(tup): =20
> >     if self.message in tup[2]: return True      # matched message =20
> >=20
> >     for (tool, date_time) in messageTimes: =20
> >         if tool =3D=3D tup[0]: =20
> >             if abs(date_time-tup[1]) <=3D tdiff: =20
> >                return True=20
> >=20
> >     return False =20
> >         =20
> > cdata[:] =3D [tup for tup in cdata if determine(tup)]=20
> >
> > Here's the code now:=20
> >=20
> >=20
> >        # Parse data and make a list of the time for each message matchi=
ng the specified message for each tool=20
> >         messageTimes =3D defaultdict(list)    # a dict with sorted list=
s=20
> >=20
> >         for row in cdata:   # tool, time, message=20
> >             if self.message in row[2]:=20
> >                 messageTimes[row[0]].append(row[1])=20
> >=20
> >         # now pull out each message that is within the time context for=
 each matched message=20
> >         # as well as the matched messages themselves=20
> >=20
> >         # return true is we should keep this message=20
> >         def determine(tup):=20
> >             if self.message in tup[2]: return True     # matched messag=
e
> >             if seconds =3D=3D 0: return False                # no time =
context specified=20
> >=20
> >             times =3D messageTimes[tup[0]]              # get the list =
of matched messages for this tool=20
> >            =20
> >             le =3D bisect.bisect_right(times, tup[1])   # find time les=
s than or equal to tup[1]=20
> >             ge =3D bisect.bisect_left(times, tup[1])    # find time gre=
ater then to equal to tup[1]=20
> >             return (le and tup[1]-times[le-1] <=3D tdiff) or (ge !=3D l=
en(times) and times[ge]-tup[1] <=3D tdiff)=20
> >=20
> >         cdata =3D [tup for tup in cdata if determine(tup)]=20
> >=20
> > In my test case, cdata started with 600k rows, 30k matched the users st=
ring, and a total of 110k needed to be returned (which is what cdata ended =
up with) - the 30k that matched the string, and 80k that were within the ti=
me threshold. =20
> >
> > I think the point you may have missed is the tool - I only return a row=
 if it's the same tool as a matched message and within the threshold.=20
> >=20
> > I hope I've explained this better. Thanks again.  =20
>=20
> That is better, and the point I missed noticing before is that=20
> messageTimes is substantially smaller than cdata;  it's already been=20
> filtered down by looking for self.message in its row[2].  The code was=20
> there, but I didn't relate.  Remember I was bothered that you didn't=20
> look at tup[2] when you were comparing for time-similarity.  Well, you=20
> did that implicitly, since messageTimes was already filtered.  Sorry=20
> about that.=20
>=20
> That also lowers my expectations for improvement ratio, since instead of=
=20
> 600,000 * 600,000, we're talking "only" 600,000 * 30,000, 5% as much. So
> now my expectations are only 4:1 to 10:1.=20
>
> Still, there's room for improvement.  (1) You should only need one
> bisect in determine, and (2) if you remember the last result for each=20
> tool, you could speed that one up some.=20
>
> (1) Instead of getting both and le and a ge, get just one, by searching=
=20
> for tup[1]-tdiff.  Then by comparing that row's value against=20
> tup[1]+tdiff, you can return immediately the boolean, the expression=20
> being about half of the one you've now got.

Dave, I cannot thank you enough. With this change it went from 20 minutes t=
o 10.

> (2) Make a dict of ints, keyed by the tool, and initialized to zero.=20
> Call that dict "found."  Each time you do a bisect, specify a range=20
> starting at found[tool].  Similarly, store the result of the bisect in
> found[tool].  This should gradually restrict the range searched by=20
> bisect, which COULD save some time. It works because everything's sorted.

And with this change it took 3 minutes. WOW!=20

Merry Christmas and Happy New Year!!!

=20
> Naturally, make these changes independently, and time the changes.  In
>=20
> particular, it's possible that #2 will degrade performance instead of
>=20
> improving it.  But #1 should double performance, pretty close.
>=20
>=20
>=20
> I hope these were clear enough.  I don't want to write the changes
>=20
> myself, since with no test data, I could easily make a mess of it.
>=20
> ....
>=20
>=20
>=20
> I can think of other changes which are less likely to make substantial
>=20
> improvement, and which might degrade things.  For one drastic example,
>=20
> instead of any messageTimes storage, you could have ("flags") a list of
>=20
> bool, same size as ctimes, which tracked the state of each line.  You
>=20
> loop through cdata, identifying and marking any line whose tup[2]
>=20
> matches.  And for each match, you scan backwards and forwards till the
>=20
> time gets out of range (in one direction stopping at time-tdiff or 0 or
>=20
> tool change, and in the other direction at time+tdiff or len, or
>=20
> toolchange), marking each one within tdiff.
>=20
>=20
>=20
> Then after one pass through cdata, you can have a very simple list
>=20
> comprehension, something like:
>=20
>=20
>=20
> cdata =3D [tup for index, tup in enumerate(cdata) if flags[index]]
>=20
>=20
>=20
> Will it be faster?  Depends on the number of expected matches (eg.
>=20
> 30,000 out of 300,000 is 10%), and how much data forward and backwards
>=20
> you need to scan.
>=20
> ....
>=20
>=20
>=20
> A very simple difference?  Perhaps using implicit unpacking instead of
>=20
> using tup[0] etc. will be faster.  It'll certainly be easier to read.
>=20
>=20
>=20
> for tool, time, text in cdata:
>=20
>    if self.message in text:
>=20
>        messageTimes[tool]. append(time)
>=20
>=20
>=20
> def determine(tool, time, text):
>=20
>=20
>=20
> and call it with    determine(*tup)