Matching two lists of dicts, strictly and more loosely

Question

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', 
             ..
             },
            {'stock': 'Google',  
             'last_price': afloat,  
             'some-more': 'value', 
             ..
             }, 
             ...
            ] 

List B looks like this:

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

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)

def adddict(entry, symbol):
    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
            hits.append(adddict(entry, sym))
        except TypeError:
            # if not, try a looser match
            sym = fetch(entry['stock'], symbols, 'name')
            try: 
                hits.append(adddict(entry, sym))
            except TypeError: 
                # try yet another possibility
                sym = fetch(entry['stock'].upper(), symbols, 'symbol')
                try: 
                    hits.append(adddict(entry, sym))
                except TypeError: 
                    # lastly try one of the hardcoded SPECIALS. 
                    sym = fetch(entry['stock'], SPECIALS, 'name')
                    try: 
                        hits.append(adddict(entry, sym))
                    except TypeError: 
                        misses.append(entry['stock'])

    return hits, misses  

def main():
    # load_all loads a pickle, made by some other module
    stoxlist = load_all()  

    # 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?

Please comment.

Answer 1

• 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.
• Possibly remove the comments.

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'])

Answer 2

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.