004.02 各类搜寻的算法

建檔日期: 2019/12/08

更新日期: None

相关软件信息:

说明：所有内容欢迎引用，只需注明来源及作者，本文内容如有错误或用词不当，敬请指正.

主题: 004.02 各类搜寻的算法

搜索算法

搜索算法旨在检查元素或从存储它的任何数据结构中检索元素。根据搜索操作的类型，这些算法通常分为两类：

顺序搜索：在此顺序搜索列表或数组，并检查每个元素。例如：线性搜索。

间隔搜索：这些算法是专门为搜索排序的数据结构而设计的。这些类型的搜索算法比线性搜索有效得多，因为它们反复瞄准搜索结构的中心并将搜索空间分成两半。例如：二进制搜索。

以下为各种算法在一万笔数据中搜索一万笔数据的索引所需时间, 以及代码.

结果:

0:00:09.563429 : Linear
0:00:00.400960 : Binary
0:00:00.372005 : Jump
0:00:00.273269 : Exponential
0:00:00.070810 : FibMonaccian
0:00:00.010970 : Inerpolation

代码:

from datetime import datetime
from math import sqrt
import random
import copy

size        = 10000
data        = [i for i in range(size)]
db          = random.sample(range(size), size)
db_sort     = copy.deepcopy(db)
db_sort.sort()

def call(func):
    start_time = datetime.now()
    for i in range(size):
        index = func(data[i], db_sort)
    print(datetime.now() - start_time,':',func.__name__)

def do_something(value):
    for i in range(1000):
        pass

def Binary(value, db, offset=0):
    length = len(db)
    index = int(length/2)
    if length == 0: return None
    value2 = db[index]
    if value == value2:
        return index + offset
    elif value > value2:
        return Binary(value, db[index+1:], offset=offset+index+1)
    elif value < value2:
        return Binary(value, db[:index], offset=offset)

def Exponential(value, db):
    length = len(db)
    if length == 0: return None
    if value == db[0]:
        return 0
    i = 1
    while (i<length) and (db[i]<=value):
        i = i*2
    index = Binary(value, db[int(i/2):min(i, length)])
    if index == None: return None
    return int(i/2)+index

def FibMonaccian(value, db):
    length = len(db)
    if length == 0: return None
    f2 = 0
    f1 = 1
    f  = f1 + f2
    while f<length:
        f2 = f1
        f1 = f
        f  = f1 + f2
    offset = -1
    while f>1:
        i = min(offset+f2, length-1)
        if value > db[i]:
            f  = f1
            f1 = f2
            f2 = f - f1
            offset = i
        elif value < db[i]:
            f  = f2
            f1 = f1-f2
            f2 = f -f1
        else:
            return i
    if f2 and (db[offset+1]==value): return offset+1
    return None

def Inerpolation(value, db):
    length = len(db)
    if length == 0: return None
    start = 0
    stop  = length-1
    while (start<=stop) and (value>=db[start]) and (value<=db[stop]):
        if stop==start:
            if (db[start]==value): return start
            return None
        pos = start+int((stop-start)/(db[stop]-db[start])*(value-db[start]))
        if db[pos] == value:
            return pos
        if db[pos] < value:
            start = pos + 1
        else:
            stop = start - 1
    return None

def Jump(value, db):
    length = len(db)
    if length == 0:
        return None
    step = old_step = int(sqrt(length))
    index = 0
    while db[min(step, length)-1] < value:
        index = step
        step += old_step
        if (index >= length):
            return None
    while (db[index] < value):
        index += 1
        if (index == min(step, length)):
            return None
    if (db[index] == value):
        return index
    return None

def Linear(value, db):
    if db == []: return None
    index = 0
    while index<size:
        if value == db[index]:
            return index
        index += 1
    return None

# This is the only one, could be called with unsorted list
call(Linear)
# All functions called should be with sorted list
call(Binary)
call(Jump)
call(Exponential)
call(FibMonaccian)
call(Inerpolation)

本作品采用《CC 协议》，转载必须注明作者和本文链接