【基础】查表法_dongpy的博客-程序员ITS304_查表法

技术标签: 扩展  C/C++  存储  360  

 查表法是将一些事先计算好的结果,存储在常量数组中,运行时节省计算开销。

例如,

计算字节中位1的个数,

int countBits( unsigned char dat )

{

   static char nBitTab[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, ...... };

   return nBitTab[dat];

}

或将字节按位逆序,

unsigned char reverse( unsigned char dat )

{

   static char revTab[256] = { 0x0, 0x80, 0x40, ......};

   return nBitTab[dat];

}

或计算0~360度的正弦值,

int sin( int ang )
{
 static const int sinV[] = {
   /*sin00=*/0, 1144,2287,3430,4572,5712,6850,7987,9121,10252,
   /*sin10=*/11380,12505,13626,14742,15855,16962,18064,19161,20252,21336,
   /*sin20=*/22415,23486,24550,25607,26656,27697,28729,29753,30767,31772,
   /*sin30=*/32768,33754,34729,35693,36647,37590,38521,39441,40348,41243,
   /*sin40=*/42126,42995,43852,44695,45525,46341,47143,47930,48703,49461,
   /*sin50=*/50203,50931,51643,52339,53020,53684,54332,54963,55578,56175,
   /*sin60=*/56756,57319,57865,58393,58903,59396,59870,60326,60764,61183,
   /*sin70=*/61584,61966,62328,62672,62997,63303,63589,63856,64104,64332,
   /*sin80=*/64540,64729,64898,65048,65177,65287,65376,65446,65496,65526,
   /*sin90=*/65536,  
   };
 if ( 0 <= ang && ang <= 90 )
 {
  return sinV[ang];
 }
 if ( 90 < ang && ang <= 180 )
 {
  return sinV[180-ang];
 }
 if ( 180 < ang && ang <= 270 )
 {
  return -sinV[ang-180];
 }
 if ( 270 < ang && ang < 360 )
 {
  return -sinV[360-ang];
 }
 return 0;
}

理论上,y=f(x),x的取值范围为有限种状态,且f(x)有一定运算量时,都可以考虑查表法。

如,前两个例子中x的范围是字节的256个值,第三个例子是0~90度。

运算量方面,sin的运算量大很多,因此更适合查表。另外,自定义查表法还可用定点数代替浮点数,且一般四则运算也不会溢出(定点数范围0~65535),所以进一步节省了浮点的运算量。

 

有些情况,x取值状态很多,无法直接用查表法,也可基于其中的公共子集进行扩展。

如要计算32位数中位1的个数,可将其拆成4个字节分别计算并求和。

如要计算0.0~90.0的sin值,可再建立一个sin0.1~0.9的常量表,然后用sin(x+y)的公式,如sin50.5=sin(50+0.5)=sin50*cos0.5+cos50+sin0.5。

 

另外,查表法还用于简化switch/case语句,还可将数据与代码分离。
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/dongpy/article/details/6883930

智能推荐

hadoop 命令执行报错解决_雪水的博客-程序员ITS304

ls: Failed on local exception: java.io.IOException: javax.security.sasl.SaslException: GSS initiate failed [Caused by GSSException: No valid credentials provided (Mechanism level: Failed to find any

IDEA报错:log4j:WARN No appenders could be found for logger (org.mybatis.generator.internal.db.Databas)_cici未完成的拼图的博客-程序员ITS304

报错信息:log4j:WARN No appenders could be found for logger (org.mybatis.generator.internal.db.DatabaseIntrospector).log4j:WARN Please initialize the log4j system properly.log4j:WARN See http://logging...

Vue 模板是如何编译的_前端同学的博客-程序员ITS304_vue模板编译

认识模板编译我们知道 &lt;template&gt;&lt;/template&gt; 这个是模板,不是真实的 HTML,浏览器是不认识模板的,所以我们需要把它编译成浏览器认识的原生的 HTML这一块的主要流程就是提取出模板中的原生 HTML 和非原生 HTML,比如绑定的属性、事件、指令等等经过一些处理生成 render 函数render 函数再将模板内容生成对应的 vnode再经过 patch 过程( Diff )得到要渲染到视图中的 vnode最后根据 vnode 创建真实的 DOM

sota结果是什么意思_只有达到SOTA的方法才能发文章吗_weixin_39743369的博客-程序员ITS304

最近关注了一个问题:只有达到 state of the art 精度的方法才能发文章吗?得赞同最多的回答分享了ICML审稿人的话,说的非常好:The academic is not an army race. It does not really matter how fancy the model is. It does not really matter whether the model c...

浙江工商大学和杭电计算机哪个好,浙江工业大学、杭电、浙江理工大学、浙江工商大学哪所值得报考?..._Clarlie的博客-程序员ITS304

有人问,浙江工业大学、杭州电子科技大学、浙江工商大学和浙江理工大学,哪个学校更值得选择?这4所大学都是浙江省的普通高校。不过,这几所大学的实力并不太弱,也许要好于部分211大学。原因是,浙江的高等教育跟它的教育强省地位不符合。浙江只有浙大一所985兼211大学。在双一流名单里,也只有3所学校上榜,除了浙大,还有宁波大学和中国美术学院。中国美院实力很强,但属于艺术类学校,对大部分考生不适合。综合性院...

[SPI]SPI协议详解_weixin_30539625的博客-程序员ITS304

转自:https://my.oschina.net/freeblues/blog/674001.SPI协议简介1.1.SPI协议概括  SPI,是英语Serial Peripheral interface的缩写,顾名思义就是串行外围设备接口。是Motorola首先在其MC68HCXX系列处理器上定义的。SPI接口主要应用在 EEPROM,FLASH,实时时钟,AD转换器,还有数字信...

随便推点

Day23——知识点总结_九灬八的博客-程序员ITS304

1. 网络编程概述1.1 C/S和B/SC/S 客户端 服务器软件结构 服务提供商给予用户服务需要准备的内容 1. 各大平台的客户端 Android iOS PC Windows Linux macOS QQ 微信 淘宝 JD 剑与远征 2. 服务器提供服务 软件更新: LOL服务器版本更新,同时本地软件也要进行更新操作。这个操作非常耗时。 热更新 B...

Gazebo学习--第四讲:制作一个移动机器人_pangweijian的博客-程序员ITS304

第四讲:制作一个移动机器人概述本讲演示了Gazebo的基本模型管理,并通过带领用户创建使用差动驱动机制进行运动的两轮移动机器人的过程,练习熟悉模型数据库中的基本模型表示。设置模型路径通读模型数据库文档。您将创建自己的模型,它必须遵循Gazebo模型数据库目录结构的格式化规则。另外,关于模型描述格式的详细信息,请参考SDF参考手册创建模型目录:mkdir -p ~/.gazebo/models/my_robot创建模型配置文件gedit ~/.gazebo/models/my_robo

Android中级:代码混淆与反编译_AndroidCQC的博客-程序员ITS304

参考: Android Studio混淆模板及常用第三方混淆(看了都说好) 混淆 混淆简介-dontwarn com.baidu. 忽略com.baidu下的所有warning混淆模板混淆就是把module的build.gradle中的minifyEnabled改为true,同时需要修改module的prodeard-rules.pro############################

tensorflow session的关闭问题_ok_kakaka的博客-程序员ITS304_tensorflow 关闭session

在使用tensorflow时,需要在不同的函数中,调用同一个session,所以需要session在第一次使用后保持开启。在网上搜索到的教程中,一般是说:调用tf.Session.close方法,或使用session作为上下文管理器,都可以关闭session。所以我理解的意思是,如果用方法1打开session,那么session就不会自动关闭。但事实并不是这样的,即使使用方法1,session使...

python调用scikit-fuzzy实现简单模糊逻辑控制的说明(一)_sweet_Chanyelo的博客-程序员ITS304_模糊逻辑python实现

一直想要实现用python编写一个模糊控制器,自己尝试了很久发现还(zhu)是(yao)很 (shi) 难(lan),不过终于找到了可以直接调用的现成的模糊控制库scikit-fuzzy,看起来和scikit-learn 很像,也看了几个大佬的博客,发现功能还是比较简单,能处理的问题也十分有限。1.案例说明这里同样采用一个大佬常用来说明的案例进行说明,其中由2个输入,1个输出,每个输入设置3个参考值,因此共9条规则,相应的规则矩阵如下表输入参考值NMPNN`MMM

什么是WAP网关? _iteye_5823的博客-程序员ITS304

1. 什么是WAP网关?WAP网关是一个软件。它连接Internet或者Intranet,使得WAP电话可以来访问其中的资源。有些网关可能具有将HTML文件转换为WML页面的功能。WAP网关在WAP设备与Web服务器之间的连接中有好多功能。这些功能基本上是:将标记语言(WML)从文本转换成可以被WAP设备读懂的编码(二进制/压缩的)格式; 将WAP设备的请求转换成Web中的HT...