0
0

带猜测的二分查找算法

云风 发表于 2021年06月11日 14:39 | Hits: 268
Tag: 算法

我想用 C 实现一个内存紧凑的 ECS 框架,希望数据结构足够的简单,且能管理海量的对象。所以我让每个 component 就是一个不包含任何引用的 struct ,并带有一个 32bit 的 id 。并把这样的一个数据结构放在一块连续内存中。

这个 id 没有对外暴露的 API (不是 entity id ),可以在运行过程中调整。如果两个不同类型的 component 有相同的 id ,即认为它们同属一个 entity 。id 的作用是管理 component 的生命期,以及在遍历 component 时,可以找到同个 entity 上其它的组件。

对于我的应用场合来说,最多的操作是遍历单类 component 的集合。这种操作在这个数据结构下特别简单,就是 for 循环遍历一个简单的数组。但有些系统会需要在处理一个 component 时,找到它归属的 entity 上的兄弟组件。由于我不想用额外的内存建立这些 component 间的联系,所以这个开销就会特别大。如果不做任何优化,查找是 O(n) 的,n 为组件的数量。这显然不能接受。

第一步优化,我让组件在组件集数组中保持有序,按 id 排序。id 本身在分配的时候是单调递增的,所以只要 32bit id 不回绕就能一直保持有序。一旦回绕,我们重排一下即可。对于有序的数组,用二分查找可以减少到 O(log N) 的时间复杂度。

如果 N 特别大(十万以上)时,还是比较慢的。那么,有没有可能对二分查找做进一步优化呢?我做了一点尝试。

因为在我的系统中,通常是顺序处理某类 component 的,处理顺序会保证 id 是单调递增的(本身按 id 排序)。所以,每次用当前的 id 去另一个有序的 component 集合中查找时,这些查找之间有较强的相关性。比如,正在处理的集合中 id 是 1 3 5 7 9 ,而它需要查找的另一个集合中 id 则是 1 4 5 9 10 ;我们做完一次查找后,下一次查找的位置就在上一次位置靠后一点的附近。利用上这个信息,就有可能提高查找的性能。

我把这个方法称为带猜测的二分查找。即:在二分查找开始前,先猜测一下目标值大致所在的范围。如果恰巧落在范围内,查找虽然还是 O(log N) ,但 N 有可能被极大的缩小。但这个猜测逻辑也不宜过于复杂,我采用的策略是,把目标范围设定在上次成功找到的位置到这个位置向后 64 个 slot 之间。

我做了一些简单的评测,发现在 N 在百万量级时,加入猜测可以比直接二分查找快 2~3 倍左右;当 N 在十万量级时,可以快 70% 左右;在一万量级时,依然有 10% 的收益。

原文链接: https://blog.codingnow.com/2021/06/binary_search_by_guess.html

0     0

我要给这篇文章打分:

可以不填写评论, 而只是打分. 如果发表评论, 你可以给的分值是-5到+5, 否则, 你只能评-1, +1两种分数. 你的评论可能需要审核.

评价列表(0)