如何对**kwargs进行记忆化？

Question

我还没看到一个成熟的方法来缓存一个接受关键字参数的函数，也就是像下面这种类型的函数：

def f(*args, **kwargs)

通常，缓存的方式是用一个 dict 来存储给定输入参数的结果，而 kwargs 本身就是一个 dict，所以它不能被哈希（也就是不能用作字典的键）。我尝试过，参考了这里的讨论，使用

(args, frozenset(kwargs.items()))

作为缓存 dict 的键，但这只在 kwargs 中的值是可哈希的情况下有效。此外，下面的回答指出，frozenset 不是一种有序的数据结构。因此，这个解决方案可能更安全：

(args, tuple(sorted(kwargs.items())))

但它仍然无法处理不可哈希的元素。我看到的另一种方法是使用 kwargs 的字符串表示作为缓存键：

(args, str(sorted(kwargs.items())))

我觉得这个方法唯一的缺点是，哈希一个可能非常长的字符串会有一些开销。就我所见，结果应该是正确的。有没有人能发现这个方法的任何问题？下面的一个回答指出，这个方法假设了关键字参数值的 __str__ 或 __repr__ 函数会有特定的行为。这似乎是个致命问题。

有没有其他更成熟的方法可以实现缓存，能够处理 **kwargs 和不可哈希的参数值？

Answer 1

这跟EMS说的有点像，但最好的方法是：

key = cPickle.dumps((*args, **kwargs))

我最近在研究和测试用装饰器来记忆的事情，这个方法是我目前找到的最好的。

Answer 2

字典里的内容顺序是随机的，所以不能保证后面的代码一定能正常工作。你可以用 sorted(kwargs.items()) 先把字典按键的顺序排好。

Answer 3

key = (args, frozenset(kwargs.items()))

这是你在不对数据做假设的情况下能做到的“最好”选择。

不过，想要对字典进行记忆化处理（这有点不常见）也是可以理解的，如果你想这样做，可以特别处理一下。例如，你可以在复制字典时递归地应用 frozenset(---.items())。

---

如果你使用 sorted，可能会遇到一些麻烦，因为有些键是无法排序的。比如说，“子集和相等比较并不能推广到完整的排序函数。例如，任何两个不相交的集合既不相等也不是彼此的子集，因此以下所有比较都会返回 False：a<b、a==b 或 a>b。因此，集合并没有实现 cmp() 方法。”

>>> sorted([frozenset({1,2}), frozenset({1,3})])
[frozenset({1, 2}), frozenset({1, 3})]

>>> sorted([frozenset({1,3}), frozenset({1,2})]) # THE SAME
[frozenset({1, 3}), frozenset({1, 2})] # DIFFERENT SORT RESULT

# sorted(stuff) != sorted(reversed(stuff)), if not strictly totally ordered

编辑：Ignacio 说“虽然你不能在任意字典上使用 sorted()，但关键字参数会有字符串类型的键。”这完全正确。因此，这对键来说不是问题，但如果你（或者不太可能的 repr）依赖于某种排序，可能需要注意值的情况。

---

关于使用 str：

大多数数据通常都能很好地工作，但在某些情况下，恶意用户（比如在安全漏洞的情况下）可能会制造冲突。虽然这并不容易，因为大多数默认的 repr 使用了良好的分组和转义。实际上，我没有找到这样的冲突。但如果使用了不可靠的第三方或不完整的 repr 实现，就有可能出现问题。

---

还要考虑以下几点：如果你存储的键像 ((<map object at 0x1377d50>,), frozenset(...)) 和 ((<list_iterator object at 0x1377dd0>,<list_iterator object at 0x1377dd0>), frozenset(...))，那么你的缓存会因为调用相同的项目而无限增长。（你也许可以用正则表达式来解决这个问题……）而尝试消费生成器会搞乱你正在使用的函数的语义。不过，如果你希望基于 is 风格的相等性进行记忆化，而不是 == 风格的相等性，这可能是你想要的行为。

另外，在解释器中执行像 str({1:object()}) 这样的代码，每次都会返回内存中相同位置的对象！我觉得这是垃圾回收器在起作用。这会造成灾难，因为如果你恰好在哈希 <some object at 0x???????>，而且后来又在同一内存位置创建了一个相同类型的对象（由于垃圾回收），你会从记忆化的函数中得到错误的结果。如前所述，一个可能非常 hack 的解决方法是用正则表达式检测这样的对象。