2019.1.27 fib 相关 demo 增加

wingfish · wingfish · commit 9c597b667cd2 · 2019-01-27T22:44:54.000+08:00
diff --git a/fib/cache.py b/fib/cache.py
@@ -0,0 +1,134 @@
+import pickle
+import time
+import inspect
+import base64
+import hashlib
+
+
+debug = False
+
+
+def log(s):
+    if debug:
+        print(s)
+
+
+caches = dict()
+updated_caches = []
+
+
+def get_cache(fname):
+    if fname in caches:
+        return caches[fname]
+    try:
+        with open(fname, "rb") as f:
+            c = pickle.load(f)
+    except:
+        c = dict()
+    caches[fname] = c
+    return c
+
+
+def write_to_cache(fname, obj):
+    updated_caches.append(fname)
+    caches[fname] = obj
+
+
+def cleanup():
+    for fname in updated_caches:
+        with open(fname, "wb") as f:
+            pickle.dump(caches[fname], f)
+
+
+def get_fn_hash(f):
+    return base64.b64encode(hashlib.sha1(inspect.getsource(f).encode("utf-8")).digest())
+
+
+NONE = 0
+ARGS = 1
+KWARGS = 2
+
+
+def cache(fname=".cache.pkl", timeout=-1, key=ARGS | KWARGS):
+
+    def impl(fn):
+        load_t = time.time()
+        c = get_cache(fname)
+        log("loaded cache in {:.2f}s".format(time.time() - load_t))
+
+        def d(*args, **kwargs):
+            log("checking cache on {}".format(fn.__name__))
+            if key == ARGS | KWARGS:
+                k = pickle.dumps((fn.__name__, args, kwargs))
+            if key == ARGS:
+                k = pickle.dumps((fn.__name__, args))
+            if key == KWARGS:
+                k = pickle.dumps((fn.__name__, kwargs))
+            if key == NONE:
+                k = pickle.dumps((fn.__name__))
+            if k in c:
+                h, t, to, res = c[k]
+                if get_fn_hash(fn) == h and (to < 0 or (time.time() - t) < to):
+                    log("cache hit.")
+                    return res
+            log("cache miss.")
+            res = fn(*args, **kwargs)
+            c[k] = (get_fn_hash(fn), time.time(), timeout, res)
+            save_t = time.time()
+            write_to_cache(fname, c)
+            log("saved cache in {:.2f}s".format(time.time() - save_t))
+            return res
+
+        return d
+
+    return impl
+
+
+@cache(timeout=0.2)
+def expensive(k):
+    time.sleep(0.2)
+    return k
+
+
+@cache(key=KWARGS)
+def expensive2(k, kwarg1=None):
+    time.sleep(0.2)
+    return k
+
+
+def test():
+    # Test timeout
+    t = time.time()
+    v = expensive(1)
+    assert v == 1
+    assert time.time() - t > 0.1
+    t = time.time()
+    expensive(1)
+    assert time.time() - t < 0.1
+    time.sleep(0.3)
+    t = time.time()
+    expensive(1)
+    assert time.time() - t > 0.1
+    t = time.time()
+    v = expensive(2)
+    assert v == 2
+    assert time.time() - t > 0.1
+    # Test key=_ annotation
+    t = time.time()
+    v = expensive2(2, kwarg1="test")
+    assert v == 2
+    assert time.time() - t > 0.1
+    t = time.time()
+    v = expensive2(1, kwarg1="test")
+    assert v == 2
+    assert time.time() - t < 0.1
+    t = time.time()
+    v = expensive2(1, kwarg1="test2")
+    assert v == 1
+    assert time.time() - t > 0.1
+    cleanup()
+    print("pass")
+
+
+if __name__ == "__main__":
+    test()
diff --git a/fib/cache_fib.py b/fib/cache_fib.py
@@ -0,0 +1,18 @@
+from fib import cache
+import time
+
+
+@cache.cache(timeout=20, fname="my_cache.pkl")
+def fib(n):
+    if n <= 2:
+        return 1
+    else:
+        return fib(n - 1) + fib(n - 2)
+
+
+if __name__ == "__main__":
+    x = 47
+    start = time.time()
+    res = fib(x)
+    elapsed = time.time() - start
+    print("Python Computed fib(%s)=%s in %0.8f seconds" % (x, res, elapsed))
diff --git a/fib/diskcache_fib.py b/fib/diskcache_fib.py
@@ -0,0 +1,20 @@
+from diskcache import FanoutCache
+import time
+
+cache = FanoutCache('/tmp/diskcache/fanoutcache1')
+
+
+@cache.memoize(typed=True, expire=None, tag='fib')
+def fib(n):
+    if n <= 2:
+        return 1
+    else:
+        return fib(n - 1) + fib(n - 2)
+
+
+if __name__ == "__main__":
+    x = 47
+    start = time.time()
+    res = fib(x)
+    elapsed = time.time() - start
+    print("Python Computed fib(%s)=%s in %0.8f seconds" % (x, res, elapsed))
diff --git a/fib/fib.py b/fib/fib.py
@@ -0,0 +1,37 @@
+import time
+
+
+def fib(n):
+    if n <= 2:
+        return 1
+    else:
+        return fib(n - 1) + fib(n - 2)
+
+
+def cache_fib(n, _cache={}):
+
+    if n in _cache:
+        return _cache[n]
+    elif n > 1:
+        return _cache.setdefault(n, cache_fib(n-1) + cache_fib(n-2))
+    return n
+
+
+def pow_fib(n):
+    return pow(2 << n, n + 1, (4 << 2 * n) - (2 << n) - 1) % (2 << n)
+
+
+def ab_fib(n):
+    a, b = 1, 1
+    n = n-2
+    for i in range(n):
+        a, b = b, a+b
+    return b
+
+
+if __name__ == "__main__":
+    x = 47
+    start = time.time()
+    res = cache_fib(x)
+    elapsed = time.time() - start
+    print("Python Computed fib(%s)=%s in %0.8f seconds" % (x, res, elapsed))
diff --git a/fib/lru_fib.py b/fib/lru_fib.py
@@ -0,0 +1,20 @@
+import time
+from functools import lru_cache
+
+
+@lru_cache(maxsize=None)
+def fib(n):
+    if n <= 2:
+        return 1
+    else:
+        return fib(n - 1) + fib(n - 2)
+
+
+if __name__ == "__main__":
+    x = 47
+    start = time.time()
+    res = fib(x)
+    elapsed = time.time() - start
+    print("Python Computed fib(%s)=%s in %0.8f seconds" % (x, res, elapsed))
+    print(fib.cache_info())
+
