2

参照透過性の関数があるとしましょう。覚えるのはとても簡単です。例：

def memoize(obj):
  memo = {}
  @functools.wraps(obj)
  def memoizer(*args, **kwargs):
    combined_args = args + (kwd_mark,) + tuple(sorted(kwargs.items()))
    if combined_args not in memo:
      memo[combined_args] = obj(*args, **kwargs)
    return cache[combined_args]
  return memoizer

@memoize
def my_function(data, alpha, beta):
  # ...

dataここで、への議論my_functionが巨大であると仮定します。たとえば、frozenset何百万もの要素が含まれています。この場合、メモ化のコストは法外です。毎回hash(data)、辞書検索の一部として計算する必要があります。

デコレータ内のオブジェクトの代わりに、memo辞書を属性にすることができます。このようにして、別の巨大なものが同じになる可能性はごくわずかであるため、キャッシュルックアップを実行するときに引数を完全にスキップできます。ただし、このアプローチでは、に渡された引数が汚染されてしまいます。さらに悪いことに、2つ以上の大きな引数がある場合、これはまったく役に立ちません（1つの引数にしかアタッチできません）。datamemoizedatafrozensetmy_functionmemo

他にできることはありますか？

4

2 に答える 2

1

ビルトイン__hash__は最初の計算後に独自の値をキャッシュするため、それほど悪くはないことがわかります。__eq__実際のパフォーマンスへの影響は、同じオブジェクトで短絡しないため、組み込みによってもたらされ、実際には毎回完全な比較が行われるため、非常にコストがかかります。

私が考えたアプローチの1つは、すべての大きな引数に対して組み込みクラスをサブクラス化することです。

class MyFrozenSet(frozenset):
  __eq__ = lambda self, other : id(self) == id(other)
  __hash__ = lambda self : id(self)

このように、辞書の検索は瞬時に行われます。しかし、新しいクラスの平等は破られます。

より良い解決策はおそらくこれです：ディクショナリルックアップが実行される場合にのみ、大きな引数を再定義__eq__し__hash__、ラップされたオブジェクトのを返す特別なクラス内にラップすることができますid()。frozensetラッパーの明らかな実装は、すべての標準メソッドをコピーする必要があるため、少し面倒です。おそらく、関連するABCクラスからそれを導き出すことはそれをより簡単にするかもしれません。

于 2012-10-04T12:02:08.827 に答える
1

さて、あなたは恐れることなくそこで「ハッシュ」を使うことができます。凍結セットのハッシュは、Pythonによって複数回計算されることはありません-作成されたとき-タイミングを確認してください：

>>> timeit("frozenset(a)", "a=range(100)")
3.26825213432312
>>> timeit("hash(a)", "a=frozenset(range(100))")
0.08160710334777832
>>> timeit("(lambda x:x)(a)", "a=hash(frozenset(range(100)))")
0.1994171142578125

Pythonの「ハッシュ」ビルトインがオブジェクトのメソッドを呼び出すことを忘れないでください。このメソッドの__hash__戻り値は、ビルトインのハッシュ可能なオブジェクトの作成時に定義されます。上記では、アイデンティティラムダ関数の呼び出しが「ハッシュ（a）」の呼び出しよりも2倍以上遅いことがわかります。

したがって、すべての引数がハッシュ可能である場合は、「combined_args」を作成するときにハッシュを追加するだけです。それ以外の場合は、条件付きで、frozenset（およびおそらく他の）タイプのハッシュを使用するように作成を記述します。

于 2012-10-04T11:59:17.517 に答える