章节列表

位图数据结构

2018-01-12 09:42:05 +0000 李述铜

Hi, 这节课时我会教你实现一种看似简单但却十分高效的算法:查表。它可以将原来可能需要几十行,很多次循环的执行的代码变成短短一行。

准确地讲,这个算法的巧妙之处体现其背后的思想:以空间换时间

主要内容

本课程介绍的位图查找算法会用于后面课程的任务调试器实现,用于代码执行加快速度。

重点难点

有些同学看完视频课程后仍不能理解其背后的原理,这里再解释一下。假设有这样一个需求:

假设我们有32位宽的数,要找到从最低位开始到最高位,第1个置1的位是哪一位?

对于这个需求,我们可能用以下算法计算出来。

for (int bitPos = 0; bitPos < 32; bitPos++) {
  if (num & (1 << bitPos)) {
      return bitPos;
  }
}
return -1;

不过这需要循环32次,速度有些慢,现在想提高性能。那么你可能会有这样一个想法:能不能把所有的可能结果都算出来,然后在需要计算时,根据数值直接查结果?是的。这就是这节课程中实现的方法。

只不过这里的数是32位宽,可能的结果是2^31个,把所有的结果都放在内存中,显示太大了。那能不能牺牲下性能,比如下面这种?

分四组,依次查第0到第7、第8~第15、第16~23、第23~31,这样每次只需要查8位。这8位的结果数量就只有256个,占用空间很小,完全可以放在存储器中。这个表定义为大小256个字节:

  • 字节0:数组索引为0,存放0的从最低位起第1个置1的序号,其值为0xFF(表示没有位置1)
  • 字节1:数组索引为1,存放1的从最低位起第1个置1的序号,其值为0(第0位置1)
  • 字节2:数组索引为2,存放2的从最低位起第1个置1的序号,其值为1(第1位置1)
  • …….
  • 字节255:数组索引为255,存放255的从最低位起第1个置1的序号,其值为0(第0位置1)

具体这张表可手工生成,也可借助程序生成。具体算法见:位图结构中表值是怎么计算出来的

这样的话,第1组、第2组、第3组、第4组的查找方法完全相同,都按8位查找,只不过最终在计算时,要稍微调整下。

  • 第1组(0~7):直接返回查找的位序号,取值为0~7
  • 第2组(8~15):采取第1组的查找方式,取值为0~7 + 8
  • 第3组(16~23):采取第1组的查找方式,取值为0~7 + 16
  • 第3组(24~31):采取第1组的查找方式,取值为0~7 + 24

抛开上面的具体实现细节,我们可以联想到:对于类似这种输入数量有限、并且耗时的计算,完全可以应用查表来提升其效率。一般情况下,只需一次查表即可快速得到结果。

注意事项

借助Cortex-M3的某些指令可以实现类似的操作,但这并不是我们要关注的重点。

常见问题