【CS61A】CS61A——Decomposition

Decomposition

Modular Design

程序的设计原则：将程序的不同部分分离开来，使得每个模块可以独立开发与测试 以以下餐厅搜索代码为例，实现从文件中读取评分与评论（使用similarity评估相似性）搜索对应评分前k个餐厅去过的其他餐厅的功能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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))

优化时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13

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