高效的通用Python memoize

Fra*_*ank 3 python memoization

我有一个通用的Python memoizer:

cache = {}

def memoize(f): 
    """Memoize any function."""

    def decorated(*args):
        key = (f, str(args))
        result = cache.get(key, None)
        if result is None:
            result = f(*args)
            cache[key] = result
        return result

    return decorated
Run Code Online (Sandbox Code Playgroud)

它有效,但我对它不满意,因为有时效率不高.最近,我使用了一个将列表作为参数的函数,显然用整个列表制作键会减慢一切.最好的方法是什么?(即,有效地计算密钥,无论args是什么,无论它们是多长还是复杂)

我想这个问题实际上是关于如何从args和泛型memoizer的函数有效地生成密钥 - 我在一个程序中观察到,糟糕的密钥(生成成本太高)对运行时产生了重大影响.我的编程用'str(args)'拍摄了45秒,但我可以用手工制作的键将其减少到3秒.不幸的是,手工制作的密钥是特定于这个编程,但我想要一个快速的记事本,我不必每次都为缓存推出特定的,手工制作的密钥.

aba*_*ert 6

首先,如果您非常确定O(N)散列是合理且必要的,并且您只想用更快的算法来加快速度hash(str(x)),请尝试以下方法:

def hash_seq(iterable):
    result = hash(type(iterable))
    for element in iterable:
        result ^= hash(element)
    return result
Run Code Online (Sandbox Code Playgroud)

当然,这对于可能很深的序列不起作用,但有一个显而易见的方法:

def hash_seq(iterable):
    result = hash(type(iterable))
    for element in iterable:
        try:
            result ^= hash(element)
        except TypeError:
            result ^= hash_seq(element)
    return result
Run Code Online (Sandbox Code Playgroud)

我不认为这是一个足够好的哈希算法,因为它将为同一个列表的不同排列返回相同的值.但我很确定没有足够好的哈希算法会快得多.至少如果它是用C或Cython编写的,如果这是你要去的方向,你最终可能会想做.

此外,值得注意的是,在许多情况下这将是正确的,其中str(或marshal)不会 - 例如,如果您list可能有一些可变元素repr涉及其id而不是其值.但是,它在所有情况下仍然不正确.特别是,它假定"迭代相同的元素"对于任何可迭代类型意味着"相等",这显然不能保证是真的.假阴性并不是一个大问题,但误报是(例如,两个dict具有相同键但不同的值可能虚假地比较相等并共享备忘录).

此外,它不使用额外的空间,而是使用相当大的乘数O(N).

无论如何,值得首先尝试这一点,然后才决定是否值得分析是否足够好和微调优化.

这是浅实现的一个简单的Cython版本:

def test_cy_xor(iterable):
    cdef int result = hash(type(iterable))
    cdef int h
    for element in iterable:
        h = hash(element)
        result ^= h
    return result
Run Code Online (Sandbox Code Playgroud)

从快速测试,纯Python实现是相当缓慢的(如你所期望的,以及所有的Python循环,相比于C循环中strmarshal),但用Cython版本赢得轻松:

    test_str(    3):  0.015475
test_marshal(    3):  0.008852
    test_xor(    3):  0.016770
 test_cy_xor(    3):  0.004613
    test_str(10000):  8.633486
test_marshal(10000):  2.735319
    test_xor(10000): 24.895457
 test_cy_xor(10000):  0.716340
Run Code Online (Sandbox Code Playgroud)

只是在Cython中迭代序列并且什么都不做(实际上只是N调用PyIter_Next和一些引用计数,所以你不会在原生C中做得更好)是70%的同时test_cy_xor.你可以通过要求一个实际的序列而不是一个可迭代来使它更快,甚至更需要一个list,尽管这两种方式都可能需要编写显式C而不是Cython才能获得好处.

无论如何,我们如何解决订购问题?显而易见的Python解决方案是哈希(i, element)而不是element,但是所有的元组操作都会使Cython版本减慢到12倍.标准解决方案是在每个xor之间乘以一些数字.但是当你在它的时候,值得尝试让值很好地分散为短序列,小int元素和其他非常常见的边缘情况.选择正确的数字很棘手,所以...我只是借用了一切tuple.这是完整的测试.

_hashtest.pyx:

cdef _test_xor(seq):
    cdef long result = 0x345678
    cdef long mult = 1000003
    cdef long h
    cdef long l = 0
    try:
        l = len(seq)
    except TypeError:
        # NOTE: This probably means very short non-len-able sequences
        # will not be spread as well as they should, but I'm not
        # sure what else to do.
        l = 100
    for element in seq:
        try:
            h = hash(element)
        except TypeError:
            h = _test_xor(element)
        result ^= h
        result *= mult
        mult += 82520 + l + l
    result += 97531
    return result

def test_xor(seq):
    return _test_xor(seq) ^ hash(type(seq))
Run Code Online (Sandbox Code Playgroud)

hashtest.py:

import marshal
import random
import timeit
import pyximport
pyximport.install()
import _hashtest

def test_str(seq):
    return hash(str(seq))

def test_marshal(seq):
    return hash(marshal.dumps(seq))

def test_cy_xor(seq):
    return _hashtest.test_xor(seq)

# This one is so slow that I don't bother to test it...
def test_xor(seq):
    result = hash(type(seq))
    for i, element in enumerate(seq):
        try:
            result ^= hash((i, element))
        except TypeError:
            result ^= hash(i, hash_seq(element))
    return result

smalltest = [1,2,3]
bigtest = [random.randint(10000, 20000) for _ in range(10000)]

def run():
    for seq in smalltest, bigtest:
        for f in test_str, test_marshal, test_cy_xor:
            print('%16s(%5d): %9f' % (f.func_name, len(seq),
                                      timeit.timeit(lambda: f(seq), number=10000)))

if __name__ == '__main__':
    run()
Run Code Online (Sandbox Code Playgroud)

输出:

    test_str(    3):  0.014489
test_marshal(    3):  0.008746
 test_cy_xor(    3):  0.004686
    test_str(10000):  8.563252
test_marshal(10000):  2.744564
 test_cy_xor(10000):  0.904398
Run Code Online (Sandbox Code Playgroud)

以下是一些提高速度的潜在方法:

  • 如果您有很多深度序列,而不是使用try周围hash,请调用PyObject_Hash并检查-1.
  • 如果你知道你有一个序列(或者,甚至更好,特别是a list),而不仅仅是一个可迭代的,PySequence_ITEM(或PyList_GET_ITEM)可能比PyIter_Next上面隐式使用的更快.

在任何一种情况下,一旦你开始调用C API调用,通常更容易删除Cython并只用C编写函数.(你仍然可以使用Cython编写一个关于该C函数的简单包装,而不是手动编写扩展模块的代码.)那时,只需tuplehash直接借用代码而不是重新实现相同的算法.

如果你正在寻找一种方法来避免这种O(N)情况,那是不可能的.如果你看看如何tuple.__hash__,frozenset.__hash__ImmutableSet.__hash__工作(最后一个是纯Python并且非常易读,顺便说一句),他们都会采取O(N).但是,它们都缓存哈希值.因此,如果你经常散列相同的 tuple(而不是非相同但相等的),它会接近恒定的时间.(它的O(N/M),在这里M是你每次调用的次数tuple.)

如果你可以假设你的list对象从未调用之间发生变异,可以很明显的做同样的事情,例如与dict映射idhash作为外部高速缓存.但总的来说,这显然不是一个合理的假设.(如果你的list对象永远不会变异,那么只需切换到tuple对象就可以更容易了,而不必担心所有这些复杂性.)

但是,你可以用你list在添加了缓存的散列值成员(或槽),而当它得到一个不同诱变调用(高速缓存无效的子类的对象append,__setitem__,__delitem__等).然后你hash_seq可以检查一下.

最终结果与tuples:amortized 具有相同的正确性和性能O(N/M),除了for tuple M是你用每个相同调用的次数tuple,而对于list它是你用每个相同list而不调用的次数.