北京大学生物信息平台论坛

 找回密码
 立即注册
搜索
热搜: 通知 活动

把x变换为最近的0.5的倍数

[复制链接]
licheng 发表于 2015-12-23 00:51:47 | 显示全部楼层 |阅读模式
脑筋转弯:R中的函数round(x)是把x四舍五入。如果我想把x变为最近的0.5的倍数,有什么快捷的办法?

- x先乘2,再round,再除以2
- round(x/0.5) * 0.5

除以0.5比乘以2的思路更自然些,代码更易读。但这两种方法都用到了三次操作:乘、除、round,乘除比加、减费时。加减是一个CPU时钟节拍(clock)的操作,2.5G hz主频的CPU每秒可以算25亿次,round要看R的帮助信息理解它的算法复杂度。能不能用更少或更快的操作?

把千分之一秒的计算时间提高到万分之一秒看似没多大用,但架不住复杂数据分析中成千上万亿次的计算。速度要从细节中优化出来。

在R中比较计算时间,可以用system.time函数嵌套一万次或一亿次运算,比较相同次数的加减、乘除、取整、if else的速度差别。

计算机数是用二进制储存和计算的,乘二和除二都有快速算法,即用“位移”(bit shifting),只用一个时钟节拍的时间。如十进制的3是二进制的11,向左移一位变成110,就是十进制6;向右移一位是1,就是十进制1(除2后把余数扔了)。这就像十进制里在数后面加0和减0,等同于乘除10。R函数bitwShiftL向左移一位,如bitwShiftL(3,1)得出6. 但这个函数只对整数位移,如何对实数位移?这要检查R是如何用二进制表示实数的,然后分别对整数部分和小数部分位移,也许有R包实现了这个功能。

相关链接:
如何位移实数
http://stackoverflow.com/questio ... ating-point-numbers
http://stackoverflow.com/questio ... it-shifting-a-float
http://cboard.cprogramming.com/c ... loat-variables.html

回复

使用道具 举报

youess 发表于 2015-12-23 12:28:01 | 显示全部楼层
小数的位移操作不好实现,不如使用Rcpp这个黑魔法。

  1. require("microbenchmark")
  2. require("Rcpp")
  3. # sourceCpp("./round2_cpp.cpp")
  4. cppFunction('NumericVector round2_cpp(NumericVector vec)
  5.             {
  6.                 for (int i = 0; i < vec.size(); ++i)
  7.                 {
  8.                     vec[i] = (double)( (int)2 * vec[i] ) / 2;
  9.                 }
  10.                 return vec;
  11.             }
  12.             ')

  13. round2 <- function(v)
  14. {
  15.     round(2 * v) / 2
  16. }


  17. x <- rnorm(100000)
  18. microbenchmark(
  19.                "round2" = round2(x),
  20.                "round2_cpp" = round2_cpp(x),
  21.                times = 100
  22.                )
复制代码
r1.png
回复 支持 反对

使用道具 举报

 楼主| licheng 发表于 2015-12-23 12:37:29 | 显示全部楼层
注释讲解一下程序吧,我们大多是生物同学啊
回复 支持 反对

使用道具 举报

youess 发表于 2015-12-23 13:32:20 | 显示全部楼层
这个程序其实很简单,round2是R语言写的, round2_cpp是c++写的,Rcpp作为两者之间连接的一个包,可以将c++的函数编译成R中的函数。

了解一些Rcpp包可以看这篇博文
回复 支持 反对

使用道具 举报

chenq 发表于 2015-12-25 10:46:04 | 显示全部楼层
可以说看不懂吗?  呵呵
回复 支持 反对

使用道具 举报

 楼主| licheng 发表于 2015-12-25 11:10:05 | 显示全部楼层
chenq 发表于 2015-12-25 10:46
可以说看不懂吗?  呵呵

R语言的语法和C/C++语言很像,但是R是解释型语言(每行命令在运行时转化为二进制机器代码),而C/C++是编译型语言(整个程序和函数都编译成二进制代码后再运行),所以后者速度快很多。

这里使用Rcpp的这个R包,通过cppFunction函数(参数是C++代码)建立一个round2_cpp的C++函数,但可以很方便地通过R来调用。C++代码通过循环对向量vec中的每一个数进行乘2、取整、除2的操作。R的向量矩阵运算也是要在二进制码层次做循环的,但它是优化过的,比在R代码层次做循环要快得多。

microbenchmark()比较C函数和R函数的运算速度,运算100次,每次操作10万个数。运算速度C函数比R函数提高10倍以上。但这里还是没有绕过乘除运算,我打赌使用位移算法会快得多。
回复 支持 反对

使用道具 举报

Galaxy 发表于 2016-1-6 12:12:32 | 显示全部楼层
本帖最后由 Galaxy 于 2016-1-6 12:16 编辑

话说,0.5肯定是浮点数,那么,直接把0.5的exponent调到与输入值的一样,得到相应移位调节后的0.5的significand值x,将输入数的significand比x低的位抹掉,应该就可以了。
(按IEEE 754规范,significand的范围是1到2,x由于发生移位,可以超出这个范围。实际实现时只需要记录0.5的significand的最高位移位后的位置。)

四舍五入的话,看x的最高位在输入中是0还是1,是1就进位。
回复 支持 反对

使用道具 举报

北京大学生物信息平台论坛

GMT+8, 2017-11-19 22:09 , Processed in 0.093947 second(s), 25 queries .

Powered by Discuz! X3

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表