我已经看到了很多不同的算法实现,但我想知道是否有办法提高效率,而不仅仅是制作搜索二进制文件 . 我已经设计了算法的这个特定版本,因此将立即检查数组/列表的边缘和中点以查找要搜索的密钥,以避免在您查找的密钥只是第一个,中间的时候循环搜索,或最后一个元素 .
def searchRB(the_array, the_key, imin, imax):
print("searching")
found = False
if (0 > the_key or the_key > len(the_array)):
return found
else:
imid = imin + ((imax - imin) // 2)
if imid == the_key or imin == the_key or imax == the_key:
found = True
return found
elif the_array[imid] > the_key:
return searchRB(the_array, the_key, imin, imid-1)
elif the_array[imid] < the_key:
return searchRB(the_array, the_key, imid+1, imax)
else:
return found
例如,如果您在1-100的列表中查找数字1,则会在第一个循环中找到它,这与其他实现不同 .
但是,我不确定这是否实际上提高了效率(除了某些边缘情况),并且如果继续循环并且必须检查,检查列表/数组中的first,mid和end值实际上是有害的每次都是这三个值 .
这是这种算法的好坏实现,还是我只是分裂?
1 回答
主要的一个是从递归方法改为使用while循环,节省了调用堆栈(因为python没有尾递归) .
您可以优化小冗余 . 算法已经足够优化了,除非你理解编译器,否则不要over optimise
如果你要沿着左边的树走下去,你将一遍又一遍地比较相同的亚胺,但这整行可能是并行的或顺序完成的
if the_array[imid] == the_key or the_array[min] == the_key or the_array[imax] == the_key:
此外,这可能会影响缓存性能,因为您将始终将the_array [min]保留在缓存中 . 有时编译器会在您尝试在缓存中访问的索引周围存储数组中的块 . 你可能会浪费更多的缓存而不仅仅是那个1值 .
此类语句也可以进行优化,您只需键入return True,但同样应该由编译器选择 .
found = True return found
没有
found
作为对象会优化代码,因为该对象不会一直存储在内存中 .这个else语句似乎是多余的,因为没有可能的方法来达到其他目的
else return found
实际的相关优化将来自对数据集的更多了解 .
如果您能够预处理数据(或者有关于数据的更多信息),您可以执行其他算法 .