每日分享
The struggle you're in today is developing the strength you need for tomorrow.
今天拼搏的是明天你需要的力量。
小闫语录:
没有无畏的奋斗,也没有无用的经历。现在所经历的都会成为将来你厚积薄发的蓄力,加油!
1.笔试题
1.1 哈希树
哈希树是专门优化查询效率的一种数据结构,这棵树查询效率极高,单论查询,要比二叉排序树快。
哈希树是通过质数分辨算法建立的,所以我们首先来看一下质数分辨算法。
质数是只能被1和它本身整除的数,所以2是最小的质数。在一篇论文中曾描述过质数分辨定理『n个不同的质数可以“分辨”的连续整数个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能有完全相同的余数序列』。
人们发现int类型最大能表示21亿个数,10个连续的质数能分辨的整数个数为 2*3*5*7*11*13*17*19*23*29=6464693230
这个数超过了21亿,也就是说任何数经过10次以内计算肯定能找到。这就是为什么它查询快了。
看完是不是一脸蒙蔽,我还是用一个小栗子来说一下这棵树吧。
一个数除以2,余数有几种?0和1,所以哈希树的第2层有两个叉。查询就是根据余数判别走哪条路,一个数先除以2,根据余数找到分叉,用商除以3,根据余数找到分叉,再用商除以5。。。。不断的除下去,直到根据余数找到对应的数,或者跟本找不到为空。这就是哈希树。
1.2链表和顺序表的区别
顺序表中元素存储位置是相邻连续的,是可以快速访问到任何元素的一种数据结构。一个顺序表在使用前必须指定好存储空间大小,一旦分配内存就不可轻易更改。优点就是查询快速,缺点是插入非尾端数据或删除非尾端数据麻烦。顺序表由两部分组成,一部分是元素集合,一部分是有关表整体情况的信息(主要包括元素存储区的容量和元素的个数)。实现的方式为一体式和分离式,顾名思义,以顺序表两部分的情况区分。python中的list就是利用分离式顺序表实现的。
顺序表的构建需要预先知道数据大小来申请连续的存储空间,而进行扩充的时候,又不得不进行数据的搬迁,使用起来不是很灵活。为了充分利用计算机的内存空间,实现灵活的内存动态管理,我们就用到了链表。链表作为一种基础的数据结构,与顺序表不同,它是通过指针来描述元素关系的一种数据结构。它保存元素的时候,内存空间可以是不连续的,每个节点保存元素和下一个元素的指针即可。优点显而易见,但是缺点也很明显,就是查找元素必须重头开始查找。
1.3用代码实现一个死锁
假如一个线程在未释放锁的情况下发生了意外终止响应,其他线程获取不到锁而一直等待,这就是造成了死锁。下面我们利用简单的几行代码来模拟一个死锁的情况:
import threading import time # 创建互斥锁 lock = threading.Lock() # 根据下标去取值, 保证同一时刻只能有一个线程去取值 def get_value(index): # 上锁 lock.acquire() print(threading.current_thread()) my_list = [3,6,8,1] # 判断下标释放越界 if index >= len(my_list): print("下标越界:", index) return value = my_list[index] print(value) time.sleep(0.2) # 释放锁 lock.release() if __name__ == '__main__': # 模拟大量线程去执行取值操作 for i in range(30): sub_thread = threading.Thread(target=get_value, args=(i,)) sub_thread.start()
死锁产生后,程序会发生停止响应,空耗资源。为了避免此种情况,我们需要在合适的地方释放锁。