def fib(n):
    if n==0 or n==1:
        return n
    else:
        return fib(n-2)+fib(n-1)
def count(f):
    def counted(n):
        counted.call_count +=1
        return f(n)
    counted.call_count = 0
    return counted
def memo(f):
    cache={}
    def memoized(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return memoized
fib = count(fib)
counted_fib =fib
fib = memo(fib)
fib = count(fib)
print(fib(30))
print("origin:", fib.call_count, "memorized:", counted_fib.call_count)

%matplotlib inline
import matplotlib.pyplot as plt
plt.style.use('ggplot')
plt.rc('font', size = 16)

from timeit import repeat
from numpy import median, percentile

def plot_times(name, xs, n=15):
    f = lambda x: name+'('+str(x)+')'
    g = globals()

    samples = []
    for _ in range(n):
        times = lambda x: repeat(f(x), globals = g, number = 1, repeat = n)
        samples.append([median(times(x)) for x in xs])
    ys = [10e3*median(sample) for sample in zip(*samples)]

    plt.figure(figsize=(8, 8))
    plt.plot(xs, ys)
    plt.xlabel('n')
    plt.ylabel('ms')

def exp_fast(b,n):
    if n==0:
        return 1
    elif n%2==0:
        return square(exp_fast(b,n//2))
    else:
        return b*exp_fast(b, n-1)

def square(x):
    return x*x

exp_2_fast = lambda n: exp_fast(2.0, n)
plot_times('exp_2_fast', range(20, 1600, 10))

class Link:
    # 使用空元组实现空节点，类属性
    empty = ()
    def __init__(self, first, rest=empty):
        # 判断rest是否是空节点或是一个Link类
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest


s = Link(3, Link(4, Link(5)))
print(s.first)
print(s.rest.first)
print(s.rest.rest.first)
print(s.rest.rest.rest is Link.empty)

class Link:
    # 使用空元组实现空节点，类属性
    empty = ()
    def __init__(self, first, rest=empty):
        # 判断rest是否是空节点或是一个Link类
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest
def range_link(start, end):
    if start>=end:
        return Link.empty
    else:
        return Link(start, range_link(start+1, end))

def map_link(f, s):
    if s is Link.empty:
        return s
    else:
        return Link(f(s.first), map_link(f, s.rest))

def filter_link(f, s):
    if s is Link.empty:
        return s
    filter_rest = filter(f, s.rest)
    if f(s.first):
        return Link(s.first, filter_rest)
    else:
        return filter_rest

>>> s = Link(1, Link(2, Link(3)))
>>> s.first = 5
>>> t = s.rest
>>> t.rest = s;
>>> s.first
5
>>> s.rest.rest.rest.rest.rest.first
2

def add(s, v):
    assert s is not Link.empty
    if s.first > v:
        s.first, s.rest = v, Link(s.first, s.rest)
    elif s.first < v and s.rest is Link.empty:
        s.rest = Link(v)
    elif s.first < v:
        add(s.rest, v)
    return s

class Tree:
    def __init__(self, label, branches = []):
        self.label = label
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = list(branches)
    def __repr__(self):
        if self.branches:
            branches_str = ', '+ repr(self.branches)
        else:
            branch_str = ''
        return 'Tree({0}{1})'.format(repr(self.label), branch_str)
    def __str__(self):
        return '\n'.join(self.indented())

    def indented(self):
        lines = []
        for b in self.branches:
            for line in b.indented():
                lines.append('    '+line)
        return [str(self.label)] + lines
    def is_leaf(self):
        return not self.branches

def fib_tree(n):
    if n==0 or n==1:
        return Tree(n)
    else:
        left = fib_tree(n-2)
        right = fib_tree(n-1)
        fib_n = left.label + right.label
        return Tree(fib_n, [left, right])

def leaves(t):
    if t.is_leaf():
        return [t.label]
    else:
        all_leaves = []
        for b in t.branches:
            all_leaves.extend(leaves(b))
        return all_leaves

# 通过每次重新构建branches列表，将等于n的值排除在列表外以实现
def prune(t, n):
    t.branches = [b for b in t.branches if b.label!=n]
    for b in t.branches:
        prune(b, n)

def repr(x):
    return type(x).__repr__(x)

class Ratio:
    def __init__(self, n, d):
        self.numer = n
        self.denom = d

    def __repr__(self):
        return 'Ratio({0}, {1})'.format(self.numer, self.denom)
    def __str__(self):
        return '{0}/{1}'.format(self.numer, self.denom)

class Ratio:
    def __init__(self, n, d):
        self.numer = n
        self.denom = d

    def __repr__(self):
        return 'Ratio({0}, {1})'.format(self.numer, self.denom)
    def __str__(self):
        return '{0}/{1}'.format(self.numer, self.denom)
    def __add__(self, other):
        if isinstance(other, int):
            n = self.numer+self.denom*other
            d = self.denom
        elif isinstance(other, Ratio):
            n = self.numer*other.denom +self.denom*other.numer
            d = self.denom*other.denom
        elif isinstance(other, float):
            return float(self)+other
        g = gcd(n,d)
        return Ratio(n//g, d//g)
    __radd__ = __add__

    def __float__(self):
        return self.numer/self.denom

def gcd(n, d):
    while n!=d:
        n, d = min(n, d), abs(n-d)
    return n

# 类的继承
class CheckingAccount(Account):
    """A bank account that charges for withdrawals"""
    withdraw_fee = 1
    interest = 0.01
    def withdraw(self, amount):
        return Account.withdraw(self, amount + self.withdraw_fee)

ch = CheckingAccount('Tom')
print(ch.interest)
ch.deposit(20)
ch.withdraw(5)
print(ch.balance)

class Bank:
    """a bank has accounts"""
    def __init__(self):
     self.accounts=[]   # 账户列表

    def open_account(self, holder, amount, kind = Account):
        account = kind(holder)   # 创建某种类型的账户
        account.deposit(amount)   # 存入amount的钱
        self.accounts.append(account)   # 将创建的账户加入当前银行的账户列表
        return account

    def pay_interest(self):
        # 计算列表中的利息
        for a in self.accounts:
            a.deposit(a.balance*a.interest)

bank = Bank()
john = bank.open_account('john', 10)
jack = bank.open_account('jack', 5, CheckingAccount)
bank.pay_interest()
print(jack.balance)
print(john.balance)

# 类的多重继承
class SavingsAccount(Account):
    deposit_fee = 2
    def deposit(self, amount):
        return Account.deposit(self, amount-self.deposit_fee)
class GoodAccount(CheckingAccount, SavingsAccount):
    def __init__(self, account_holder):
        super().__init__(account_holder)
        self.holder = account_holder
        self.balance = 1

def search(query, ranking = lambda r: -r.stars):
    results  =[r for r in Restaurant.all if query in r.name]
    return sorted(results, key= ranking)
def reviewed_both(r, s):
    return len([x for x in r.reviewers if x in s.reviewers])
class Restaurant:
    all = []
    def __init__(self, name, star, reviewer):
        self.name = name
        self.star = star
        self.reviewer = reviewer
        Restaurant.all.append(self)

    def similar(self, k, similarity=reviewed_both):
        """Return the k most similar restaurants to self"""
        others = Restaurant.all
        others.remove(self)
        different = lambda r: -similarity(r, self)
        return sorted(others, key=different)[:k]


    def __repr__(self):
        return '<'+self.name+'>'

import json
reviewers_for_restaurant = {}
for line in open('reviews.json'):
    r = json.loads(line)
    biz = r['business_id']
    if biz not in reviewers_for_restaurant:
        reviewers_for_restaurant[biz] = [r['user_id']]
    else:
        reviewers_for_restaurant[biz].append(r['user_id'])
for line in open('restaurant.json'):
    r = json.loads(line)
    reviewers = reviewers_for_restaurant[r['business_id']]
    Restaurant(r['name'], r['stars'], reviewers)
results = search('Thai')
for r in results:
    print(r,'share reviewer with', r.similar(3))

def reviewed_both(r, s):
    return fast_overlap(r.reviewers, s.reviewers)

def fast_overlap(s, t):
    count, i, j = 0, 0, 0
    while i<len(s) and j<len(t):
        if s[i]==t[j]:
            count, i, j = count+1, i+1, j+1;
        elif s[i]<t[i]:
            i+=1
        else:
            j+=1
    return count