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足够短,整个过程就很有效率。

numBuckets = 47  #this is ugly.  We will see a better way soon

def create():
    global numBuckets
    hSet = []
    for i in range(numBuckets):
        hSet.append([])
    return hSet

def hashElem(e):
    global numBuckets
    return e%numBuckets     

def insert(hSet, i):
    hSet[hashElem(i)].append(i)

#insert并不看element是不是已经存在,可能会存在很多次,所以要删除
def remove(hSet, i):
    newBucket = []
    for j in hSet[hashElem(i)]:
        if j != i:
            newBucket.append(j)
    hSet[hashElem(i)] = newBucket

def member(hSet, i):
    return i in hSet[hashElem(i)]

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.

def readVal(valType, requestMsg, errorMsg):
    numTries = 0
    while numTries < 4:
        val = raw_input(requestMsg)
        try:
            val = valType(val)
            return val
        except ValueError:
            print(errorMsg)
            numTries += 1
    raise TypeError('Num tries exceeded')
print readVal(int, 'Enter int: ', 'Not an int.')

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了

发表评论

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.