# 创建哈希表
def make_hashtable(size):
table = []
for unused in range(0, size):
table.append([])
return table
# 计算哈希值
def hash_string(s, size):
h = 0
for c in s:
h = h + ord(c)
return h % size
# 获取key的值列表（条目）
def hashtable_get_bucket(htable, key):
return htable[hash_string(key, len(htable))]
# helper：获取条目
def get_entry(htable, key):
bucket = hashtable_get_bucket(htable, key)
for entry in bucket:
if entry[0] == key:
return entry
# 更新条目中的值
def hashtable_update(htable, key, value):
if get_entry(htable, key):
get_entry(htable, key)[1] = value
hashtable_get_bucket(htable, key).append([key, value])
# 查找值
def hashtable_lookup(htable, key):
if get_entry(htable, key):
return get_entry(htable, key)[1]
return None
# test_case
table = make_hashtable(10)
hashtable_update(table, 'Python', 'Monty')
hashtable_update(table, 'CLU', 'Barbara Liskov')
hashtable_update(table, 'JavaScript', 'Brendan Eich')
hashtable_update(table, 'Python', 'Guido van Rossum')
print hashtable_lookup(table, 'Python')
#>>> Guido van Rossum
# 读取网页数据
#def get_page(url):
# try:
# import urllib
# return urllib.urlopen(url).read()
#except:
# return ''
# 获取所有链接，通过索引存储数据
## 获取第一个链接和该链接结束位置
def get_next_target(page):
start_link = page.find(('<a href='))
if start_link == -1:
return None, 0
start_quote = page.find('"', start_link)
end_quote = page.find('"', start_quote + 1)
url = page[start_quote + 1:end_quote]
return url, end_quote
## 通过循环，获取当前页面的所有链接
def get_all_links(page):
links = []
while True:
url, end_quote = get_next_target(page)
if url:
links.append(url)
page = page[end_quote:]
else:
break
return links
## 创建关键字、链接、点击量的索引
### index-->[[keyword,[[url,num],...]],...]
### helper:记录用户点击数
def record_user_click(index, keyword, url):
urls = lookup(index, keyword)
if url:
for entry in urls:
if entry[0] == url:
entry[1] = entry[1] + 1
### helper:增：添加链接和关键字至索引
def add_to_index(index, keyword, url):
if keyword in index and url not in index[keyword]:
index[keyword].append(url)
else:
index[keyword] = [url]
def add_page_to_index(index, url, content):
words = content.split()
for word in words:
add_to_index(index, word, url)
## 爬取所有链接
### helper:合并两个列表，并排除重复项
def union(p, q):
for e in q:
if e not in p:
p.append(e)
def crawl_web(seed, max_depth):
tocrawl = [seed] # 待爬取
crawled = [] # 已爬取
next_page = [] # 本层链接列表
depth = 0 #爬取层数
index = {} # 关键字索引
while tocrawl and depth <= max_depth:
page = tocrawl.pop()
if page not in crawled:
content = get_page(page)
add_page_to_index(index, page, content)
union(next_page, get_all_links(content))
crawled.append(page)
if not tocrawl:
tocrawl, next_page = next_page, []
depth += 1
return index
# 查找
def lookup(index, keyword):
if keyword in index:
return index[keyword]
else:
return None
# %%timeit
# test_case
def get_page(url):
try:
if url == "http://www.udacity.com/cs101x/index.html":
return '''<html> <body> This is a test page for learning to crawl!
<p> It is a good idea to
<a href="http://www.udacity.com/cs101x/crawling.html">
learn to crawl</a> before you try to
<a href="http://www.udacity.com/cs101x/walking.html">walk</a> or
<a href="http://www.udacity.com/cs101x/flying.html">fly</a>.</p></body></html>'''
elif url == "http://www.udacity.com/cs101x/crawling.html":
return '''<html> <body> I have not learned to crawl yet, but I am
quite good at <a href="http://www.udacity.com/cs101x/kicking.html">kicking</a>.
</body> </html>'''
elif url == "http://www.udacity.com/cs101x/walking.html":
return '''<html> <body> I cant get enough
<a href="http://www.udacity.com/cs101x/index.html">crawling</a>!</body></html>'''
elif url == "http://www.udacity.com/cs101x/flying.html":
return '<html><body>The magic words are Squeamish Ossifrage!</body></html>'
except:
return ""
return ""
#print get_page('http://www.udacity.com/cs101x/index.html')
#print crawl_web('http://www.udacity.com/cs101x/index.html', 0)
#index = crawl_web('http://www.udacity.com/cs101x/index.html',10)
#print lookup(index, 'good')
#record_user_click(index, 'good', 'http://www.udacity.com/cs101x/crawling.html')
#print lookup(index, 'good')
# 改写crawl_web，使返回index和graph
def crawl_web(seed):
tocrawl = [seed]
crawled = []
index = {}
graph = {} # url:[list of pages it links to]
while tocrawl:
page = tocrawl.pop()
if page not in crawled:
content = get_page(page)
add_page_to_index(index, page, content)
outlinks = get_all_links(content)
graph[page] = outlinks
union(tocrawl, outlinks)
crawled.append(page)
return index, graph
# 计算排名
def compute_ranks(graph):
d = 0.8 # damping factor
numloops = 10
ranks = {}
npages = len(graph)
for page in graph:
ranks[page] = 1.0/npages
for i in range(0, numloops):
newranks = {}
for page in graph:
newrank = (1 - d) / npages
for node in graph:
if page in graph[node]:
newrank = newrank + d*ranks[node]/len(graph[node])
newranks[page] = newrank
ranks = newranks
return ranks
# 搜索获得最佳网页
def lucky_search(index, ranks, keyword):
pages = lookup(index, keyword)
if not pages:
return None
best_page = pages[0]
for candidate in pages:
if ranks[candidate] > ranks[best_page]:
best_page = candidate
return best_page
# 随机选取中间值，将小于等于它的列入左列表，大于它的列入右列表，逐层分解，最后
# 按照左列表+中间值+右列表的方式，逐层合并。
# 需要用到递归。简单起见，取第一个值为中间值
def quicksort(urls,ranks):
if len(urls) < 2:
return urls
pivot = urls[0]
lower = []
greater = []
for url in urls[1:]:
if ranks[url] >= ranks[pivot]:
lower.append(url)
else:
greater.append(url)
return quicksort(lower, ranks) + [pivot] + quicksort(greater, ranks)
def ordered_search(index, ranks, keyword):
if keyword not in index:
return None
return quicksort(index[keyword], ranks)
# test_case
cache = {
'http://udacity.com/cs101x/urank/index.html': """<html>
<body>
<h1>Dave's Cooking Algorithms</h1>
<p>
Here are my favorite recipes:
<ul>
<li> <a href="http://udacity.com/cs101x/urank/hummus.html">Hummus Recipe</a>
<li> <a href="http://udacity.com/cs101x/urank/arsenic.html">World's Best Hummus</a>
<li> <a href="http://udacity.com/cs101x/urank/kathleen.html">Kathleen's Hummus Recipe</a>
</ul>
For more expert opinions, check out the
<a href="http://udacity.com/cs101x/urank/nickel.html">Nickel Chef</a>
and <a href="http://udacity.com/cs101x/urank/zinc.html">Zinc Chef</a>.
</body>
</html>
""",
'http://udacity.com/cs101x/urank/zinc.html': """<html>
<body>
<h1>The Zinc Chef</h1>
<p>
I learned everything I know from
<a href="http://udacity.com/cs101x/urank/nickel.html">the Nickel Chef</a>.
</p>
<p>
For great hummus, try
<a href="http://udacity.com/cs101x/urank/arsenic.html">this recipe</a>.
</body>
</html>
""",
'http://udacity.com/cs101x/urank/nickel.html': """<html>
<body>
<h1>The Nickel Chef</h1>
<p>
This is the
<a href="http://udacity.com/cs101x/urank/kathleen.html">
best Hummus recipe!
</a>
</body>
</html>
""",
'http://udacity.com/cs101x/urank/kathleen.html': """<html>
<body>
<h1>
Kathleen's Hummus Recipe
</h1>
<p>
<ol>
<li> Open a can of garbanzo beans.
<li> Crush them in a blender.
<li> Add 3 tablespoons of tahini sauce.
<li> Squeeze in one lemon.
<li> Add salt, pepper, and buttercream frosting to taste.
</ol>
</body>
</html>
""",
'http://udacity.com/cs101x/urank/arsenic.html': """<html>
<body>
<h1>
The Arsenic Chef's World Famous Hummus Recipe
</h1>
<p>
<ol>
<li> Kidnap the <a href="http://udacity.com/cs101x/urank/nickel.html">Nickel Chef</a>.
<li> Force her to make hummus for you.
</ol>
</body>
</html>
""",
'http://udacity.com/cs101x/urank/hummus.html': """<html>
<body>
<h1>
Hummus Recipe
</h1>
<p>
<ol>
<li> Go to the store and buy a container of hummus.
<li> Open it.
</ol>
</body>
</html>
""",
}
def get_page(url):
if url in cache:
return cache[url]
else:
return None
index , graph = crawl_web('http://udacity.com/cs101x/urank/index.html')
if 'http://udacity.com/cs101x/urank/index.html' in graph:
print graph['http://udacity.com/cs101x/urank/index.html']
#>>> ['http://udacity.com/cs101x/urank/hummus.html',
#'http://udacity.com/cs101x/urank/arsenic.html',
#'http://udacity.com/cs101x/urank/kathleen.html',
#'http://udacity.com/cs101x/urank/nickel.html',
#'http://udacity.com/cs101x/urank/zinc.html']
index, graph = crawl_web('http://udacity.com/cs101x/urank/index.html')
ranks = compute_ranks(graph)
print ranks
#>>> {'http://udacity.com/cs101x/urank/kathleen.html': 0.11661866666666663,
#'http://udacity.com/cs101x/urank/zinc.html': 0.038666666666666655,
#'http://udacity.com/cs101x/urank/hummus.html': 0.038666666666666655,
#'http://udacity.com/cs101x/urank/arsenic.html': 0.054133333333333325,
#'http://udacity.com/cs101x/urank/index.html': 0.033333333333333326,
#'http://udacity.com/cs101x/urank/nickel.html': 0.09743999999999997}
print lucky_search(index, ranks, 'Hummus')
#>>> http://udacity.com/cs101x/urank/kathleen.html
print lucky_search(index, ranks, 'the')
#>>> http://udacity.com/cs101x/urank/nickel.html
print lucky_search(index, ranks, 'babaganoush')
#>>> None
print ordered_search(index, ranks, 'Hummus')
#>>> ['http://udacity.com/cs101x/urank/kathleen.html',
# 'http://udacity.com/cs101x/urank/nickel.html',
# 'http://udacity.com/cs101x/urank/arsenic.html',
# 'http://udacity.com/cs101x/urank/hummus.html',
# 'http://udacity.com/cs101x/urank/index.html']
print ordered_search(index, ranks, 'the')
#>>> ['http://udacity.com/cs101x/urank/nickel.html',
# 'http://udacity.com/cs101x/urank/arsenic.html',
# 'http://udacity.com/cs101x/urank/hummus.html',
# 'http://udacity.com/cs101x/urank/index.html']
print ordered_search(index, ranks, 'babaganoush')
#>>> None
## 编写一个迭代器
class FibIterable:
"""
this class is a generates a well known sequence of numbers
"""
def __init__(self,iLast=1,iSecondLast=0,iMax=50):
self.iLast = iLast
self.iSecondLast = iSecondLast
self.iMax = iMax #cutoff
def __iter__(self):
return self # because the object is both the iterable and the itorator
def next(self):
iNext = self.iLast + self.iSecondLast
if iNext > self.iMax:
raise StopIteration()
self.iSecondLast = self.iLast
self.iLast = iNext
return iNext
o = FibIterable()
for i in o:
print(i)