在很多的python库之中,我们可以看到有的时候,库作者会使用一些很特殊的“列表”或者“字典”。虽然他们看起来很像是一个列表或者字典,但是使用的方法却又不一样,这是因为那不是真的python中原本的列表和字典,而是作者自己创建的。那么,我们如何可以创建我们自己的列表和字典呢?
前后都使用两个下划线的方法,一般被称之为魔法方法,比如我们常见的 init ,就是一种魔法方法。一般来说,我们自行定义变量名的时候,不要定义很像是魔法方法的变量名。魔法方法被定义后,可以在适当的时候自动被调用,一般不需要手动对其进行调用。
在python中,实现一个序列,我们需要以下四种魔法方法
另外,一般来说,错误的键应当引发TypeError异常,而错误的索引应当引发IndexError异常
在python的列表中,只能够使用数字作为索引,如果使用字符串的数字的话,那么会引发异常。因此,我们可以尝试一下,对原始的列表进行扩充,使其可以接受字符串作为列表的索引。
注意,这样的自建列表,存在很多问题,几乎全部的关于列表的方法都不能再被使用了。
为了解决正常列表的方法不能再被使用,我们可以考虑直接继承list,以此得到普通列表的所有方法。
dict对象是Python中一个原始的数据类型,按照键值对的方式存储,中文名为字典,其通过键名查找对应的值有很高的效率,时间复杂度在常数级别O(1)。Python dict的底层是依靠哈希表(Hash Table)进行实现的,使用开放地址法解决冲突。所以其查找的时间复杂度会是O(1),why?
哈希表是key-value类型的数据结构,通过关键码值直接进行访问。通过散列函数进行键和数组的下标映射从而决定该键值应该放在哪个位置,哈希表可以理解为一个键值需要按一定规则存放的数组,而哈希函数就是这个规则。
算法中时间和空间是不能兼得的,哈希表就是一种用合理的时间消耗去减少大量空间消耗的操作,这取决于具体的功能要求。
创建一个数组,数组下标是索引号,数组中的值是要获得的数据,这样只需要O(1)的时间复杂度就可以完成操作,但是扩展性不强,有以下两个方面的考虑:
-1- 新添加的元素超出数组索引范围,这就需要重新申请数组进行迁移操作。
-2- 假设一种极端的情况:只存在两个元素,索引号分别是1和100000000001,按照先前的设计思路,会浪费很大的存储空间。
会不会存在一个方法,为已有的索引创建新的索引,通过压缩位数,让新索引可以和原有的大范围的稀疏索引进行一一对应,新索引所需要的存储空间要大大减小,这就是哈希思想。
上面的例子中哈希函数的设计很随意,但是从这个例子中我们也可以得到信息:
哈希函数就是一个映射,因此哈希函数的设定很灵活,只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围之内即可;
因为新的索引对旧的索引进行了空间上的压缩,所以不可能所有的输入都只对应唯一一个输出,也就是哈希函数式有可能发生冲突的,哈希函数不可能做成一对一的映射关系,其本质是一个多对一的映射。
直接定址法:很容易理解,key=Value+C; 这个“C”是常量。Value+C其实就是一个简单的哈希函数。
除法取余法: 很容易理解, key=value%C解释同上。
数字分析法:这种蛮有意思,比如有一组value1=112233,value2=112633,value3=119033,针对这样的数我们分析数中间两个数比较波动,其他数不变。那么我们取key的值就可以是key1=22,key2=26,key3=90。
平方取中法。此处忽略,见名识意。
折叠法:这种蛮有意思,比如value=135790,要求key是2位数的散列值。那么我们将value变为13+57+90=160,然后去掉高位“1”,此时key=60,哈哈,这就是他们的哈希关系,这样做的目的就是key与每一位value都相关,来做到“散列地址”尽可能分散的目地。
当两个不同的数据元素的哈希值相同时,就会发生冲突。解决冲突常用的手法有2种:
开放地址法:
如果两个数据元素的哈希值相同,则在哈希表中为后插入的数据元素另外选择一个表项。当程序查找哈希表时,如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素,程序就会继续往后查找,直到找到一个符合查找要求的数据元素,或者遇到一个空的表项。
链接法:
将哈希值相同的数据元素存放在一个链表中,在查找哈希表的过程中,当查找到这个链表时,必须采用线性查找方法。
python的dict采用了哈希表,最低能在 O(1)时间内完成搜索,在发生哈希冲突的时候采用的是开放寻址法。java的HashMap也是采用了哈希表实现,但是在发生哈希冲突的时候采用的是链接法。
下面是一个使用 Python 的字典和列表来实现学生成绩管理的简单例子。此例子实现了所有要求,但没有使用定义学生结构体类型和数组:
# 定义学生数据字典
students = []
# 定义输入函数
def input_student():
while True:
student = {}
student['id'] = input('学号: ')
student['class'] = input('班级: ')
student['name'] = input('姓名: ')
student['scores'] = []
for i in range(3):
score = input('第%d门课程成绩: ' % (i + 1))
student['scores'].append(score)
students.append(student)
if input('是否继续输入(y/n): ') != 'y':
break
# 定义求平均分函数
def average_score():
for student in students:
total = 0
for score in student['scores']:
total += score
student['average'] = total / len(student['scores'])
# 定义求最高平均分函数
def max_average():
max_student = None
max_average = 0
for student in students:
if student['average'] >max_average:
max_student = student
max_average = student['average']
return max_student
# 调用输入函数
input_student()
# 调用求平均分函数
average_score()
# 输出每个学生的3门课程平均分
for student in students:
print('学号: %s, 班级: %s, 姓名: %s, 平均分: %.2f' % (student['id'], student['class'], student['name'], student['average']))
# 调用求最高平均分函数
max_student = max_average()
# 输出最高平均分的学生信息
if max_student:
print('\n平均分最高的学生: 学号: %s, 班级: %s, 姓名: %s, 3门课程成绩: %s, 平均分: %.2f' % (max_student['id'], max_student['class'], max_student['name'], max_student['scores'], max_student['average']))
在上面的例子中,我们定义了一个学生数据字典,用于存储学生信息。然后定义了三个函数,分别用于输入学生信息、求每个学生3门课程的平均分和求平均分最高的学生。最后,在主函数中调用这三个函数,并输出结果。