WisKeyのLullaby

huangwei.pro 『我失去了一只臂膀』「就睁开了一只眼睛」

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  12 Posts :: 0 Stories :: 23 Comments :: 0 Trackbacks

公告

“我该走哪条路?”
“这取决于你要去哪里。”
“我只想能到某个地方。”
“只要你走的够远,你始终能到达那个地方。”

Home: huangwei.pro
E-Mail: sir.huangwei [at] gmail.com
09.6 毕业于杭州电子科技大学
进入网易杭州研究院工作至今

常用链接

留言簿(1)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 45649
  • 排名 - 396

最新评论

阅读排行榜

评论排行榜

2015年9月1日 #

     摘要: http://huangwei.pro/2015-09/modern-opengl4/ 本篇教程中,我们会巩固上一篇所提到的矩阵和相机知识,并使用tdogl::Camera类来实现第一人称射击类型的相机。然后,我们会将相机与键盘和鼠标挂钩,使得我们可以移动和浏览3D场景。这里会学一些向量数学,还有上一篇没提到的逆矩阵。获取代码所有例子代码的zip打包可以从这里获取:https://git...  阅读全文
posted @ 2015-09-01 17:38 威士忌 阅读(1427) | 评论 (1)编辑 收藏

2015年8月14日 #

     摘要: http://huangwei.pro/2015-08/modern-opengl3/ 本文中,我会将不会动的2D三角形替换为旋转的3D立方体。你会看到这样的效果: 现在我们终于能在屏幕上搞点有趣的东西了,我放了更多的动图在这里:http://imgur.com/a/x8q7R为了生成旋转立方体,我们需要学些关于矩阵的数学,用于创建透视投影,旋转,平移和“相机...  阅读全文
posted @ 2015-08-14 17:03 威士忌 阅读(1534) | 评论 (0)编辑 收藏

2015年8月6日 #

     摘要: http://huangwei.pro/2015-08/modern-opengl2/ 在本文中,我们将给三角形加一个贴图,这需要在顶点和片段着色器中加入一些新变量,创建和使用贴图对象,并且学习一点贴图单元和贴图坐标的知识。本文会使用两个新的类到tdogl命名空间中:tdogl:Bitmap和tdogl:Texture。这些类允许我们将jpg,png或bmp图片上传到显存并用于着色器。t...  阅读全文
posted @ 2015-08-06 20:17 威士忌 阅读(1284) | 评论 (1)编辑 收藏

2015年7月27日 #

     摘要: http://huangwei.pro/2015-07/game-random/这段时间公司开发的游戏上线测试,许多玩家在抽卡时抱怨脸黑,很难抽到所需要的卡牌,而又有一部分玩家反应运气好能连着抽到紫卡,检查了下随机相关逻辑代码,并没有找出问题所在,玩家运气好与坏只是觉得真有可能是概率原因。测试开服了几天之后,需要开放某个限时抽卡活动,在内部测试时,我们发现玩家反应的问题在限时抽卡中格外明显,尤其是...  阅读全文
posted @ 2015-07-27 01:20 威士忌 阅读(2791) | 评论 (4)编辑 收藏

2015年5月21日 #

     摘要: http://huangwei.pro/2015-05/modern-opengl1/ modern-opengl 译序 早前学OpenGL的时候还是1.x版本,用的都是glVertex,glNormal等固定管线API。后来工作需要接触DirectX9,shader也只是可选项而已,跟固定管线一起混用着。现在工作内容是手机游戏,又转到OpenGL ES,发现OpenGL的世界已经完...  阅读全文
posted @ 2015-05-21 14:11 威士忌 阅读(5268) | 评论 (3)编辑 收藏

2011年4月27日 #

     摘要: http://blog.huang-wei.com/2011/04/27/read-source-tool/

做程序员的,每天要对着显示器上的行行代码
尤其是一份你从未写过、未读过的代码放在你的面前时,尼会感到似那样滴心力憔悴
这些还都算了,尼玛连个注释都没!!!文档呢!有木有啊!!
哥幼小的心灵在一大堆代码中接受着无数次的摧残~  阅读全文
posted @ 2011-04-27 15:21 威士忌 阅读(3054) | 评论 (1)编辑 收藏

2010年11月21日 #

     摘要: http://blog.huang-wei.com/2010/11/21/winsock-io/Windows Socket IO 模型套接字架构应用程序使用Winsock与传输协议驱动沟通时AFD.SYS负责缓冲区的管理。这就意味着当一个程序调用send或者WSASend发送数据时,数据将被复制到AFD.SYS它自己的内部缓冲区中(依赖SO_SNDBUF的设置)WSASend调用立即返回。然后A...  阅读全文
posted @ 2010-11-21 12:10 威士忌 阅读(6957) | 评论 (3)编辑 收藏

2010年11月17日 #

     摘要: Http://Blog.Huang-Wei.Com/2010/08/09/C%E4%B8%AD%E5%AE%9E%E7%8E%B0%E5%A7%94%E6%89%98%EF%BC%88delegate%EF%BC%89/C++中实现委托(Delegate)公司的项目里有用到Don Clugston的FastDelegate,当时只知道是类似boost::function的东西,UI上当watche...  阅读全文
posted @ 2010-11-17 11:17 威士忌 阅读(10612) | 评论 (8)编辑 收藏

     摘要: Http://Blog.Huang-Wei.Com/2010/11/02/Bloom-Filter/Bloom Filter 原理与应用介绍Bloom Filter是一种简单的节省空间的随机化的数据结构,支持用户查询的集合。一般我们使用STL的std::set, stdext::hash_set,std::set是用红黑树实现的,stdext::hash_set是用桶式哈希表。上述两种数据结构,都...  阅读全文
posted @ 2010-11-17 11:16 威士忌 阅读(3066) | 评论 (1)编辑 收藏

2010年7月23日 #

http://blog.huang-wei.com/2010/07/20/%e5%8f%8c%e6%95%b0%e7%bb%84%e5%ad%97%e5%85%b8%e6%a0%91%e7%9a%84%e5%86%85%e5%ad%98%e5%8d%a0%e7%94%a8%e6%b5%8b%e8%af%95/

上一篇文章介绍了双数组字典树 DATrie,现在让我们来简单的测试下内存占用情况。

测试用例,我选了The Holy Bible,数据文件大小为4.2MB。只记录英文单词,全部转为小写。

words : 822,529
u-words : 12,591
nodes : 34,266
trie-mem : 1,247,308
datrie-mem : 483,376

Trie的实现我已经做了一些优化,初始每个节点的指针数组 size 为0,当有节点插入时,再开 max(size, char) 大小的数组。trie-mem 显示的是已经除去节点自身的大小,即该数值体现的是申请的指针数组总大小。

trie-mem / ptr-size / nodes = 9.1,说明平均每个节点(内节点+叶节点)分配了9.1个指针。相对完全Trie树而言,已经节省了很多空间了。但这样算浪费的量明显是不够精确的,nodes 应该换成内节点数(这里就用 u-words 代替叶节点,虽然两者是不等同的),因为叶节点未分配指针数组,并应该减去真正有用的转移边。这个浪费的值应该是 (trie-mem / ptr-size – nodes) / (nodes – u-words) = 12.8。

DATrie的浪费值应该是 (datrie-mem / (2 * int-size) – nodes) / (nodes – u-words) – 1 = 1.2,可见 DATrie 的空间复杂度还是相当不错的。当然DATrie的实现我还没有进行深入的优化,基本就是上一篇文章里的代码做的测试。如果按那文章里提到的优化方法继续优化,空间的浪费值会更低。

但DATrie存在一个比较大的问题,就是它的空间是预先申请好的,因为根本无从得出它实际的大小,如果空间不够大了再重新分配的话,那势必又得消耗时间,而且还是无法解决空间是否足够的问题。另外,附加的信息域最好保存为指针的形式,否则重排时复制的复杂度就可能会很高。

总结,DATrie还是比较适合在工程中应用,尤其对于数据集比较固定的。

posted @ 2010-07-23 08:52 威士忌 阅读(760) | 评论 (0)编辑 收藏