Nor*_*ard 4 algorithm optimization search
我真的很喜欢研究算法和优化代码(我尽量不要过早地做)因为当花费5分钟运行的东西现在在2分钟内运行时感觉非常酷.我对搜索算法特别感兴趣,因为当你必须在表中搜索匹配的子字符串或条目时,它是如此频繁.
我正在考虑比较排序的下限,并且正在思考如何通过猜测哪些答案将会跳过某些比较,然后整个比较线可能会消失并且高度降低,那么如何对于巨大的数据集进行思考通过1.(例如,如果一个算法可以猜测bcd在一起,则排序a,b,c,d,e,f然后你真的只是排序a,bcd,e,f)猜测必须是聪明的,有效的猜测让它值得,加上需要有相当不错的击球率.
与搜索相同,如果智能搜索可以首先猜测项目可能在哪里,并且仅搜索前5个猜测区域.如果所有5个猜测都是错误的,那么它可能会返回错误的答案并且永远不会找到该项目,但是如果它具有足够好的正确比率,那么它可能与它相关.它可能比创建二进制搜索树然后进行log(n)搜索更快.
无论如何,我相信任何理解这个主题的人现在都会意识到这主要是没有实质内容的猜测/幻想所以我正在寻求帮助,以便在学习没有100的算法方面采取措施%正确返回,特别是在搜索/排序区域,但更快并且应用这些算法.
我用谷歌搜索,点击维基百科上的随机链接试图找到这个,但没有令人满意的结果.我应该阅读什么/我应该去哪里开始学习这个？
我想我应该提到我对大多数"标准"算法和数据结构感到满意,如快速排序,合并排序,气泡,基数,计数等,以及哈希,自平衡树等.
我认为要取得很大成就,你必须为你的"几乎排序"定义一些标准.例如,如果在正确位置的N个点内有一个元素就足够了,你可以做一些像Quicksort这样的事情,但是当一个分区到达N个元素时停止.请注意,执行此操作已经很常见,并使用插入排序完成作业.但是,除非N非常大,否则你可能不会从中获得太多.
就搜索而言,您可能正在寻找通常称为插值搜索的东西.您可以使用插值来猜测您正在寻找的项目的可能位置,而不是总是猜测范围的中间位置(例如,如果您正在寻找以'b'开头的字符串,那么您可以从1开始/ 13 次的方式,通过一个集合,而不是完成了一半.
如果集合中的项目分布极不均匀,后者可能效果不佳,但假设分布合理均匀,则会产生非常好的结果(大约为O(log log N)而不是O(log N)你得到二分搜索).然而,它确实依赖于均匀分布,并且具有可以计算至少与"距离"相似的东西的键类型,而不仅仅是 "小于"或"大于"的比较.在实践中,它通常可以很好地工作(并且它通常在前面是非常明显的情况).