3

私は一般的なPythonメモライザーを持っています:

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

動作しますが、効率的でない場合があるため、満足できません。最近、リストを引数として取る関数でそれを使用しましたが、明らかにリスト全体でキーを作成するとすべてが遅くなりました。それを行う最善の方法は何ですか？(つまり、引数が何であれ、キーがどれだけ長くても複雑でも、キーを効率的に計算するため)

問題は、一般的なメモライザーの引数と関数からキーを効率的に生成する方法についてだと思います.1つのプログラムで、貧弱なキー (生成するにはコストがかかりすぎる) がランタイムに大きな影響を与えることを観察しました。私のプログラムは 'str(args)' で 45 秒かかっていましたが、手作りのキーで 3 秒に短縮できました。残念ながら、手作りのキーはこのプログラムに固有のものですが、毎回キャッシュ用に特定の手作りのキーをロールアウトする必要のない、高速なメモライザーが必要です。

4

2 に答える 2

7

まず、ここでハッシュ化が合理的で必要であると確信していO(N)て、より高速なアルゴリズムで高速化したい場合はhash(str(x))、これを試してください。

def hash_seq(iterable):
    result = hash(type(iterable))
    for element in iterable:
        result ^= hash(element)
    return result

もちろん、これはおそらく深いシーケンスでは機能しませんが、それを回避する明白な方法があります:

def hash_seq(iterable):
    result = hash(type(iterable))
    for element in iterable:
        try:
            result ^= hash(element)
        except TypeError:
            result ^= hash_seq(element)
    return result

同じリストの異なる順列に対して同じ値を返すため、これが十分なハッシュアルゴリズムであるとは思いません。しかし、十分に高速なハッシュ アルゴリズムは存在しないと確信しています。少なくとも、C や Cython で書かれている場合は、これが目的の方向である場合、最終的にはそうしたいと思うでしょう。

また、これはstr(or marshal) が正しくない多くの場合で正しいことに注意する価値がlistあります。ただし、すべての場合においてまだ正しいわけではありません。特に、「同じ要素を反復する」とは、反復可能な型に対して「等しい」ことを意味すると想定していますが、これは明らかに真であるとは限りません。偽陰性は大した問題ではありませんが、偽陽性は問題です (たとえば、キーが同じで値が異なる 2 つの が誤って等しく比較され、メモが共有される場合があります)。repriddict

また、かなり大きな乗数を持つ 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

str簡単なテストから、純粋な Python 実装はかなり遅いです (ご想像のとおり、すべての Python がループしているため、 C がand をループしているのに比べてmarshal)、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

Cython でシーケンスを反復するだけで何もしない (これは事実上 N 回の呼び出しPyIter_Nextといくつかの refcounting であるため、ネイティブ C ではあまりうまくいかない) は、 と同じ時間の 70% ですtest_cy_xor。おそらく、 iterable の代わりに実際のシーケンスを要求することで高速化できます。また、 を要求することでさらに高速化できますがlist、どちらの方法でも利点を得るには、Cython ではなく明示的な C を記述する必要がある場合があります。

とにかく、順序の問題をどのように解決しますか? 明らかな 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))

ハッシュテスト.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()

出力：

    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

これを高速化するためのいくつかの潜在的な方法を次に示します。

  • 深いシーケンスがたくさんある場合は、tryaroundを使用する代わりにhash、呼び出しPyObject_Hashて -1 をチェックします。
  • list単なる iterable の代わりに、シーケンス (または、さらに良いことに、a ) があることがわかっている場合、 PySequence_ITEM(or ) はおそらく上記で暗黙的に使用され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マッピングidを使用します。hashしかし、一般的に、それは明らかに合理的な仮定ではありません。(listオブジェクトが決して変化しない場合は、オブジェクトに切り替えるだけtupleで、この複雑さを気にする必要がなくなります。)

ただし、キャッシュされたハッシュ値メンバー (またはスロット) を追加するサブクラスでオブジェクトをラップし、変更呼び出し ( 、、など)listを受け取るたびにキャッシュを無効にすることができます。次に、それを確認できます。append__setitem____delitem__hash_seq

tuple最終結果は、 s: amortizedを使用した場合と同じ正確性とパフォーマンスになりますがO(N/M)、 fortuple Mは各同一で呼び出した回数であり、 for は各同一tupleで呼び出した回数であり、その間で変化することlistはありませんlist。

于 2012-12-28T20:02:07.203 に答える
3

あなたはいくつかのことを試すことができます：

strの代わりにmarshal.dumpsを使用すると、（少なくとも私のマシンでは）少し速くなる可能性があります。

>>> timeit.timeit("marshal.dumps([1,2,3])","import marshal", number=10000)
0.008287056301007567
>>> timeit.timeit("str([1,2,3])",number=10000)
0.01709315717356219

また、関数の計算にコストがかかり、それ自体がNoneを返す可能性がある場合は、メモ化関数が毎回それらを再計算します（ここに到達している可能性がありますが、詳細を知らなくても推測できます）。これらの2つのことを組み込むと、次のようになります。

import marshal
cache = {}

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

    def decorated(*args):
        key = (f, marshal.dumps(args))
        if key in cache:
            return cache[key]

        cache[key] = f(*args)
        return cache[key]

    return decorated
于 2012-12-28T19:14:52.940 に答える