利用python二分法编程，在族谱中搜索父亲的所有子女

清华大佬耗费三个月吐血整理的几百G的资源，免费分享！....>>>

最近用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教程或者资讯欢迎持续关注编程学习网