def kh(s, t, n, l):
@lru_cache(maxsize=None)
def kmm(n, si, ti):
if n == 0:
return 1
if min(si, ti) < n:
return 0
if s[si-1] == t[ti-1]:
return l*(kmm(n, si, ti-1) + l*km(n-1, si-1, ti-1))
else:
return l * kmm(n, si, ti-1)
# return sum(km(n-1, si-1, j) * l**(ti-(j+1)+2) for j in range(ti) if t[j] == s[si-1])
@lru_cache(maxsize=None)
def km(n, si, ti):
if n == 0:
return 1
if min(si, ti) < n:
return 0
return l*km(n, si-1, ti) + kmm(n, si, ti)
# return l*km(n, si-1, ti) + sum(km(n-1, si-1, j) * l**(ti-(j+1)+2) for j in range(ti) if t[j] == s[si-1])
@lru_cache(maxsize=None)
def k(n, si, ti):
if min(si, ti) < n:
return 0
return k(n, si-1, ti) + sum(km(n-1, si-1, j) for j in range(ti) if t[j] == s[si-1]) * l**2
return k(n, len(s), len(t))
python类lru_cache()的实例源码
def lru_cache():
def dec(f):
def _(*args, **kws):
return f(*args, **kws)
return _
return dec
def lru_cache(func, maxsize=128, typed=False):
"""
Can be used with or without parenthesis. See `meta_wrap`'s effect.
"""
return functools.lru_cache(maxsize, typed)(func)
# ======================== Type conversion ========================
def lru_cache(*args, **kwargs):
return lambda x: x
def _get_indexword(model):
@functools.lru_cache(maxsize=50)
def indexword(word):
try:
return model.voc.index(word)
except ValueError:
return None
return indexword
def __init__(self, name):
self.word = True
self.regex = None
self.bold = False
self.italic = False
self.underline = False
self.reverse = False
self.color = None
self.linecolor = None
self._sound = None
self.abs_sound = None
self.wrap_line = None
self.format_line = ""
self.wrap_match = None
self.format_match = ""
self.replacement = None
self.enabled = True
self.mute = False
self.notify = False
self.focus = False
self.flash = False
self.copy = False
self._name = name
self.strip = 0
self.pattern = name
self._parent = self._prev = self._next = None
# Nickname and Channel filters:
# Lists of (bool, filter) tuples, where the bool is True for allow, False for deny.
self.filters = {'nick': [], 'channel': []}
self.check_filter = functools.lru_cache(maxsize=128)(self._check_filter)
self.update()
def test_lru_with_maxsize_none(self):
@functools.lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
self.assertEqual([fib(n) for n in range(16)],
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610])
self.assertEqual(fib.cache_info(),
functools._CacheInfo(hits=28, misses=16, maxsize=None, currsize=16))
fib.cache_clear()
self.assertEqual(fib.cache_info(),
functools._CacheInfo(hits=0, misses=0, maxsize=None, currsize=0))
def test_lru_with_exceptions(self):
# Verify that user_function exceptions get passed through without
# creating a hard-to-read chained exception.
# http://bugs.python.org/issue13177
for maxsize in (None, 100):
@functools.lru_cache(maxsize)
def func(i):
return 'abc'[i]
self.assertEqual(func(0), 'a')
with self.assertRaises(IndexError) as cm:
func(15)
self.assertIsNone(cm.exception.__context__)
# Verify that the previous exception did not result in a cached entry
with self.assertRaises(IndexError):
func(15)
def test_lru_with_types(self):
for maxsize in (None, 100):
@functools.lru_cache(maxsize=maxsize, typed=True)
def square(x):
return x * x
self.assertEqual(square(3), 9)
self.assertEqual(type(square(3)), type(9))
self.assertEqual(square(3.0), 9.0)
self.assertEqual(type(square(3.0)), type(9.0))
self.assertEqual(square(x=3), 9)
self.assertEqual(type(square(x=3)), type(9))
self.assertEqual(square(x=3.0), 9.0)
self.assertEqual(type(square(x=3.0)), type(9.0))
self.assertEqual(square.cache_info().hits, 4)
self.assertEqual(square.cache_info().misses, 4)
def __init__(self):
self.t_add_rules()
self.lexer = get_script_lexer()
self.parser = yacc.yacc(module=self, errorlog=logging, start='term',
debug=False, optimize=True, picklefile=os.path.join(parser_folder, "script_parser.pickle"))
# rename the parsing method (can't name it directly parse with lru_cache due to ply checking)
self.parse = self.t_parse
def __init__(self):
# Build the lexer and parser
self.lexer = get_lexer()
self.parser = yacc.yacc(module=self, errorlog=logging, start='path',
debug=False, optimize=True, picklefile="parser/path_parser.pickle")
# rename the parsing method (can't name it directly parse with lru_cache due to ply checking)
self.parse = self.t_parse
def simple_cache(func):
"""
Save results for the :meth:'path.using_module' classmethod.
When Python 3.2 is available, use functools.lru_cache instead.
"""
saved_results = {}
def wrapper(cls, module):
if module in saved_results:
return saved_results[module]
saved_results[module] = func(cls, module)
return saved_results[module]
return wrapper
def clear_path_caches():
"""Clear the caches of all path-related methods in this module that use an lru_cache."""
create_environment.cache_clear()
which.cache_clear()
find_python.cache_clear()
get_python_paths.cache_clear()
find_executable.cache_clear()
def _prebuilt_pkg(cls, pkg_type, fallback):
"""act as lru_cache"""
if pkg_type not in cls._cache_prebuilt_pkg:
pkg = fallback(force_rebuilt=True)
cls._cache_prebuilt_pkg[pkg_type] = pkg
logging.info("_prebuilt_pkg,id:{}".format(id(cls._cache_prebuilt_pkg)))
return cls._cache_prebuilt_pkg[pkg_type]
def pbuild_hs_m2s(cls, force_rebuilt=False):
"""pkg build: Handshake Master to Slaver"""
# because py27 do not have functools.lru_cache, so we must write our own
if force_rebuilt:
return CtrlPkg(
pkg_type=cls.PTYPE_HS_M2S,
data=(cls.SECRET_KEY_CRC32,),
SECRET_KEY_CRC32=cls.SECRET_KEY_CRC32, SECRET_KEY_REVERSED_CRC32=cls.SECRET_KEY_REVERSED_CRC32
)
else:
return cls._prebuilt_pkg(cls.PTYPE_HS_M2S, cls.pbuild_hs_m2s)
def _prebuilt_pkg(cls, pkg_type, fallback):
"""act as lru_cache"""
if pkg_type not in cls._cache_prebuilt_pkg:
pkg = fallback(force_rebuilt=True)
cls._cache_prebuilt_pkg[pkg_type] = pkg
return cls._cache_prebuilt_pkg[pkg_type]
def pbuild_hs_m2s(cls, force_rebuilt=False):
"""pkg build: Handshake Master to Slaver"""
# because py27 do not have functools.lru_cache, so we must write our own
if force_rebuilt:
return cls(
pkg_type=cls.PTYPE_HS_M2S,
data=(cls.SECRET_KEY_CRC32,),
)
else:
return cls._prebuilt_pkg(cls.PTYPE_HS_M2S, cls.pbuild_hs_m2s)
def lru_cache(maxsize=128):
def tmp_func(func):
return func
return tmp_func
def isclose(a, b, rel_tol=1e-09, abs_tol=0.0):
"Return true if numbers a and b are close to each other."
return abs(a - b) <= max(rel_tol * max(abs(a), abs(b)), abs_tol)
# ______________________________________________________________________________
# Misc Functions
# TODO: Use functools.lru_cache memoization decorator
def callable(obj):
return any("__call__" in klass.__dict__ for klass in type(obj).__mro__)
# --- stdlib additions
# py 3.2 functools.lru_cache
# Taken from: http://code.activestate.com/recipes/578078
# Credit: Raymond Hettinger
