[Python知识库] 数据检索二分查找法

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> Python知识库 -> 数据检索二分查找法 -> 正文阅读

[Python知识库]数据检索二分查找法

测试时间

主要是利用time这个包，并不复杂

import time
start=time.time()#开始时间

doubledata=0.0
for i in range(1000000):
	doubledata+=i
print(doubledata)
end=time.time()#结束时间
print("cost  time一共用了",end-start)

装饰器

我有一点点不明白，costtime里调用的func为啥是下面的函数func，但是装饰器的定义是把函数当做参数，所以我认为就是costtime里的func是下面func()参数，但看到下面的就晓得func只是一个变量名。


def  costtime(func): #装饰器，把函数当作参数，
    import time
    start=time.time()#开始时间
    func()
    end=time.time()#结束时间
    print("cost  time一共用了",end-start)

def  func():
    doubledata=0.0
    for i in range(1000000):
	    doubledata+=i
    print(doubledata)
costtime(func)

装饰器参数

加上了可输入的n


def  costtime(func,n): #装饰器，把函数当作参数，
    import time
    start=time.time()#开始时间
    func(n)
    end=time.time()#结束时间
    print("cost  time一共用了",end-start)

def  func(n):
    doubledata=0.0
    for i in range(n):
	    doubledata+=i
    print(doubledata)
costtime(func,1000000)

数据查询装饰器

我照着源代码敲了一遍，思路跟之前一样，只是多了很多步骤，一步一步的完成

class  CSDNfind:
    def __init__(self):#初始化函数
        self.file=open(r"C:\Users\Tsinghua-yincheng\Desktop\YinchengDay8\csdn.txt","rb")
        pass
    def  memload(self):
        self.memlist=self.file.readlines()#文件载入内存
        self.file.seek(0,0)#文件回到开头
    def  diskfind(self,findstr):#硬盘查询
        self.file.seek(0,0)#文件回到开头
        while  True:
            line =self.file.readline()
            if not  line: #为空跳出
                break
            line=line.decode("gbk",errors="ignore")#解码，
            linelist=line.split(" # ")#切割
            if  findstr==linelist[0]: #判断
                print(line)
                break #找到就退出

    def memfind(self,findstr):#内存查询
        for  line  in  self.memlist:  #遍历列表
            line=line.decode("gbk",errors="ignore")#解码，
            linelist=line.split(" # ")#切割
            if  findstr==linelist[0]: #判断
                print(line)
                break #找到就退出
    def findcosttime(self,func,findstr,searchtype):#查询时间
        import time
        start=time.time()#开始时间
        func(findstr)
        end=time.time()#结束时间
        print(searchtype,"cost  time一共用了",end-start)

    def __del__(self):#删除
        self.file.close()
        pass


csdn=CSDNfind()
csdn.findcosttime(csdn.diskfind,"yincheng01","硬盘")
csdn.findcosttime(csdn.diskfind,"yincheng0571","硬盘")


'''
csdn.memload()
print("内存载入完成")
csdn.findcosttime(csdn.memfind,"yincheng01","内存")
csdn.findcosttime(csdn.memfind,"yincheng0571","内存")
csdn.findcosttime(csdn.memfind,"yincheng","内存")
'''

行缓冲

linecache.updatecache:当文件内容发生改变时，如果需要获得到最新的文件内容，那么需要调用这个方法。如果不调用，仍然使用在缓存中的老文件内容。类似的操作还可以是linecache.clearcache之后再getlines也行。

import  os
import  linecache
#linecache仅仅处理utf-8编码文件，
#随机跳到哪一行
path=r"C:\Users\Tsinghua-yincheng\Desktop\YinchengDay8\csdnmail.txt"
linecache.updatecache(path) #抓取路径进行预处理
print("OK")
mylist=linecache.getlines(path)[2500000:2500100]#列表，抓取2500000-2500100
print(mylist)

二分查找

方法：考研的时候算是最简单的一种，先排序，最左最右取个中间值，比大小，所到范围之中后，再取中间值一直如此

def   search2(finddata,findlist):
    low=0 #第一个
    high=len(findlist)-1 #最后一个
    while low  <=  high: #重合跳出循环
        mid=(low+high)//2 #取得索引中间值
        midata=findlist[mid]#取得中间值
        if finddata<midata:
            high=mid-1  #移动位置
        elif finddata >midata:
            low=mid+1   #移动位置
        else:
            print("找到",finddata,mid)
            return mid
    print("找不到")
    return -1

def  search(finddata,findlist):
    for data in findlist:
        if data==finddata:
            print(data,"找到")
    return 0


def  costtime(func,finddata,findlist):
    import time
    start=time.time()#开始时间
    func(finddata,findlist)
    end=time.time()#结束时间
    print("cost  time一共用了",end-start)

findlist=[x for x in range(100000000)]
finddata=98000000
costtime(search2,finddata,findlist)
costtime(search,finddata,findlist)

内存检索二分查找法

将原本for循环的方式改为二分法

def  getuser(line):
      line=line.decode("gbk",errors="ignore")#解码，
      linelist=line.split(" # ")#切割
      return linelist[0] #抓取用户名


class  CSDNfind:
    def __init__(self):#初始化函数
        self.file=open(r"C:\Users\Tsinghua-yincheng\Desktop\YinchengDay8\csdn.txt","rb")
        pass
 
    def  memload(self):
        self.memlist=self.file.readlines()#文件载入内存
        self.file.seek(0,0)#文件回到开头
    def  memsort(self):
        self.memlist.sort(key = lambda x:getuser(x))#根据user排序

    def memsearch2(self,findstr):
        low=0
        high=len(self.memlist)-1
        while  low<=high:
            mid=(low+high)//2

            line=self.memlist[mid]
            line=line.decode("gbk",errors="ignore")#解码，
            linelist=line.split(" # ")
            midstr=linelist[0] #对比user
            
            if findstr<midstr:
                high=mid-1
            elif findstr>midstr:
                low=mid+1
            else:
                print("找到",mid,line)
                return mid

        print("找不到")
        return -1





    def  diskfind(self,findstr):#硬盘查询
        self.file.seek(0,0)#文件回到开头
        while  True:
            line =self.file.readline()
            if not  line: #为空跳出
                break
            line=line.decode("gbk",errors="ignore")#解码，
            linelist=line.split(" # ")#切割
            if  findstr==linelist[0]: #判断
                print(line)
                break #找到就退出

    def memfind(self,findstr):#内存查询
        for  line  in  self.memlist:  #遍历列表
            line=line.decode("gbk",errors="ignore")#解码，
            linelist=line.split(" # ")#切割
            if  findstr==linelist[0]: #判断
                print(line)
                break #找到就退出
    def findcosttime(self,func,findstr,searchtype):#查询时间
        import time
        start=time.time()#开始时间
        func(findstr)
        end=time.time()#结束时间
        print(searchtype,"cost  time一共用了",end-start)

    def __del__(self):#删除
        self.file.close()
        pass

csdn=CSDNfind()
csdn.memload()
csdn.findcosttime(csdn.memfind,"yincheng01","内存")
csdn.findcosttime(csdn.memfind,"yincheng0571","内存")
csdn.findcosttime(csdn.diskfind,"yincheng01","硬盘")
csdn.findcosttime(csdn.diskfind,"yincheng0571","硬盘")
csdn.memsort()
print("排序完成")
csdn.findcosttime(csdn.memsearch2,"yincheng01","内存 2分")
csdn.findcosttime(csdn.memsearch2,"yincheng0571","内存 2分")



'''
csdn=CSDNfind()
csdn.findcosttime(csdn.diskfind,"yincheng01","硬盘")
csdn.findcosttime(csdn.diskfind,"yincheng0571","硬盘")
'''



'''
csdn.memload()
print("内存载入完成")
csdn.findcosttime(csdn.memfind,"yincheng01","内存")
csdn.findcosttime(csdn.memfind,"yincheng0571","内存")
csdn.findcosttime(csdn.memfind,"yincheng","内存")
'''

不消耗内存的二分查找法

90g文件0.0s完成查询

#6428632
def   search2(findstr):
    low=0  #开始
    high=6428632-1 #结束
    while low<=high:
        mid= (low+high)//2
        indexfile.seek(10*(mid),0)#跳到索引的位置
        midval=indexfile.read(10)#读取10个字符
        midval=eval(midval)#取出索引数据

        csdnfile.seek(midval,0)#调到这个索引
        line=csdnfile.readline()#读取一行
        line=line.decode("gbk",errors="ignore")#解码，
        linelist=line.split(" # ")#切割
        midstr=linelist[0]


        #midstr=None

        if findstr>midstr:
            low=mid+1
        elif findstr <midstr:
            high=mid-1
        else:
            print("找到",mid,   line)
            return mid



    print("没有找到")
    return -1





csdnfile=open(r"C:\Users\Tsinghua-yincheng\Desktop\YinchengDay8\csdnsort.txt","rb")
indexfile=open(r"C:\Users\Tsinghua-yincheng\Desktop\YinchengDay8\csdnsortindex.txt","rb")

while True:
    mystr=input("输入要查找的数据")
    import time
    start=time.time()#开始时间
    search2( mystr)
    end=time.time()#结束时间
    print("cost  time一共用了",end-start)
csdnfile.close()
indexfile.close()