MIT600SC笔记10&11


第十课:Hashing and Classes

#我发现越往后的内容需要十分认真听才行

Hashing is how dictionaries are implemented in python. 牺牲space换取effeciency

例子:假设hashing是一套interger,有一个特定的interger在其中

hash(i)—->some interger in range(0,k)—>index into a list of lists(list当中的每个元素和对应的list称作bucket)—->找到i是否在bucket中

#找到第i个element的时间是恒定的,如果第一层list足够短,整个过程就很有效率。

Hash is many-to-one. Bucket是有限的,integer是无限的。两个element hash the same bucket, 就叫做collision。

解决collision的办法有很多,这里介绍Linear rehash.(并不是真的rehash,只是保存一个list)

好的hash有将value广泛分布的特性,可以将value放到不同的bucket里面。一般人都会将bucket的数量放大到足够大,因为可以假定找到第i个bucket的时间是恒定的,算法复杂度是O(1)。如果bucket只有一个,算法复杂度是O(n).

所有immutable的value都可以被hash(例如python中的int,float,turple,string)。这也是key为什么是immutable的原因,这样才能得到相同的hash结果。

程序总是把要hash的值变成一个integer,例如机场安检系统把人脸图像变成integer,string可以转化成ascii码。

下面要撇开算法和计算机科学讲一下python中的三个语法概念。exceptions, classes, iterators

Exception:
unhandled exceptions cause crash. Try……Except block.

Class:
Module – Collection of Related Functions (例如import math)
Class – data + Functions(operate on that data)—–>Object-oriented programms
data和function被称作这个object的attributes
Message passing metaphor—例如L.append(e),L执行append(e)
Method is a function associated with an object.
List和dict是python的bulit-in classes产生的type. 可以用外部的class扩展语言,增加语言的type

第十一课 OOP和继承

abstract data type

Interface – explains what methods do, not how they do it.

Specification — what that thing does

为什么不直接引用class中的data attribute,因为编程依据对built-in types的规范而不是实践。—> Data Hiding –> no direct access to instance variables and class variables

继承– Inherits properties of super class; can override properties of super class

一旦有了class,就可以考虑不用global variable了



发表评论

电子邮件地址不会被公开。 必填项已用*标注