Обработчик заметок
Является ли «хорошей практикой» создать класс, подобный ниже, который может обрабатывать процесс memoization для вас? Преимущества memoization настолько велики (в некоторых случаях, как этот, где он падает с 501003 до 1507 вызовов функций и от 1,409 до 0,006 секунды времени процессора на моем компьютере), что, похоже, такой класс будет полезен.
Однако я читал только отрицательные комментарии об использовании eval() . Является ли это использование этого оправданным, учитывая гибкость такого подхода?
Это может автоматически сэкономить любое возвращаемое значение за счет потери побочных эффектов. Благодарю.
import cProfile class Memoizer(object): """A handler for saving function results.""" def __init__(self): self.memos = dict() def memo(self, string): if string in self.memos: return self.memos[string] else: self.memos[string] = eval(string) self.memo(string) def factorial(n): assert type(n) == int if n == 1: return 1 else: return n * factorial(n-1) # find the factorial of num num = 500 # this many times times = 1000 def factorialTwice(): factorial(num) for x in xrange(0, times): factorial(num) return factorial(num) def memoizedFactorial(): handler = Memoizer() for x in xrange(0, times): handler.memo("factorial(%d)" % num) return handler.memo("factorial(%d)" % num) cProfile.run('factorialTwice()') cProfile.run('memoizedFactorial()')
- Невозможно реализовать алгоритм таблицы динамического программирования в python
- Рекурсивный алгоритм изменения
- memoization не работает как ожидалось
- Сумма подмножества рекурсивно в Python
- Является ли эта самая длинная общая подпоследовательность правильной?
Вы можете memoize, не прибегая к eval .
A (очень простой) memoizer:
def memoized(f): cache={} def ret(*args): if args in cache: return cache[args] else: answer=f(*args) cache[args]=answer return answer return ret @memoized def fibonacci(n): if n==0 or n==1: return 1 else: return fibonacci(n-1)+fibonacci(n-2) print fibonacci(100)
eval часто ошибается как evil первую очередь потому, что идея выполнения «строк» во время выполнения чревата соображениями безопасности. Вы достаточно избежали кода? Кавычки? И множество других раздражающих головных болей. Ваш обработчик memoise работает, но на самом деле это не Python. Подход MAK намного более Pythonic. Попробуем несколько экспериментов.
Я отредактировал обе версии и запустил их только один раз с 100 в качестве входных данных. Я также переместил экземпляр Memoizer . Вот результаты.
>>> timeit.timeit(memoizedFactorial,number=1000) 0.08526921272277832h >>> timeit.timeit(foo0.mfactorial,number=1000) 0.000804901123046875
В дополнение к этому, ваша версия требует обертки вокруг функции, которая должна быть замечена, которая должна быть записана в строке. Это уродливо. Решение MAK является чистым, поскольку «процесс memoisation» инкапсулирован в отдельную функцию, которая может быть удобно применена к любой дорогостоящей функции ненавязчивым образом. Это не очень Pythonic. У меня есть некоторые подробности о написании таких декораторов в моем учебнике по Python по адресу http://nibrahim.net.in/self-defence/, если вы заинтересованы.
- Как удобно решить задачу оптимизации назначения
- Алгоритм поиска самого загруженного периода?
- Вычисление расстояния редактирования последовательности ДНК python
- Самая длинная общая подпоследовательность строк 3+
- Поиск кратчайших комбинаций в массиве / последовательности, которая равна сумме
- рекурсивно реализуя «минимальное количество монет» в python
- Задача динамического программирования в Python
- Интерпретация против динамического штрафа отправки в Python
- Самая длинная возрастающая подпоследовательность в Python (для цикла vs While)