在字典中获取相似值的最有效方法是什么

Question

我有一个包含对象的字典：

# I have thousands of objects in my real world scenario
dic = {'k1':obj1, 'k2':obj2, 'k3':obj3, ...}
# keys are string
# objs are MyObject

编辑: 抱歉让问题有些模糊。这里是具体的类和 like() 函数：

class MyObject(object):
    def __init__(self, period, dimensions):
        self.id = None
        self.period = period # period is etree.Element
        self.dimensions = dict() # id -> lxml.XMLElements
        for dim in dimensions:
            # there must be only one child: the typed dimension
            self.dimensions[dim.get('dimension')] = dim[0]
        self._hash = None

    def __eq__(self, other):
        return isinstance(other, MyObject)
            and self.period == other.period
            and self.dimensions == other.dimensions

    def like(self, other):
        return (other is not None \
            and self.period == other.period \
           and self.dimensions.keys() == other.dimensions.keys())

我想知道如何才能更好地实现查找字典 dic 中与给定值 val 相似的对象。也就是说，我想要一个类似于：

def find_keys(dic, val):
    return [v for v in dic if v.like(val))

不过这个方法太慢了，因为我需要对 find-keys() 进行成千上万次的迭代，而字典中有成千上万的对象。

现在，我在这些对象上实现了 __hash__(self)，并把键作为一个属性添加进去了：

    def __hash__(self):
        if self._hash is None:
            self._hash = hash(self.periodtype) ^ \
                hash(tuple(sorted(self.dimensions.values())))
        return self._hash

然后，我建立了一个查找字典，它是

hash_dic = { hash(obj1): [obj1], hash(obj2): [obj2, obj3] }

而这个新的搜索方法快多了：

def find_keys_fast(dic, val):
    prefetched=hash_dic[hash(val)]
    return [x.key for x in prefetched if x.like(val)]

由于 __hash__ 是一个内部使用的原生函数，通常用于集合和字典，我还有没有更快或更优雅的方法可以使用呢？

Answer 1

你的方法看起来不错，前提是你只想处理少量相似的对象。

为你自己的类定义 __hash__() 也是完全可以的。

如果你想把所有对象分成“相似”对象的类别，那有个更快的方法：你可以利用你的 like() 方法的传递性。实际上，如果 like(obj0, obj1) 和 like(obj1, obj2) 都为真，那么 like(obj0, obj2) 也会自动为真，这样就不需要再进行额外的计算了。这意味着你可以直接把所有对象高效地分组：

signature = lambda obj: (obj.period, obj.typed_dimensions.keys())
sorted_objs = sorted(dic.values(), key=signature)
objs_in_like_classes = [list(group) for (_, group) in itertools.groupby(sorted_objs, key=signature)]

这样可以自动把相似的对象放在一起。这种方法更简单，而且可能比自己定义 __hash__() 和 __eq__() 以及自己进行预取要快，因为 groupby() 利用了 == 的传递性。

(PS: 我更喜欢 Michael J. Barber 的“通过可哈希签名分组的相似对象字典”这种方法，因为它可能稍微快一点，而且更通用，因为不需要排序。)

如果你想保持当前的方法，可以稍微清理一下：你可以检查一下是否真的需要这些 if other is not None 的测试。如果你想正确处理比较（__eq__），你还应该处理 other 是不同类的情况（而不仅仅是检查是否为 None）；使用 isinstance() 就可以了。如果你只比较 MyObject 类的对象，like() 可能会有所不同。在这种情况下，你的代码应该像这样：

def __eq__(self, other):
    if isinstance(other, MyObject):
        return (self.period == other.period
                and self.typed_dimensions == other.typed_dimensions)
    else:
        return False

def like(self, other):
    return (self.period == other.period  # No need for a backslash
            and self.typed_dimensions.keys() == other.typed_dimensions.keys())

这样可以让代码更简洁（但不一定更快）。

你可以通过在 __init__() 中不执行 self._hash = None 来让你的 __hash__() 函数稍微快一点，并且可以写成：

def __hash__(self):
    try:
        return self._hash
    except AttributeError:
        self._hash = (hash(self.periodtype) ^
                      hash(tuple(sorted(self.dimensions.values()))))
        return self._hash

实际上，当没有引发异常时，try 是很快的（在你的情况下，这种情况是最常见的）。

至于你的 hash_dict，可以用以下方式高效构建：

hash_dict = dict(itertools.groupby(dic.values(), key=hash))

(也许这就是你已经在做的事情)。

Answer 2

因为我不知道你的数据结构是什么样的，也不清楚你想要的相似性是什么，所以我只能猜测一些可能有效的方法。不过，也许你可以用字典构建一种叫做前缀树的东西。就像这样：

trie = {'a':{'b':{'e':{}, 's':{}}, 'c':{'t':{}, 'k':{}}}}

前缀树通常用来查找有共同前缀的字符串，但也许你的对象数据可以以某种方式表示成字符串。如果数据可以按照某种顺序排列，使得字符串中较早的数据必须相等（==），那么这种方法可能特别有效。我甚至可以想象，前缀树的叶子节点可以包含所有相似的对象，而不仅仅是完全相同的对象。

下面是一个关于如何使用前缀树的小示例：

>>> trie = {'a':{'b':{'e':{}, 's':{}}, 'c':{'t':{}, 'k':{}}}}
>>> def rec_print(trie, accum=''):
...     if trie:
...         for k in trie:
...             rec_print(trie[k], accum + k)
...     else:
...         print accum
... 
>>> rec_print(trie)
ack
act
abs
abe

Answer 3

现在我们可以看到like的实现，一个相当简单的方法似乎是可行的——比我之前的答案简单多了。我们可以在MyObject上定义一个新的signature方法：

def signature(self):
    return (self.period, frozenset(self.dimensions.keys()))

然后遍历这些对象：

import collections
sig_keys = collections.defaultdict(set)
for k, obj in dic.iteritems():
    sig_keys[obj.signature()].add(k)

这样一来，sig_keys.values()就能得到所有相似对象的标识符集合。如果需要的话，也可以直接构建对象的列表，这样可能更好：

sig_objs = collections.defaultdict(list)
for obj in dic.itervalues():
    sig_objs[obj.signature()].append(obj)

如果你愿意，可以把__hash__定义为return hash(self.signature())或者类似的方式。