將類似詞典的詞條組作爲鍵的組合鍵

Question

我想對數據集的類似條目進行分組。

ds = {1: 'foo', 
     2: 'bar', 
     3: 'foo', 
     4: 'bar', 
     5: 'foo'} 

>>>tupelize_dict(ds) 
{ 
    (1,3,5): 'foo', 
    (2,4): 'bar' 
} 

我寫了這個函數，但我確定有一些方法更簡單，不是嗎？

def tupelize_dict(data): 
    from itertools import chain, combinations 
    while True: 
     rounds = [] 
     for x in combinations(data.keys(), 2): 
      rounds.append((x, data[x[0]], data[x[1]])) 

     end = True 
     for k, a, b in rounds: 
      if a == b: 
       k_chain = [x if isinstance(x, (tuple, list)) else [x] for x in k] 
       data[tuple(sorted(chain.from_iterable(k_chain)))] = a 
       [data.pop(r) for r in k] 
       end = False 
       break 
     if end: 
      break 
    return data 

編輯

我感興趣的是一般情況下的數據集的內容可以是任何類型的對象，允許ds[i] == ds[j]：

ds = {1: {'a': {'b':'c'}}, 
     2: 'bar', 
     3: {'a': {'b':'c'}}, 
     4: 'bar', 
     5: {'a': {'b':'c'}}} 

Answer 1

繼acushner答案，就可以讓它工作，如果我可以計算數據集的元素內容的哈希值。

import pickle 
from collections import defaultdict 

def tupelize_dict(ds): 
    t = {} 
    d = defaultdict(list) 
    for k, v in ds.items(): 
     h = dumps(ds) 
     t[h] = v 
     d[h].append(k) 

    return {tuple(v): t[k] for k, v in d.items()} 

這個解決方案比我原來的主張要快得多。

爲了測試它，我做了一個集大隨機嵌套的字典和兩個實現運行cProfile：

original: 204.9 seconds 
new:  6.4 seconds 

編輯：

我意識到dumps不能與某些辭書工作，因爲鍵的順序可以在內部因爲不明原因而變化（見question）

解決方法是定購所有的字典：

import copy 
import collections 

def faithfulrepr(od): 
    od = od.deepcopy(od) 
    if isinstance(od, collections.Mapping): 
     res = collections.OrderedDict() 
     for k, v in sorted(od.items()): 
      res[k] = faithfulrepr(v) 
     return repr(res) 
    if isinstance(od, list): 
     for i, v in enumerate(od): 
      od[i] = faithfulrepr(v) 
     return repr(od) 
    return repr(od) 

def tupelize_dict(ds): 
    taxonomy = {} 
    binder = collections.defaultdict(list) 
    for key, value in ds.items(): 
     signature = faithfulrepr(value) 
     taxonomy[signature] = value 
     binder[signature].append(key) 
    def tu(keys): 
     return tuple(sorted(keys)) if len(keys) > 1 else keys[0] 
    return {tu(keys): taxonomy[s] for s, keys in binder.items()} 

Answer 2

這樣的事情應該做的絕招：

>>> from collections import defaultdict 
>>> ds = {1: 'foo', 
...  2: 'bar', 
...  3: 'foo', 
...  4: 'bar', 
...  5: 'foo'} 
>>> 
>>> d = defaultdict(list) 
>>> for k, v in ds.items(): 
...  d[v].append(k) 
... 
>>> res = {tuple(v): k for k, v in d.items()} 
>>> res 
{(1, 3, 5): 'foo', (2, 4): 'bar'} 

Answer 3

as以及你可以做這樣的事情。

def tupelize_dict(ds): 
    cache = {} 
    for key, value in ds.items(): 
     cache.setdefault(value, []).append(key) 
    return {tuple(v): k for k, v in cache.items()} 


ds = {1: 'foo', 
     2: 'bar', 
     3: 'foo', 
     4: 'bar', 
     5: 'foo'} 
print(tupelize_dict(ds))