This is from android

没想起wordpress还有app版本,多谢小芳邓的推荐。

最近一年blog都快荒废了,我的勤奋点了。

GDB调试stl的利器脚本

今天在weibo上发现了GDB调试STL容器类的利器,这里记录下:

脚本地址这里

使用方法:将链接里的文件内容保存到home目录的.gdbinit中,然后启动gdb时就可直接使用相关命令.

提供以下的方法:

#std::vector -- via pvector command
#std::list -- via plist or plist_member command
#std::map -- via pmap or pmap_member command
#std::multimap -- via pmap or pmap_member command
#std::set -- via pset command
#std::multiset -- via pset command
#std::deque -- via pdequeue command
#std::stack -- via pstack command
#std::queue -- via pqueue command
#std::priority_queue -- via ppqueue command
#std::bitset -- via pbitset command
#std::string -- via pstring command
#std::widestring -- via pwstring command

测试用例:


XOR链表

今天看到云风的一篇blog,提到了XOR链表,第一次见到,算法非常有意思,记录下。

大概思想:正常实现双向链表,对于每个node都会保存两个指针pre和next, 但是对于XOR linked list来说,可以只保存一个指针就可以实现,

保存的就是pre^next的异或值。

这个数据结构可以工作起来,依赖位运算的一个特性: A^(A^B) == B ,我们知道前序地址或后继地址中的任意一个,都可以用这个值推算出另一个来。这样的链表,从前向后与从后向前遍历的算法是一样的,区别只在于初始参数。

对于每个链表对象,我们只需要保存链表的head和tail, 就可实现从头和从尾遍历链表。

这里是Wikipedia对XOR linked list的介绍:http://en.wikipedia.org/wiki/XOR_linked_list

另外还有一篇论文对lock-free FIFO 的介绍:http://people.csail.mit.edu/edya/publications/OptimisticFIFOQueue-journal.pdf

iMacros工具用法介绍

iMacros是作为浏览器的插件,通过录制对网页的操作,然后进行回放,这样可以避免大量的重复性的劳动;目前已支持Firefox、Chrome和IE,我试用了一下Firefox的插件,感觉还挺方便的,与类似12306的刷票插件的原理基本是一样的,不过iMacros提供了自己的脚本,你可以直接图形界面录制,当然你也可以通过自己修改脚本来进行录制并回放,是实现浏览器自动抓取的利器。

本文主要介绍iMacros的基本用法,最后以一个比较的小的例子作为说明。

安装

1. Firefox插件下载地址:这里

2. Chrome插件下载地址:这里

使用

安装完成后,你会看到增加了这个图标,然后点击该图标,你就会看到iMacros展开的样子



可以看到上面一栏是对应的脚本,下面分为三栏:“运行”, “记录”, “编辑”

  • “运行”: 选中某个录制的脚本,点击运行,就会回放对应的操作
  • “记录”: 点击“记录”按钮,此时iMacros会开始录制你再浏览器上做的操作,然后会保存在Current.iim脚本中,比如我首先打开baidu.com, 并点击录制,然后输入”firefox imacros”搜索,最后“停止”;
  • “编辑”:选中“Current.iim”文件,选择“编辑宏”按钮,你会看到如下的内容:
VERSION BUILD=8300326 RECORDER=FX
TAB T=1
URL GOTO=http://www.baidu.com/
TAG POS=1 TYPE=INPUT:TEXT FORM=NAME:f ATTR=ID:kw CONTENT=firefox<SP>imacros
TAG POS=1 TYPE=INPUT:SUBMIT FORM=NAME:f ATTR=ID:su

上述脚本的大致意思:

  1. “URL GOTO”: 进入该页面
  2. “TAG POS=1 TYPE=INPUT:TEXT FORM=NAME:f ATTR=ID:kw CONTENT=firefoximacros”:在input表单中输入”firefox imacros”, 这里主要是TAG这个命令,选中html中该标签,可使用TYPE, ATTR, FORM进一步指定,最常用的一个命令,详情点击这里
  3. “TAB T=1″: 在第一个标签中打开URL, “TAB OPEN”在新的标签页打开,详情
iMacros中其它比较常用的命令
  • 变量赋值SET: SET today {{!NOW: dd-mm-yyyy}} 将当前的日期赋值给today这个变量,后续通过{{}}来引用该变量
  • WAIT SECONDS=3: sleep 3s.
  • 填充表单:使用TAG命令, 同时增加CONTENT选项即可:
    TAG POS=1 TYPE=INPUT:TEXT FORM=NAME:NoFormName ATTR=ID:SearchWord CONTENT={{today}}
  • 提取文本:TAG+EXTRACT 如
    TAG POS=1 TYPE=TD ATTR=TXT:当页汇总 EXTRACT=TXT
  • 模拟点击:比如要点击一个超级链接,同时知道其anchor,则就非常简单:
    TAG POS=1 TYPE=A ATTR=TXT:入口页面
  • 保存提取的文本到文件:在提取文本后,其内容会自动添加到EXTRACT变量中,你可以通过ADD或者SET命令来修改{{!EXTRACT}}这个变量,最后通过SAVEAS来保存提取的文本,以逗号分隔
    SAVEAS TYPE=EXTRACT FOLDER=D:\ FILE=report_{{yestoday}}.txt
  • 读取文件数据:有些情况下,比如要搜索大量的query,此时你就需要使用数据文件,然后使用{{!COL1}} {{!COL2}}来访问对应数据的列,默认列是以逗号进行分隔
    SET !DATASOURCE d:\datasource.txt
    SET !DATASOURCE_COLUMNS 2
    最后运行时要点击”播放(循环)”按钮,否则只会执行一行就会退出了,同时设置最大的行数

Unix/Linux设计思想学习笔记之一

最近在看《Unix/Linux设计思想》这本书,有些地方读起来很容易,但是真正理解还需要细细品味,以后就把书中提到的一些准则简单记录下,主要是为了加深理解,今天主要记录下Unix哲学的概述。

Unix哲学概述:

(1) 小即是美。相对于同类庞然大物,小巧的事物有着无可比拟的优势,其中一点就是它们能够以独特有效的方式结合其他小事物,这和软件工程中提到的“模块化”的思想基本是一致的。

(2) 让每个程序只做好一件事情。通过集中精力应对单一任务,程序可以减少冗余代码,从而避免过高的资源开销、不必要的复杂性和缺乏灵活性。

(3) 尽快建立原型。大多数人都认同“建立原型”(prototyping)是任何项目的一个重要组成部分。在Unix环境中,它是达成完美设计的主要工具。

(4) 舍高效率而取移植性。当Unix作为第一个可移植性系统而开创先河时,它曾掀起过轩然大波。今天,可移植性早被视作为现代软件设计中一个理所当然的特性。

(5) 使用纯文本文件来存储数据。可以看到在类Unix的系统中,所有的配置文件都是使用文本数据直接存储,一方面用户可以直接修改配置,另一方面也是为移植性考虑的。

(6) 充分利用软件的杠杆效应。很多程序员对可重用代码模块的重要性只有一些肤浅的认识。代码重用能帮助人们充分利用软件的杠杆效应。一些Unix程序员正是遵循这个强大的理念,在相对较短的时间内编写出大量应用程序。

(7) 使用shell脚步来提高杠杆效应和可移植性。shell脚步在软件设计中可谓是一把双刃剑,它可以加强软件的可重用性和可移植性。无论什么时候,只要有可能,编写shell脚本来替代C语言程序都不失为一个良好的选择。

(8) 避免强制的用户界面

(9) 让每个程序都成为过滤器(filter)。所有软件程序共有的最基本特性就是,它们只修改而从不创造数据。因此,基于软件的过滤器本质,人们应该把它们编写成执行过滤器任务的程序,管道就是Unix这一个特性的非常好代表。

google sparse hash set/map

google开源了hashtables的包,包括两个部分:

  • sparse, 比较节省空间space-efficient;
  • dense, 高效的查询效率 time-efficient;

同时接口兼容SCI的hash_map和hash_set, 并且提供了序列化的功能,非常赞~

下面是其官方的性能测试数据:可以看到sparse_hash_map比stl::map和hash_map节省2/3的空间,而dense_hash_map具备较高的查询,删除, insert性能,可以根据具体的应用

来使用不同的数据结构。

下载地址:http://code.google.com/p/sparsehash/

doc : http://google-sparsehash.googlecode.com/svn/trunk/doc/

SPARSE_HASH_MAP:
map_grow                  665 ns
map_predict/grow          303 ns
map_replace               177 ns
map_fetch                 117 ns
map_remove                192 ns
memory used in map_grow    84.3956 Mbytes

DENSE_HASH_MAP:
map_grow                   84 ns
map_predict/grow           22 ns
map_replace                18 ns
map_fetch                  13 ns
map_remove                 23 ns
memory used in map_grow   256.0000 Mbytes

STANDARD HASH_MAP:
map_grow                  162 ns
map_predict/grow          107 ns
map_replace                44 ns
map_fetch                  22 ns
map_remove                124 ns
memory used in map_grow   204.1643 Mbytes

STANDARD MAP:
map_grow                  297 ns
map_predict/grow          282 ns
map_replace               113 ns
map_fetch                 113 ns
map_remove                238 ns
memory used in map_grow   236.8081 Mbytes

google早期的索引结构介绍

最近一直在做索引压缩方面的事情,无意中看到了Jeff Dean大牛分享的google早期的索引结构,对于我们这种刚刚起步的搜索公司,还是很有启发意义的,收获还是比较大,所以就简单记录下。

1. 索引压缩常用的压缩算法

淘宝的一篇技术blog分享了一些比较常用的压缩算法:

  • varint (变长压缩): 字节对齐,压缩比不高
  • group varint: 变长压缩的变形,比varint的解压速率高很多,这里有它的实现
  • Gamma:  对比较小的数字压缩比会比较高,将数值分为两个部分: 一元编码(num_bits)+二进制编码
  • Simple9 + simple16: 对于32bit的空间进行组织,可存储多个数值
  • PForDelta + NewPForDelta: 比较新的压缩算法,压缩比和解压缩比都比较高效,适合于docid_delta的压缩

关于这些算法的相关介绍可以看下www.wikipedia.org,或者搜下对应的paper.

2. Google的索引结构

索引结构

可以看到,对于token的doclist是以Block的方式进行组织的,如果doclist比较长,还会使用skip table来快速查找;

Block的组织方式:

a. block header:  使用变长存储与上一个block的delta, 并存储block 实际的存储长度(可能是作为验证)

b. 第二行使用Gamma来压缩编码类型及在block中出现的docs的数目(因为这些数值都比较小)

c. 使用Rice压缩对应docld delta, 其实这里可以使用比较新的压缩算法PFDelta,更高效一些

d. 使用Gamma来压缩对应token在doc中出现的frequence, 即hit的数目

e. 使用length-limit Huffman 来存储Hit Attribute信息,这里主要是利用Attribute的重复的比例会很高,也就是说大部分hit  attribute

都会是相同的,所以用到了Huffman压缩,然后对length进行了限制

f: positions用Huffman-Int 来压缩位置信息,由于position分布不确定性很多,对position的压缩一直是业界的难题,压缩比不会很高。

Huffman-Int : 类似于Gamma压缩,但是对于一元编码部分,使用了Huffman code.

优化

这里其实可以将doclist和hit 信息进行分离存储,因为只有在打分的时候才会用到hit的相关信息,访问次数会比较少,而doclist就会访问比较频繁

可以对其进行Cache,这样Cache命中率会更高一些

2012xiao结

今天是腊月二十六,还在公司上班,看来今天是没有可能码代码,就静下心来回顾下2012年,看了前两年的总结,虽然只有寥寥几行,但是回味起来还是挺有味道的~ 所以记录下2012发生的事,算个总结吧!

关键词:毕业

2012.07.01正式从ICT毕业,正式结束了自己的学生生涯,也算是比较顺利;

从2月份过年回来,被拉去封闭开发了一段时间,大概有一个月的时间,那段时间也算是见识了下大场面,还被领导人接见了下哈~

之后回来开始搞毕业论文,这里也晒下毕业论文的题目:面向网络仿真的虚拟化网络IO优化研究与实现,是基于KVM虚拟机做的二次优化,加上研究生之前的工作和周大神的帮助,最后论文完成的比较顺利,顺利通过了论文的答辩,据说最后还被评为优秀毕业论文,哈哈,也算是最自己研究生三年的一个交代了~

回顾三年的研究生生涯,学术上没有啥成果,最后连一篇论文都没有发表,技术了稍微有些提高吧,接触了一些开源的项目的,但是比较遗憾的是没有专注于在上面,纯属打酱油状态,最后的收获就是认识了猛爷,彪爷和韬爷三位同学,现在韬爷已经飘洋过海,猛爷和彪爷最后就职于某靠谱的互联网公司,当然是希望韬爷以后带领我们完成屌丝的逆袭了。

关键词:工作

2012我也正式参加工作,最后去了一家伪互联网公司,提前了一个月去公司实习,提前熟悉环境,最后看来这个决定还是比较明智的,后面批量入职的同学都要被bt新人练习题折磨近一个月的时间,主要负责的工作是搜索引擎检索模块,还算比较靠谱;没过多久,公司来了位大牛,公司部门调整,我很荣幸的被分配到了该大牛的手下,作为我们这些刚走出校门的学生来说,真的是比较荣幸,同时我们陆续开始接手相关模块,开展相关工作,那段时间工作压力真的挺大,成长也比较快,松爷把威廉张的十六字口诀送给了我们:”想得仔细,说得清楚,写得精确,做得有力“,真正做到这16字很不容易。

好景不长,两个月后松爷就闪人了,其中也有各种原因, 留下了我们这些小兵,最后组里来了个吉大的校友继续领导我们,当前JOJ排行榜NO1, 我们的工作也没有受太多影响,继续推动着。

总得来说,工作半年多,还算比较适应,工作也算比较顺利,来年继续努力吧~~

关键词:生活

今年和小芳邓 只是在五一的时候回了趟母校,参加了下同学聚会,大家都变化不大,吃到了久违的菜煎饼,哈哈!

十一的时候又去了趟大城市铁岭, 商讨结婚事宜;别的地方好像就没去了,我印象中好像是没去,这个只能明年补上了~

关键词:2013

2013估计俺就该结婚了,结婚对象当然是小芳邓同学了,顺便可以度个蜜月;

希望工作顺利,技术上有比较大的成长;

定位多线程内存越界问题实践总结【转载学习】【淘宝大牛的分享】

linux gcc编译字节对齐设置方法

使用#pragma pack(n)

  • 伪指令#pragma pack (n),编译器将按照n 个字节对齐
  • 伪指令#pragma pack (),取消自定义字节对齐方式
#pragma pack(1)
struct my_align_struct {
  uint32 u0:8;
  uint32 u1:8;
  uint32 u2:8;
  uint32 u3:16;
};
#pragma pack()
sizeof(my_align_struct) == 5 // 默认情况下gcc是按照四字节对齐的,sizeof(my_align_struct) == 8.

使用__attribute__属性

struct my_align_struct {
  uint32 u0:8;
  uint32 u1:8;
  uint32 u2:8;
  uint32 u3:16;
}__attribute__((packed, aligned(1)));