Deleting dicts with near-duplicate values from a list of dicts - Python

I want to clean up a list of dicts, according to the following rules:

1) The list of dicts is already sorted, so the earlier dicts are preferred.

2) In the lower dicts, if the ['name'] and ['code'] string values match with the same key values of any dict higher up on the list, and if the absolute value of the difference of the int(['cost']) between those 2 dicts is < 2; then that dict is assumed to be a duplicate of the earlier dict, and is deleted from the list.

Here is one dict from the list of dicts:

{
'name':"ItemName", 
'code':"AAHFGW4S",
'from':"NDLS",
'to':"BCT",
'cost':str(29.95)
 }

What is the best way to delete duplicates like t开发者_如何学编程his?

---

There may be a more pythonic way of doing this but this is the basic pseudocode:

def is_duplicate(a,b):
  if a['name'] == b['name'] and a['cost'] == b['cost'] and abs(int(a['cost']-b['cost'])) < 2:
    return True
  return False

newlist = []
for a in oldlist:
  isdupe = False
  for b in newlist:
    if is_duplicate(a,b):
      isdupe = True
      break
  if not isdupe:
    newlist.append(a)

---

Since you say the cost are integers you can use that:

def neardup( items ):
    forbidden = set()
    for elem in items:
        key = elem['name'], elem['code'], int(elem['cost'])
        if key not in forbidden:
            yield elem
            for diff in (-1,0,1): # add all keys invalidated by this
                key = elem['name'], elem['code'], int(elem['cost'])-diff
                forbidden.add(key)

Here is a less tricky way that really calculates the difference:

from collections import defaultdict
def neardup2( items ):
    # this is a mapping `(name, code) -> [cost1, cost2, ... ]`
    forbidden =  defaultdict(list)
    for elem in items:
        key = elem['name'], elem['code']
        curcost = float(elem['cost'])
        # a item is new if we never saw the key before
        if (key not in forbidden or
              # or if all the known costs differ by more than 2
              all(abs(cost-curcost) >= 2 for cost in forbidden[key])):
            yield elem
            forbidden[key].append(curcost)

Both solutions avoid rescanning the whole list for every item. After all, the cost only gets interesting if (name, code) are equal, so you can use a dictionary to look up all candidates fast.

---

Kind of a convoluted problem but I think something like this would work:

for i, d in enumerate(dictList):
    # iterate through the list of dicts, starting with the first
    for k,v in d.iteritems():
        # for each key-value pair in this dict...
        for d2 in dictList[i:]:
             # check against all of the other dicts "beneath" it
             # eg,
             # if d['name'] == d2['name'] and d['code'] == d2['code']:
             #     --check the cost stuff here--