Я использовал jruby, в моем случае я создал в config / initializers
postgres_driver.rb
$CLASSPATH << '~/.rbenv/versions/jruby-1.7.17/lib/ruby/gems/shared/gems/jdbc-postgres-9.4.1200/lib/postgresql-9.4-1200.jdbc4.jar'
или везде, где ваш драйвер, и все!
Memoization в основном сохраняет результаты прошлых операций, выполняемых с помощью рекурсивных алгоритмов, чтобы уменьшить необходимость пересечения дерева рекурсии, если тот же расчет требуется на более позднем этапе.
см. http : //scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/
Пример Memoization Fibonacci в Python:
fibcache = {}
def fib(num):
if num in fibcache:
return fibcache[num]
else:
fibcache[num] = num if num < 2 else fib(num-1) + fib(num-2)
return fibcache[num]
Memoization сохраняет результаты дорогостоящих вычислений и возвращает кешированный результат, а не непрерывно пересчитывает его.
Вот пример:
def doSomeExpensiveCalculation(self, input):
if input not in self.cache:
<do expensive calculation>
self.cache[input] = result
return self.cache[input]
Более полное описание можно найти в записи wikipedia в memoization .
if input not in self.cache
и self.cache[input]
(has_key
устарело, поскольку ... в начале серии 2.x, если не 2.0. self.cache(index)
никогда не был прав. IIRC)
– Jürgen A. Erhard
1 January 2010 в 16:46
Решение, которое работает как с аргументами positional, так и с ключевыми словами независимо от порядка, в котором были переданы ключевые слова args (используя inspect.getargspec ):
import inspect
import functools
def memoize(fn):
cache = fn.cache = {}
@functools.wraps(fn)
def memoizer(*args, **kwargs):
kwargs.update(dict(zip(inspect.getargspec(fn).args, args)))
key = tuple(kwargs.get(k, None) for k in inspect.getargspec(fn).args)
if key not in cache:
cache[key] = fn(**kwargs)
return cache[key]
return memoizer
Аналогичный вопрос: Идентификация эквивалентных функций функции varargs для memoization в Python
Запоминание - это преобразование функций в структуры данных. Обычно требуется, чтобы преобразование происходило постепенно и лениво (по запросу данного элемента домена - или «ключ»). В ленивых функциональных языках это ленивое преобразование может происходить автоматически, и, таким образом, мемонирование может быть реализовано без (явных) побочных эффектов.
Давайте не будем забывать о встроенной функции hasattr
, для тех, кто хочет заниматься ремеслом. Таким образом, вы можете хранить кеш-память внутри определения функции (в отличие от глобального).
def fact(n):
if not hasattr(fact, 'mem'):
fact.mem = {1: 1}
if not n in fact.mem:
fact.mem[n] = n * fact(n - 1)
return fact.mem[n]
Новое для Python 3.2 - functools.lru_cache
. По умолчанию он кэширует только 128 последних вызовов, но вы можете установить maxsize
на None
, чтобы указать, что кеш никогда не истекает:
import functools
@functools.lru_cache(maxsize=None)
def fib(num):
if num < 2:
return num
else:
return fib(num-1) + fib(num-2)
Эта функция сама по себе очень медленно, попробуйте fib(36)
, и вам придется подождать около десяти секунд.
Добавление аннотации lru_cache
гарантирует, что если функция была вызвана в последнее время для определенного значения, она не будет компрометировать это значение, а использовать кешированный предыдущий результат. В этом случае это приводит к значительному улучшению скорости, в то время как код не загроможден деталями кеширования.
fib
он должен будет вернуться к базовому регистру до того, как произойдет мемонирование. Итак, ваше поведение как раз и ожидается.
– Quelklef
19 August 2018 в 02:07
Я нашел это чрезвычайно полезным
def memoize(function):
from functools import wraps
memo = {}
@wraps(function)
def wrapper(*args):
if args in memo:
return memo[args]
else:
rv = function(*args)
memo[args] = rv
return rv
return wrapper
@memoize
def fibonacci(n):
if n < 2: return n
return fibonacci(n - 1) + fibonacci(n - 2)
fibonacci(25)
functools.wraps
.
– anishpatel
25 April 2017 в 02:29
Другие ответы охватывают то, что хорошо. Я не повторяю этого. Просто некоторые моменты, которые могут быть полезны для вас.
Как правило, memoisation - это операция, которую вы можете применить к любой функции, которая что-то вычисляет (дорого) и возвращает значение. Из-за этого он часто реализуется как декоратор . Реализация прост, и это будет нечто подобное
memoised_function = memoise(actual_function)
или выражено в качестве декоратора
@memoise
def actual_function(arg1, arg2):
#body
Мемонирование эффективно относится к запоминанию («воспоминания» → «меморандум» → для запоминания) результаты вызовов методов на основе входных данных метода, а затем возврат запоминаемого результата, а не повторение вычисления результата. Вы можете думать об этом как кэш для результатов метода. Более подробную информацию см. На стр. 387 для определения в . Введение в алгоритмы (3e), Cormen и др.
. Простой пример вычисления факториалов с использованием memoization в Python был бы чем-то вроде это:
factorial_memo = {}
def factorial(k):
if k < 2: return 1
if k not in factorial_memo:
factorial_memo[k] = k * factorial(k-1)
return factorial_memo[k]
Вы можете усложниться и инкапсулировать процесс memoization в класс:
class Memoize:
def __init__(self, f):
self.f = f
self.memo = {}
def __call__(self, *args):
if not args in self.memo:
self.memo[args] = self.f(*args)
#Warning: You may wish to do a deepcopy here if returning objects
return self.memo[args]
Затем:
def factorial(k):
if k < 2: return 1
return k * factorial(k - 1)
factorial = Memoize(factorial)
Функция известный как « decorators », был добавлен в Python 2.4, который позволяет вам просто написать следующее, чтобы выполнить одно и то же:
@Memoize
def factorial(k):
if k < 2: return 1
return k * factorial(k - 1)
Библиотека декораторов питона имеет аналогичный декоратор, называемый memoized
, который немного более устойчив, чем класс Memoize
, показанный здесь.
factorial_memo
, потому что factorial
внутри def factorial
все еще вызывает старое unmemoize factorial
.
– adamsmith
6 August 2013 в 08:35
if k not in factorial_memo:
, который лучше, чем if not k in factorial_memo:
.
– ShreevatsaR
4 April 2014 в 07:34
args
является кортежем. def some_function(*args)
делает args кортежем.
– Adam Smith
13 December 2016 в 19:18
Вот решение, которое будет работать со списком или аргументом типа dict без завивания:
def memoize(fn):
"""returns a memoized version of any function that can be called
with the same list of arguments.
Usage: foo = memoize(foo)"""
def handle_item(x):
if isinstance(x, dict):
return make_tuple(sorted(x.items()))
elif hasattr(x, '__iter__'):
return make_tuple(x)
else:
return x
def make_tuple(L):
return tuple(handle_item(x) for x in L)
def foo(*args, **kwargs):
items_cache = make_tuple(sorted(kwargs.items()))
args_cache = make_tuple(args)
if (args_cache, items_cache) not in foo.past_calls:
foo.past_calls[(args_cache, items_cache)] = fn(*args,**kwargs)
return foo.past_calls[(args_cache, items_cache)]
foo.past_calls = {}
foo.__name__ = 'memoized_' + fn.__name__
return foo
Обратите внимание, что этот подход может быть естественным образом распространен на любой объект, реализуя собственную хеш-функцию как особый случай в handle_item. Например, чтобы этот подход работал для функции, которая принимает набор в качестве входного аргумента, вы можете добавить к handle_item:
if is_instance(x, set):
return make_tuple(sorted(list(x)))
list
[1, 2, 3]
можно ошибочно считать тем же самым, что и другой аргумент set
со значением {1, 2, 3}
. Кроме того, наборы неупорядочены, как словари, поэтому они также должны быть sorted()
. Также обратите внимание, что аргумент рекурсивной структуры данных вызовет бесконечный цикл.
– martineau
20 January 2014 в 03:31
list
s и set
s являются «упорядоченными». в одно и то же, и поэтому становятся неотличимыми друг от друга. Пример кода для добавления поддержки для sets
, описанного в вашем последнем обновлении, не исключает, что я боюсь. Это можно легко увидеть, передав [1,2,3]
и {1,2,3}
отдельно в качестве аргумента в функцию «memoize» d test и видя, называется ли она дважды, как и должно быть, или нет.
– martineau
21 January 2014 в 04:07
list
s и dict
s, потому что для <[i3> возможно i>] для того, чтобы list
имел в точности то же самое, что и в результате вызова make_tuple(sorted(x.items()))
для словаря. Простым решением для обоих случаев было бы включение значения type()
в генерируемый набор. Я могу придумать еще более простой способ обработки set
s, но он не обобщает.
– martineau
22 January 2014 в 04:49
Просто хотел добавить к уже предоставленным ответам, библиотека декораторов Python имеет несколько простых, но полезных реализаций, которые также могут memoize «unhashable types», в отличие от functools.lru_cache
.
cache = {}
def fib(n):
if n <= 1:
return n
else:
if n not in cache:
cache[n] = fib(n-1) + fib(n-2)
return cache[n]
if n not in cache
. используя cache.keys
, создаст ненужный список в python 2
– n611x007
29 January 2013 в 11:53
Ну, я должен сначала ответить на первую часть: что такое memoization?
Это всего лишь метод для торговли памятью за время. Подумайте о таблице умножения .
Использование изменяемого объекта в качестве значения по умолчанию в Python обычно считается плохим. Но если использовать его с умом, на самом деле может быть полезно реализовать memoization
.
Вот пример, адаптированный из http://docs.python.org/2/faq/design.html # why-are-default-values-shared-between-objects
Используя mutable dict
в определении функции, промежуточные вычисленные результаты могут быть кэшированы (например, при расчете factorial(10)
после вычисления factorial(9)
мы можем повторно использовать все промежуточные результаты)
def factorial(n, _cache={1:1}):
try:
return _cache[n]
except IndexError:
_cache[n] = factorial(n-1)*n
return _cache[n]