Mec*_*cki 37 algorithm search range
我有几个数字范围.这些范围不重叠 - 因为它们不重叠,逻辑结果是任何时候任何数字都不能成为多个范围的一部分.每个范围都是连续的(单个范围内没有孔,所以8到16的范围实际上包含8到16之间的所有数字),但两个范围之间可能存在空洞(例如范围从64开始到128,下一个范围从256开始并转到384),因此某些数字可能根本不属于任何范围(在此示例中,数字129到255不属于任何范围).
我得到一个号码,需要知道该号码属于哪个范围......如果它属于任何范围.否则我需要知道它不属于任何范围.当然速度很重要; 我不能简单地检查所有范围是O(n),因为可能有数千个范围.
一个简单的解决方案是将所有数字保存在已排序的数组中并对其运行二进制搜索.这至少会给我O(log n).当然二进制搜索必须稍微修改,因为它必须始终检查范围的最小和最大数量.如果要查找的数字介于两者之间,我们找到了正确的范围,否则我们必须搜索当前范围之下或之上的范围.如果最后只剩下一个范围并且数字不在该范围内,则该数字根本不在范围内,我们可以返回"未找到"结果.
范围也可以在某种树形结构中链接在一起.这基本上就像是带有二分搜索的排序列表.优点是修改树比修改数组(添加/删除范围)更快,但不像我们浪费一些额外的时间来保持树平衡,树可能会在一段时间内变得非常不平衡,这将导致比排序数组上的二进制搜索慢得多.
人们可以争论哪种解决方案更好或更差,因为实际上搜索和修改操作的数量几乎是平衡的(每秒执行的搜索和添加/删除操作数量相同).
对于这类问题,是否有比排序列表或树更好的数据结构？也许在最好的情况下可能比O(log n)更好,在最坏的情况下可能比O(log n)更好？
此处可能有用的一些其他信息如下:所有范围始终以2的幂的倍数开始和结束.它们总是以相同的2的幂开始和结束(例如,它们以4的倍数或8的倍数或16的倍数开始/结束,依此类推).在运行时,2的功率不能改变.在添加第一个范围之前,必须设置2的幂,并且所有已添加的范围必须以此值的倍数开始/结束,直到应用程序终止.我认为这可以用于优化,好像它们都以例如8的倍数开始,我可以忽略所有比较操作的前3位,其他位将告诉我范围(如果有的话).
我读到了关于树和树的范围.这些是问题的最佳解决方案吗？有没有更好的解决方案？问题听起来类似于malloc实现必须做的事情(例如,每个freed内存块属于一系列可用内存,malloc实现必须找到哪一个),那么通常如何解决这个问题呢？
Mec*_*cki 22
在运行各种基准测试后,我得出的结论是,只有树状结构可以在这里工作.排序列表显示了固然好查找性能 - O(log n)的 - 但它显示了可怕的更新性能(插入和移除是比相比树10倍更慢!).
平衡二叉树也具有O(log n)查找性能,但是更新速度快得多,也在O(log n)附近,而排序列表更像O(n)更新(O(log n)到找到要插入的位置或要删除的元素,但最多必须在列表中移动n个元素,这是O(n)).
我实现了一个AVL树,一个红黑树,一个Treap,一个AA树和B树的各种变体(B在这里意味着拜耳树,而不是二进制).结果:拜耳树几乎从未获胜.他们的查找很好,但是他们的更新性能很差(因为在B-Tree的每个节点中你都有一个排序列表!).拜耳树仅在箱子优越其中读/写一个节点是一个非常缓慢的操作(例如,当节点被直接读取或从/写入硬盘) - 作为B树必须读/写少得多的节点比任何其他树,所以在这种情况下它会赢.如果我们虽然在内存中的树,它的立场与其他树木没有机会了,对不起,所有的B树的球迷在那里.
Treap最容易实现(不到其他平衡树所需的代码行的一半,只是不平衡树所需代码的两倍),并且查找和更新的平均性能良好......但我们可以做得比那.
AA-Tree显示出惊人的良好查找性能 - 我不知道为什么.它们有时会击败所有其他树(不是很远,但仍然不够重合)......并且移除性能还可以,但是除非我太愚蠢而无法正确实现它们,插入性能非常糟糕(它执行每个插入物上的树旋转比任何其他树更多 - 甚至B树也具有更快的插入性能.
这给我们留下了两个经典,即AVL和RB-Tree.它们都非常相似,但经过数小时的基准测试后,有一件事是清楚的:AVL Trees肯定比RB-Trees有更好的查找性能.差异并不大,但在所有基准测试的2/3中,他们将赢得查找测试.在所有AVL树比RB-Trees更严格平衡之后,并不太令人惊讶,因此在大多数情况下它们更接近最佳二叉树.我们不是在谈论这里的巨大差异,它始终是一场紧密的竞赛.
另一方面,RB Trees几乎在所有测试运行中都击败了AVL Trees以进行插入,而这种情况并非如此紧密.和以前一样,这是预期的.与AVL树相比,不太严格平衡的RB树在插入上执行的树旋转要少得多.
删除节点怎么样？这似乎很大程度上取决于节点的数量.对于小节点数(一切都不到五十万),RB树再次拥有AVL树; 差异甚至比插入更大.相当出乎意料的是,一旦节点数量增长超过一百万个节点,AVL树似乎赶上并且与RB树的差异缩小,直到它们或多或少同样快.但这可能是系统的影响.它可能与进程的内存使用或CPU缓存等有关.对RB树具有比AVL树更负面影响的东西,因此AVL树可以赶上.查找没有观察到相同的效果(AVL通常更快,无论有多少节点)和插入(RB通常更快,无论有多少节点).
结论:
我认为我能得到的最快就是使用RB-Trees时,因为查找次数只会略高于插入和删除次数,无论AVL查询速度有多快,整体性能都会受到影响.更糟糕的插入/删除性能.
也就是说,除非这里的任何人都想出一个更好的数据结构,它将拥有RB树的大时间;-)
创建排序列表并按下边距/开始排序.这是最容易实现的,并且足够快,除非你有数百万个范围(甚至可能那么).
寻找范围时,找到范围start <= position.您可以在此处使用二进制搜索,因为列表已排序.该数字在if范围内position <= end.
由于任何范围的结束都保证小于下一个范围的开始,因此在找到可能包含位置的范围之前,您无需关心结束.
当您获得交叉点或者您拥有大量范围以及构建结构并经常查询时,所有其他数据结构都会变得有趣.