List performance and CSV

[Stephan]

Hello,

I'm working on a simple project in Python that reads in two csv files
and compares items in one file with items in another for matches. I
read the files in using the csv module, adding each line into a list.
Then I run the comparision on the lists. This works fine, but I'm
curious about performance.

Here's the main part of my code:

######
file1 = open("CustomerL ist.csv")
CustomerList = csv.reader(file 1)
Customers = []

#Read in the contents of the CSV file into memory
for CustomerRecord in CustomerList:
Customers.appen d(CustomerRecor d)

#not shown here: the second file CustomersToMatc h
#is loaded in a similar manner

#loop through each record and find matches on column 2
#breaking out of inner loop when a match is found
for loop1 in range(len(Custo mersToMatch)):
for loop2 in range(len(Custo mers)):
if (CustomersToMat ch[loop1][2] == Customers[loop2][2]) :
CustomersToMatc h[loop1][1] = Customers[loop2][1]
break

######

With this code, it takes roughly 10 minutes on a 2Ghz x86 box to
compare two lists of 20,000 records. Is that good? Out of curiousity,
I tried psyco and saw no difference. Is there a better Python synax to
use?

Thanks,
-Stephan

[jepler@unpythonic.net]

Re: List performance and CSV

You'll probably see a slight speed increase with something like
for a in CustomersToMatc h:
for b in Customers:
if a[2] == b[2]:
a[1] = b[1]
break
But a really fast approach is to use a dictionary or other structure
that turns the inner loop into a fast lookup, not a slow loop through
the 'Customers' list. Preparing the dictionary would look like
custmap = {}
for c in Customers:
k = c[2]
if k in custmap: continue
custmap[k] = c
and the loop to update would look like
for a in customerstomatc h:
try:
a[1] = custmap[a[2]][1]
except KeyError:
continue

(all code is untested)

In "big-O" terms, I believe this changes the complexity from O(m*n) to O(m+n).

Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFDR+1lJd0 1MZaTXX0RAnYbAJ sFCBMFNkC0lCDaM HE7Z93J0W2mYACd FDgJ
qmbGFtWneEStGqj vVsE4W40=
=W4T5
-----END PGP SIGNATURE-----

[Magnus Lycka]

Re: List performance and CSV

jepler@unpython ic.net wrote:[color=blue]
> But a really fast approach is to use a dictionary or other structure
> that turns the inner loop into a fast lookup, not a slow loop through
> the 'Customers' list.[/color]

Another approach is to sort both sequences, loop over
both in one loop and just update the index for the smaller
item. Something like this (below, I'm assuming no duplicates
in the lists, and I don't know if that's true for your [2]):
[color=blue][color=green][color=darkred]
>>> l1 = (1,2,4,6,7,8,9)
>>> l2 = (2,5,6,7,9,10)
>>> i1 = i2 = 0
>>> while 1:[/color][/color][/color]
.... if l1[i1]==l2[i2]:
.... print l1[i1], 'is in both'
.... i1 += 1; i2 += 1
.... elif l1[i1]<l2[i2]:
.... i1 += 1
.... else:
.... i2 += 1
....
2 is in both
6 is in both
7 is in both
9 is in both
Traceback (most recent call last):
File "<stdin>", line 2, in ?
IndexError: tuple index out of range

Unless I'm terribly confused, this will lead to m+n iterations
in the worst case. (Of course, the sort operations are something
like O(n log n) I guess.)

By the way, you might be able to use sets too: How fast is
Set.intersectio n?