最近用Python完成了一个改进后的二分法搜索函数,能返回双键排序后嵌套序列的切片,感觉效果和效率不错,跟大家分享。
输入数据是从Sqlite3数据库查询来的,源库是家谱数据,查询得到的表data4tree包括字段name,gender,father,ranking,generation,wife,分别是姓名、性别、父亲、排行、世代和配偶。
目标是通过父亲查询,返回其所有子女列表,函数def findChildren(father,allrecs) -> list。返回的子女是按照排行排过序的,方便使用。
准备数据的代码如下:
conn = sqlite3.connect('.\FamilyTree.db') curs = conn.cursor() fb="南村张氏族谱" #库中还有其他族谱数据 curs.execute("SELECT name,gender,father,ranking,generation,wife FROM {tbl} where fb={fb} order by {orderby}".format(tbl='data4tree',orderby='father,ranking')) #结果双键排序 allrecs=curs.fetchall() conn.close()
结果集allrecs中的数据是由数千个元组组成的列表,每个元组包括姓名、性别、父亲、排行、世代和配偶。列表中的数据先按father排序,father相同的再按排行ranking排序。父亲名字已经过处理,没有重名的。故称双排序。
通常的二分法算法,处理的输入数据都不是嵌套的,且返回的都是找到的元素的起始位置。
当相同元素不止一个时,常用bisect模块的方法bisect_left和bisect_right,获得起始地址,然后再切片得到最终的子女列表。这种方法的效率并不高,尤其数据量很大时。
这里实现的二分法搜索,直接返回需要的子女序列,且效率高。
def findChildren(father,allrecs) -> list: # 先找下限 left = 0 start=0 end=0 RIGHT = len(allrecs) - 1 right = RIGHT while left < right: mid = (left + right) // 2 if father <= allrecs[mid][2]: right = mid else: left = mid + 1 if father != allrecs[left][2]: return [] start=left if left == RIGHT: return [allrecs[left:left]] # 再找上限 right = RIGHT # left是下限, 在left到RGHT范围中找 while left < right: mid = (left + right) // 2 + 1 if father >= allrecs[mid][2]: left = mid else: right = mid - 1 end=right return allrecs[start:end+1] #返回切片
调用上述函数:
childrenlist=findChildren("拴林",allrecs),则返回"拴林"六个孩子从大到小的元组(姓名、性别、父亲、排行、世代、配偶)列表。
经过timeit测试,该函数的效率明显高于采用bisect模块的方法bisect_left和bisect_right。原因是,找上限索引时,没有重新开始,而是在剩下的数据中查找,自然节省了时间。
使用场景,该函数可以用于家谱数据在TreeView中的显示。通过父亲能够找到,所有子女。
以上就是“利用python二分法编程,在族谱中搜索父亲的所有子女”的详细内容,想要了解更多Python教程或者资讯欢迎持续关注编程学习网
扫码二维码 获取免费视频学习资料
- 本文固定链接: http://phpxs.com/post/8941/
- 转载请注明:转载必须在正文中标注并保留原文链接
- 扫码: 扫上方二维码获取免费视频资料