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

Question

我还没有看到一个成熟的方法来记忆一个接受关键字参数的函数，即一些类型的东西

def f(*args, **kwargs)

由于通常记忆化程序（memoizer）具有一个字典（dict）来缓存给定输入参数的结果，而kwargs是一个字典（dict），因此不可哈希。我尝试过根据此讨论所述使用

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

作为缓存 dict 的键，但只有当 kwargs 中的值是可哈希的时才有效。此外，如下面的答案所指出的那样，frozenset 不是一个有序的数据结构。因此，以下解决方案可能更安全：

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

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

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

我所看到的唯一缺点是哈希可能会产生很长的字符串开销。就我所知，结果应该是正确的。有人能发现后一种方法存在什么问题吗？下面的一个答案之一指出，这假设关键字参数的值的__str__或__repr__函数遵循某些行为。这似乎是一个致命缺陷。是否有另一种更为成熟的方法可以处理**kwargs和不可哈希的参数值？

- juanchopanza

Answer 1

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()，但kwargs将具有str键。”这是完全正确的。因此，这对于键不是问题，但如果您（或者不太可能的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???????>进行散列，并且稍后由于垃圾回收在同一内存位置创建了相同类型的对象，则将从记忆化函数获得不正确的结果。如上所述，一个可能真正刻意的解决方法是使用正则表达式检测这些对象。

- ninjagecko

---

你是否有这样一种感觉，即在相同的平台上，对于相同的kwargs，frozenset(kwargs.items())的排序是否是确定性的？ - juanchopanza

虽然您无法在任意字典上使用 sorted()，但 kwargs 将具有字符串键。 - Ignacio Vazquez-Abrams

确实，这可能排除了第一种选项。但也许是一个已排序的kwargs.items()元组... - juanchopanza

@ninjagecko，您的回答涉及许多重要问题，但我认为您的第一句话是不正确的，如果考虑到“frozenset”排序问题的话。我已经扩展了我的问题，以反映从答案中获得的一些信息。我还没有选择一个答案，因为我想看看是否有人有魔法般的解决方案，或者是否达成共识认为没有解决方案。 - juanchopanza

@ninjagecko 我的问题是顺序没有定义，所以在一个地方使用frozenset(some_sequence)可能与其他地方不同。虽然不太可能发生，但如果标准不能保证顺序，我宁愿不依赖它。 - juanchopanza

Answer 2

字典可以是任意顺序的，因此不能保证后者会起作用。使用sorted(kwargs.items())首先按键排序。

- Ignacio Vazquez-Abrams

---

+1非常好的观点！我会更正问题，因为那不是主要重点。 - juanchopanza

顺便问一下，那会使使用frozenset的第一种方法无效吗？ - juanchopanza

我不知道关于frozenset的具体内容，但我相信它可能会。 - Ignacio Vazquez-Abrams

备忘录通常使用args作为结果字典的键，而hash(sorted({'key': 'arg'}.items()))会失败，但是hash(frozenset({'key': 'arg'}.items()))可以正常工作。 - Russia Must Remove Putin

Answer 3

这与EMS所说的类似，但最好的方法是：

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

我一直在进行有关修饰符的记忆方面的研究和测试，这是目前我发现的最佳方法。

- swampfox357

Answer 4

在这里：

from functools import wraps

def memoize(fun):
    """A simple memoize decorator for functions supporting positional args."""
    @wraps(fun)
    def wrapper(*args, **kwargs):
        key = (args, frozenset(sorted(kwargs.items())))
        try:
            return cache[key]
        except KeyError:
            ret = cache[key] = fun(*args, **kwargs)
        return ret
    cache = {}
    return wrapper

测试:

import unittest

class TestMemoize(unittest.TestCase):
    def test_it(self):
        @memoize
        def foo(*args, **kwargs):
            "foo docstring"
            calls.append(None)
            return (args, kwargs)

        calls = []
        # no args
        for x in range(2):
            ret = foo()
            expected = ((), {})
            self.assertEqual(ret, expected)
            self.assertEqual(len(calls), 1)
        # with args
        for x in range(2):
            ret = foo(1)
            expected = ((1, ), {})
            self.assertEqual(ret, expected)
            self.assertEqual(len(calls), 2)
        # with args + kwargs
        for x in range(2):
            ret = foo(1, bar=2)
            expected = ((1, ), {'bar': 2})
            self.assertEqual(ret, expected)
            self.assertEqual(len(calls), 3)
        self.assertEqual(foo.__doc__, "foo docstring")

unittest.main()

只要你不传递一个不可哈希的类型（例如dict）作为参数，这就可以工作。我对此没有解决方案，但是collections.lru_cache()的实现可能有。在这里查看_make_key()函数：http://code.activestate.com/recipes/578078/。

- Giampaolo Rodolà

Answer 5

那么 key = pickle.dumps( (args, sorted(kwargs.items()), -1 ) 呢？ 这似乎比 str() 或 repr() 更为健壮。

- EMS