查找Python字典的相似性

Question

我有一个包含一千个项目的Python字典。每个项目本身也是一个字典。我想找一种简单优雅的方法来遍历每个项目，找出并创建模板。

下面是这些字典结构的一个简化示例：

{'id': 1,
 'template': None,
 'height': 80,
 'width': 120,
 'length': 75,
 'weight': 100}

从这个结构中，我想只遍历一次，如果发现1000个项目中有500个的高度和宽度是一样的，就记录下来，这样我就可以根据这些数据构建一个模板，并把模板的ID赋值给'template'。虽然我可以建立一个巨大的参考哈希表，但我希望能有一种更简洁优雅的方法来实现这个目标。

实际的数据大约有30个键，其中有一小部分需要在模板检查时排除。

Answer 1

给定一个字典，里面又包含了字典，叫做 items：

import itertools as it

for (height, width), itemIter in it.groupby (items.values(), lambda x: (x['height'], x['width'])):
    # in list(itemIter) you will find all items with dimensions (height, width)

Answer 2

@eumiro 提出了一个很好的核心思路，就是使用 itertools.groupby() 来把具有相同值的项目分成一组一组的。不过，他没有先用 @Jochen Ritzel 指出的相同关键函数对数据进行排序（这个在文档中也有提到），而且他也没有解决你提到的其他几个想要做的事情。

下面是一个更完整、稍微长一点的回答。它在遍历字典的过程中一次性确定模板并进行分配。为此，首先创建一个排序好的项目列表，然后使用 groupby() 将它们分组，如果每组的数量足够，就创建一个模板，并把它的 ID 分配给每个成员。

inventory = {
    'item1': {'id': 1, 'template': None, 'height': 80, 'width': 120, 'length': 75, 'weight': 100},
    'item2': {'id': 2, 'template': None, 'height': 30, 'width': 40,  'length': 20, 'weight': 20},
    'item3': {'id': 3, 'template': None, 'height': 80, 'width': 100, 'length': 96, 'weight': 150},
    'item4': {'id': 4, 'template': None, 'height': 30, 'width': 40,  'length': 60, 'weight': 75},
    'item5': {'id': 5, 'template': None, 'height': 80, 'width': 100, 'length': 36, 'weight': 33}
}

import itertools as itools

def print_inventory():
    print 'inventory:'
    for key in sorted(inventory.iterkeys()):
        print '  {}: {}'.format(key, inventory[key])

print "-- BEFORE --"
print_inventory()

THRESHOLD = 2
ALLKEYS = ['template', 'height', 'width', 'length', 'weight']
EXCLUDEDKEYS = ['template', 'length', 'weight']
INCLUDEDKEYS = [key for key in ALLKEYS if key not in EXCLUDEDKEYS]

# determines which keys make up a template
sortby = lambda item, keys=INCLUDEDKEYS: tuple(item[key] for key in keys)

templates = {}
templateID = 0
sortedinventory = sorted(inventory.itervalues(), key=sortby)
for templatetuple, similariter in itools.groupby(sortedinventory, sortby):
    similaritems = list(similariter)
    if len(similaritems) >= THRESHOLD:
        # create and assign a template
        templateID += 1
        templates[templateID] = templatetuple # tuple of values of INCLUDEDKEYS
        for item in similaritems:
            item['template'] = templateID
print
print "-- AFTER --"
print_inventory()
print
print 'templates:', templates
print

当我运行这个代码时，输出结果如下：

-- BEFORE --
inventory:
  item1: {'weight': 100, 'height': 80, 'width': 120, 'length': 75, 'template': None, 'id': 1}
  item2: {'weight': 20, 'height': 30, 'width': 40, 'length': 20, 'template': None, 'id': 2}
  item3: {'weight': 150, 'height': 80, 'width': 100, 'length': 96, 'template': None, 'id': 3}
  item4: {'weight': 75, 'height': 30, 'width': 40, 'length': 60, 'template': None, 'id': 4}
  item5: {'weight': 33, 'height': 80, 'width': 100, 'length': 36, 'template': None, 'id': 5}

-- AFTER --
inventory:
  item1: {'weight': 100, 'height': 80, 'width': 120, 'length': 75, 'template': None, 'id': 1}
  item2: {'weight': 20, 'height': 30, 'width': 40, 'length': 20, 'template': 1, 'id': 2}
  item3: {'weight': 150, 'height': 80, 'width': 100, 'length': 96, 'template': 2, 'id': 3}
  item4: {'weight': 75, 'height': 30, 'width': 40, 'length': 60, 'template': 1, 'id': 4}
  item5: {'weight': 33, 'height': 80, 'width': 100, 'length': 36, 'template': 2, 'id': 5}

templates: {1: (30, 40), 2: (80, 100)}