2013年五月

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
    最后运行时要点击”播放(循环)”按钮,否则只会执行一行就会退出了,同时设置最大的行数