Подходит ли frozenset для кэширования симметричных входных данных в python dict? - PullRequest
Новая
       22

Подходит ли frozenset для кэширования симметричных входных данных в python dict?

1 голос
/ 04 апреля 2010

Название более или менее говорит само за себя:

У меня есть функция, которая принимает симметричный ввод в виде двух аргументов, например что-то вроде 

def f(a1, a2):
    return heavy_stuff(abs(a1 - a2))

Теперь я хочу представить метод кеширования. Было бы правильно / питонно / достаточно эффективно сделать что-то вроде этого: 

cache = {}
def g(a1, a2):
    fs =frozenset((tuple(a1), tuple(a2)))
    if fs not in cache:
        cache[fs] = f(a1, a2)
    return cache[fs]

Или есть какой-нибудь лучший способ?

Редактировать : a1 и a2 могут быть строками массива numpy; Вот почему я обертываю их в кортеж каждый.

1 Ответ

2 голосов
/ 04 апреля 2010

Python всегда вычисляет все аргументы, которые вы передаете функции, и только тогда он вызывает функцию. Другими словами, как и большинство других языков, Python «нетерпелив» в своей оценке (главное исключение сегодня, вероятно, Haskell, но это вам не помогает; -).

Итак, setdefault - это очень неподходящий подход для кэширования! Всякий раз, когда вы делаете 

cache.setdefault(akey, f(x, y))

вы сначала звоните f(x, y) со всеми его вычислительными затратами, , затем , возможно, отбрасывает результаты этого вычисления на пол; это делает кеширование совершенно неэффективным.

Скорее, всегда делайте это следующим образом: 

akey = whatever(x, y)
if akey not in cache:
    cache[akey] = f(x, y)
return cache[akey]

или тому подобное - есть несколько других идиом, особенно если, например, вы знаете, что f никогда не вернется None: 

result = cache.get(akey)
if result is None:
    result = cache[akey] = f(x, y)
return result

Что касается вторичного вопроса о том, что является подходящим whatever для вычисления ключа, учитывая, что вы знаете, что f является симметричным, я думаю, frozenset, вероятно, в порядке; хотя (если компоненты x и y сопоставимы, а также хешируемы - то есть не будут работать с комплексными числами), вы можете рассмотреть 

ta1 = tuple(a1)
ta2 = tuple(a2)
if ta1 > ta2: key = ta1, ta2
else: key = ta2, ta1

Относительная производительность зависит от стоимости сравнения, по сравнению с хэшированием, пунктов в a1 и a2. Различия, скорее всего, будут незначительными.

...