# Matching two lists of dicts, strictly and more loosely

Two lists of dictionaries. Dicts in A and B can be matched by a particular dict key that may be identical or similar. The result should be a list of the source key from A, the matching key from B, and an additional key from B.

Both lists are constructed using screen-scraping, so you normally don't get to see them (unless you print them explicitly). For clarity though: list A is called stoxlist and looks something like this:

stoxlist = [{'stock': 'Apple',
'last_price': afloat,
'some-more': 'value',
..
},
'last_price': afloat,
'some-more': 'value',
..
},
...
]


List B looks like this:

symbollist = [{'name': 'Apple',  'symbol': 'APPLE'},
...
]


The following does what it should do. Using Python 2.7.

# lookup helpers
def match(this, that):
''' returns True if this loosely matches with that '''
if this.strip('.') in that or this.split()[0] in that:
return True
else:
return False        # this is not necessary, but explicit is better than implicit.

def fetch(name, symbols, key):
''' find name by dict[key] in list of dicts symbols  '''
return next((item for item in symbols if match(name, item[key])), None)

dict = {'source'    : entry['stock'],
'found'     : symbol['name'],
'symbol'    : symbol['symbol']}
return dict

def lookup(stox, symbols):
'''lookup symbol for stock name'''
hits = []
misses = []
for entry in stox:
# try an exact match first
sym = next((item for item in symbols if entry['stock'] == item['name']), None)
try:
# save a hit, if any
except TypeError:
# if not, try a looser match
sym = fetch(entry['stock'], symbols, 'name')
try:
except TypeError:
# try yet another possibility
sym = fetch(entry['stock'].upper(), symbols, 'symbol')
try:
except TypeError:
# lastly try one of the hardcoded SPECIALS.
sym = fetch(entry['stock'], SPECIALS, 'name')
try:
except TypeError:
misses.append(entry['stock'])

return hits, misses

def main():

# get_symlist is a screen-scraper, using BeautifulSoup.
symbollist, nosyms = get_symlist()

hits, misses = lookup(stoxlist, symbollist)


I think try-except makes for better readability than if-elif. But it's four levels deep, which is not pretty.

There are four full iterations over list B (symbols) for every entry in list A (stox). That's not pretty either. Yet I can't think of any better way, because it is necessary to first try an == on all items in B, then a looser match on all items in B, and so on.

I'm not really bothered by performance yet. The lists aren't big, less than 100 items each. But perhaps it could all be done much more efficiently/elegantly/Pythonically if I chose a different data structure than list of dicts?

• Exceptions can be faster and slower than using dict.get.

If you don't care about performance then you pick whichever you prefer. However, if you do care you have to take into account three timings; using get, without an exception, and with an exception. Using get is slower than try without an exception, by about 37.8%. But try with an exception is slower than get, by about 35.7%.

So, you should pick the method on whether there will be a sizeable amount of exceptions, or not. In this case, as you expect upto four times, you should use dict.get.

Here are my timings in Python 3.6.0:

>>> from timeit import timeit
>>> timeit('''\
try:
v = d['key']
except KeyError:
pass
else:
pass
''', 'd = {}')
0.25764639688429725
>>> timeit('''\
try:
v = d['key']
except KeyError:
pass
else:
pass
''', 'd = {"key": "here"}')
0.034827991199023245
>>> timeit('''\
v = d.get('key')
if v is not None:
pass
''', 'd = {}')
0.0920266698828982

• Change match to return, rather than being in the if.

• Move match into fetch. It makes the code easier to read.
• Changing your nested trys to a function that yields the possible symbols, makes the code more DRY, and easier to read.
• Move adddict into lookup.

This makes swapping between try and dict.get simpler if one is faster than the other. And also makes the code a little more dense, whilst still being readable. Personally, I find the code being a bit more dense makes your code more readable. But it's not much of a change from your current code.

This can change your code to:

# lookup helpers
def fetch(name, symbols, key):
''' find name by dict[key] in list of dicts symbols  '''
return next((
item
for item in symbols
if name.strip('.') in item[key]
or name.split()[0] in item[key]
), None)

def methods(entry, symbols):
yield next((item for item in symbols if entry['stock'] == item['name']), None)
yield fetch(entry['stock'], symbols, 'name')
yield fetch(entry['stock'].upper(), symbols, 'symbol')
yield fetch(entry['stock'], SPECIALS, 'name')

def lookup(stox, symbols):
'''lookup symbol for stock name'''
hits = []
misses = []
for entry in stox:
for symbol in methods(entry, symbols):
try:
hits.append({'source': entry['stock'],
'found' : symbol['name'],
'symbol': symbol['symbol']})
break
except TypeError:
continue
else:
misses.append(entry['stock'])


However I don't think this should be done in Python. It looks like your extracting data from your database and filtering it in Python, rather than performing both in SQL. And from my limited knowable of SQL this would be much easier written SQL. Assuming SQL has an equivalent of in.

But if you want to keep with Python, to change your code to use equality, rather than in. This is as it can change your code to have linear time, rather than quadratic. If I were to do this I'd change your code to something like:

def methods(stox, symbols):
methods = [
{i['name']: i for i in symbols},
{i['symbol']: i for i in symbols},
{i['name']: i for i in SPECIALS}
]
def inner(stock):
strip = stock.strip('.')
split = stock.split()[0]
yield methods[0].get(stock)
yield methods[0].get(strip)
yield methods[0].get(split)
yield methods[1].get(strip.upper())
yield methods[1].get(split.upper())
yield methods[2].get(strip)
yield methods[2].get(split)
return inner

def lookup(stox, symbols):
meth = methods(stox, symbols)
hits = []
misses = []
for entry in stox:
for symbol in meth(entry['stock']):
if symbol is not None:
hits.append({'source': entry['stock'],
'found' : symbol['name'],
'symbol': symbol['symbol']})
break
else:
misses.append(entry['stock'])

• Many thanks! I'm not familiar with most of your suggestions, so I'll look into them, which will take some time. As for SQL, I'm not using SQL because I think it's overkill. I'm screen-scraping with BeautifulSoup (bs4) and requests, and I save results in pickles. Small, fast, good enough. Feb 1 '17 at 11:12
• @RolfBly As you're scraping, the parts under the line (SQL, and linear code) aren't going to be too helpful. Before that, I used a generator and for-else, but don't know what else I added that you don't know, so ping me if I missed anything. :) Feb 1 '17 at 11:41
• Unfortunately, using equality doesn't yield all matches, I have to use in. Nevertheless, I learned a lot from trying to grok and visualize your last piece of code. I wasn't too familiar with yieldnor generators, and I had not seen of heard of cascaded yield, inner, closure and late bindings, at all before. So thank you again! Feb 6 '17 at 16:17
• @RolfBly my apologies, I was meant to emphasise that it's unlikely to work in your situation. And I didn't seem to do that. :( I'm glad you learnt thoes things, if you've not come across trampolining, then I would advise a look at that, as it can make visualising generators a bit simpler. I rate this very highly for this You may also be interested in their coroutines extension, too. If it's not in that. But I'm happy I could help, :D Feb 6 '17 at 17:30

Disclaimer: This is posted after careful consideration. It's not an answer to the question, but elaboration on @Peilonrayz' answer. I may be stretching an SO guideline here, but I do believe it may help others, and that it may help others best in this form, i.e. not in a comment. It's way too long for a comment. In a new question/answer, we'd lose context. So here goes.

To me, the most difficult to understand in @Peilonrayz's third piece of code was the def inner.

Specifically, methods() is called with two arguments in meth = methods(stox, symbols). But how can def inner(stock) "know" it's called at all? And with what argument? I found the answer Googling. Via "inner", I found better search terms "closure" and "late binding" If you have better ones, please share.

So I made this to help me visualize what's going on:

def funk(a, b):
def the_funk(c):
yield '{}, {}, {}'.format(a, b, c)

return the_funk

E9 = 'da fonk'
Am7 = 'da whole fonk'
B7 = 'an\' nuttin\' but da fonk'

fonk = funk(E9, Am7)  # is a function
da_fonk = fonk(B7)    # is a generator

for y in da_fonk:
print y


funk is a function that returns a generator. You first name the function (fonk) and give it the arguments it requires (2). You then name the generator (da_fonk), and pass it its argument. It's as if the function, when given a third argument, thinks 'do I have a use for this?', looks inside for an empty placeholder, finds c, and decides 'aha, so it must be for c. That's late binding. Better explanations may well be possibile (feel free to add), but this one works for me.

I think it's called closure because the inner is closed off, it's only accessible if you first name its outer function. In this case, you pass the lists to the function, and then the search key to iterate over the generator. Nifty!

Another thing I had never seen before is the yield cascade. Probably not the accepted jargon - cmiiw again, but that's what it looks like. Again to visualize what's going on:

>>> def y(x):
def z(q):
yield x*q
yield x**q
return z

>>> for i in y(3)(2):
print i

6
9


You just get both yields. So in @Peilonrayz's code, for symbol in meth(entry['stock']): iterates over every yield. If not None is yielded, it breaks out of the inner for and starts on the next entry in the outer for. That is, it tries all methods until it gets a hit.

So some entries iterate 5 times over the symbols list and 2 times over the SPECIALS list before finding a match. In my own code, this was 3 + 1 maximum.

Plus, I had to stick with in, equality just wouldn't do. So I ended up using @Peilonrayz second piece of code.

Now. Rip it to shreds, y'all.

• I'll be honest with you, I've been using these things for years, and only fairly recently learnt their names... Also I'm Peilonrayz not Paylonrayz/Pailonrayz, :P Feb 9 '17 at 22:41
• Name corrected, tx for pointing that out. Feb 11 '17 at 22:27