优达学城《计算机科学导论》小结

[TOC]

简介

优达学城开设的《计算机科学导论》课程是“谷歌推荐的计算机科学学习路线”中推荐的入门导论课,与它同性质的还有斯坦福大学开设的《计算机科学入门》(目前coursera上已经没有了,但斯坦福网站有)。

整个课程以构建一个简单的网络搜索引擎(web search engine)为主线,介绍计算机是如何运作的(computing),以python语言为实现工具教学生如何写程序,进而引导学生入门计算机科学(computer science, CS)。

代码

课程所有代码均使用python 2.7,课程中遇到的代码传到了github:udacity_intro_to_CS_course_note

课程笔记

课程10怎样解决问题

通过一个问题:求两个日期间的天数,来说明如何解题,一般的解题步骤:

1.what’s the inputs?

2.outputs?

3.example by hand

4.simple mechanical solution

5.develop incrementally and test as we go

  • 不要过早优化,用人能想到的最简单的方法来做,效率差一点没有关系。
  • 先不考虑细节,保证函数接口不会变的前提下,给一个大致的实现也没关系。
  • 写的代码要方便测试

课程11怎样管理数据 unit3

2个要点:learning to crawl,structured data

1.string

2.list

<list>

[<expression>, <expression>,...]

nested lists

string不能直接改变:

1
2
3
>>> s='hello
>>> s[1]='j'
TypeError: 'str' object does not support item assignment

指向

1
2
3
4
5
p = ['h', 'e', 'l', 'l', 'o']
q = p
p[0] = 'y' # p改变的同时也会改变q
print p
print q
  • aliasing
  • 函数参数为列表时

要明白传的是引用,会改变原来spy的值

1
2
3
4
5
def replace_spy(spy):
spy[2] = spy[2] + 1
# 但是传整数的时候,不能改变原来的值
def inc(n):
n = n + 1
  • list operations

append

<list>.append(<element>)

+

len(<list>)

  • append的注意事项

q追加到p,是作为一个整体,并且改变p也会改变p中对应的部分

1
2
3
4
5
6
7
p = [1,2]
q = [3,4]
p.append(q)
print p
print len(p)
q[1] = 5
print p
  • 关于register和DRAM的两个类比做的很好

register是不需要刷新,而DRAM电荷会慢慢消失(所以需要不断刷新)

内存是DRAM,关机后所有数据都会丢失。(当然register也会)

latency - 12 nanoseconds

  • 平方
1
2 ** 10
  • 关于存储器速度

写程序的时候要让数据尽可能靠近cpu

  • loops on lists
1
2
3
4
while <test>:
<block>
for <name> in <list>:
<block>

返回value的index:<list>.index<value>

判断value是否在list中,返回True,False:<value> in <list>

<value> not in <list> = not <value> in <list>

  • pop

<list>.pop()

remove, return last

  • list的注意事项
1
2
def proc2(p):
p = p + [1]

原来p的值并不会改变,因为+会产生一个新的list

课程15 响应查询 unit4

主要内容:定义数据结构,以index为例子,讲解网络相关知识

  • split
  • 三引号
  • 网络

网络要点:

1.编码和解释

2.传递方式 route

3.谁使用

  • measuring networks

1.latency

2.band width

查看路由信息的命令:

windows: tracert

linux: traceroute

1
tracert www.baidu.com
  • protocols

课程18 程序怎样运行 unit5

目的:让程序运行更快

用dictionary来实现,其原理是hash

  • cost
  • time
1
2
import time
time.clock()
  • eval
1
eval(string) # 执行string
  • hash table
  • dictionary
  • ord
1
ord(<one-letter string>) -> number
  • chr
1
chr(<number>) -> <one-letter string>
  • chr(ord(a))=a
  • modulus operator
1
<number> % <modulus> -> <remainder>
  • making a better hash funciton

hash table的要点是每个bucket里面的元素数量尽量一致

  • for 中用range,防止while中忘记加1
1
2
3
4
5
def make_hashtable2(nbuckets):
table = []
for v in range(0, nbuckets):
table.append([])
return table
  • [[]]*3发生了什么?

三个元素都指向同一个地址

1
2
3
4
5
6
7
8
9
10
11
12
def make_hashtablewrong(nbuckets):
return [[]]*nbuckets
table = make_hashtablewrong(3)
table[1].append(['ud', ['http:']])
print table[1]
print table[0]
print table
# output
[['ud', ['http:']]]
[['ud', ['http:']]]
[[['ud', ['http:']]], [['ud', ['http:']]], [['ud', ['http:']]]]
  • dictionary
1
2
3
ele = {'hig':1,
'je':2}
print 'jj' in ele # 判断是否在里面

字典的key-value中,value可以多种类型,key呢?

字典的排序是靠hash值,参考

递归的最大深度,是多少?

深层递规一定要避免!一是不安全,二是调用代价高,三是cache对栈的效率低,四,这是最重要的--递规算法一定可以转为循环!

课程22如何拥有无穷力量 unit6

讲递归 recursive

定义:

1.base case

2.recursive case

python的递归是expensive(浪费资源)

fibonacii用递归会有很多重复的没有必要的计算,所以速度慢

  • 网页排名中如何找到质量高的网页?
  • relaxation algorithm

PageRank算法–从原理到实现

公式:
$$
rank(0,url) =1/N
$$

$$
rank(t, url) = (d*\sum_{p \in inlinks[url]}{rank(t-1, p) / outlinks[p]}) + (1-d)/N
$$

  • 弄明白数据结构很重要

  • 要掌握好递归是需要一些练习的

    1.找到结束条件

    2.找到前一个状态与后一个状态的关系

课程26 unit7

  • themes

abstraction

universality

recursive definitions

小结

这门课程只是一门入门课程,讲的东西非常简单,虽然在一开始说要构建一个搜索引擎的时候会觉得很厉害,等把课听了就会发现,搜索引擎其实是引用了python的一个包获取网页的内容,再写一些简单的程序就可以完成了,当然这是一个非常简陋的搜索引擎。

一路看下来就会发现主讲内容为:

  • python,很大一部分内容都是在讲python,应该说是用python,作者基本没有用python的特性,只用最基本的语法,目的就是尽量减少对语言特性的依赖,讲一般的编程思维。

  • 讲了一些编程思想,在如何解决问题那一节。

  • 讲了一些数据结构,主要是list、dictionary,构建搜索引擎的时候对它们进行了灵活运用。

  • 讲了递归,递归是一种思考方式,凡是递归写的程序都可以转换为循环,之所以用递归是因为递归的表达很容易让人看清问题的形式,写起来也简单。