Comparing massive lists of dictionaries in python

Question

I never actually thought I'd run into speed-issues with python, but I have. I'm trying to compare really big lists of dictionaries to each other based on the dictionary values. I compare two lists, with the first like so

biglist1=[{transaction:"somevalue", id:"somevalue", date:"somevalue" ...}, {transaction:"somevalue", id:"somevalue", date:"somevalue" ...}, ...]

With "somevalue" standing for a user-generated string, int or decimal. Now, the second list is pretty similar, except the id-values are always empty, as they have not been assigned yet.

biglist2=[{transaction:"somevalue", id:"", date:"somevalue" ...}, {transaction:"somevalue", id:"", date:"somevalue" ...}, ...]

So I want to get a list of the dictionaries in biglist2 that match the dictionaries in biglist1 for all other keys except id.

I've been doing

for item in biglist2:
    for transaction in biglist1:
       if item['transaction'] == transaction['transaction']:
          list_transactionnamematches.append(transaction)

for item in biglist2:
    for transaction in list_transactionnamematches:
       if item['date'] == transaction['date']:
          list_transactionnamematches.append(transaction)

... and so on, not comparing id values, until I get a final list of matches. Since the lists can be really big (around 3000+ items each), this takes quite some time for python to loop through.

I'm guessing this isn't really how this kind of comparison should be done. Any ideas?

Answer 1

What you want to do is to use correct data structures:

1. Create a dictionary of mappings of tuples of other values in the first dictionary to their id.

2. Create two sets of tuples of values in both dictionaries. Then use set operations to get the tuple set you want.

3. Use the dictionary from the point 1 to assign ids to those tuples.

Answer 2

In O(m*n)...

for item in biglist2:
    for transaction in biglist1:
       if (item['transaction'] == transaction['transaction'] &&
           item['date'] == transaction['date'] &&
           item['foo'] == transaction['foo'] ) :

          list_transactionnamematches.append(transaction)

Answer 3

Forgive my rusty python syntax, it's been a while, so consider this partially pseudocode

import operator
biglist1.sort(key=(operator.itemgetter(2),operator.itemgetter(0)))
biglist2.sort(key=(operator.itemgetter(2),operator.itemgetter(0)))
i1=0;
i2=0;
while i1 < len(biglist1) and i2 < len(biglist2):
    if (biglist1[i1]['date'],biglist1[i1]['transaction']) == (biglist2[i2]['date'],biglist2[i2]['transaction']):
        biglist3.append(biglist1[i1])
        i1++
        i2++
    elif (biglist1[i1]['date'],biglist1[i1]['transaction']) < (biglist2[i2]['date'],biglist2[i2]['transaction']):
        i1++
    elif (biglist1[i1]['date'],biglist1[i1]['transaction']) > (biglist2[i2]['date'],biglist2[i2]['transaction']):
        i2++
    else:
        print "this wont happen if i did the tuple comparison correctly"

This sorts both lists into the same order, by (date,transaction). Then it walks through them side by side, stepping through each looking for relatively adjacent matches. It assumes that (date,transaction) is unique, and that I am not completely off my rocker with regards to tuple sorting and comparison.

Answer 4

Index on the fields you want to use for lookup. O(n+m)

matches = []
biglist1_indexed = {}

for item in biglist1:
 biglist1_indexed[(item["transaction"], item["date"])] = item

for item in biglist2:
 if (item["transaction"], item["date"]) in biglist1_indexed:
  matches.append(item)

This is probably thousands of times faster than what you're doing now.

Answer 5

The approach I would probably take to this is to make a very, very lightweight class with one instance variable and one method. The instance variable is a pointer to a dictionary; the method overrides the built-in special method __hash__(self), returning a value calculated from all the values in the dictionary except id.

From there the solution seems fairly obvious: Create two initially empty dictionaries: N and M (for no-matches and matches.) Loop over each list exactly once, and for each of these dictionaries representing a transaction (let's call it a Tx_dict), create an instance of the new class (a Tx_ptr). Then test for an item matching this Tx_ptr in N and M: if there is no matching item in N, insert the current Tx_ptr into N; if there is a matching item in N but no matching item in M, insert the current Tx_ptr into M with the Tx_ptr itself as a key and a list containing the Tx_ptr as the value; if there is a matching item in N and in M, append the current Tx_ptr to the value associated with that key in M.

After you've gone through every item once, your dictionary M will contain pointers to all the transactions which match other transactions, all neatly grouped together into lists for you.

Edit: Oops! Obviously, the correct action if there is a matching Tx_ptr in N but not in M is to insert a key-value pair into M with the current Tx_ptr as the key and as the value, a list of the current Tx_ptr and the Tx_ptr that was already in N.

Answer 6

Have a look at Psyco. Its a Python compiler that can create very fast, optimized machine code from your source.

http://sourceforge.net/projects/psyco/

While this isn't a direct solution to your code's efficiency issues, it could still help speed things up without needing to write any new code. That said, I'd still highly recommend optimizing your code as much as possible AND use Psyco to squeeze as much speed out of it as possible.

Part of their guide specifically talks about using it to speed up list, string, and numeric computation heavy functions.

http://psyco.sourceforge.net/psycoguide/node8.html