乐者为王

Do one thing, and do it well.

Google Analytics中如何检测并防止垃圾流量

使用Google Analytics网站分析工具对博客进行数据统计。在经过一段时间的数据收集后,发现总是会有大量的垃圾流量存在。这里的垃圾流量,指的是对网站毫无作用且会影响网站数据报表质量的流量。通常Google Analytics中的垃圾流量可以分为以下两大类:

  • 一类被称为ghost referral,这些流量事实上从来没有来过你的网站,也不会出现在你网站服务器的日志中,但你可以在数据报表中发现它们,它们影响了Google Analytics中的数据;
  • 另一类是爬虫流量,包括搜索引擎爬虫流量和非搜索引擎爬虫流量,这些流量会影响Google Analytics中各渠道流量占比及会话次数、跳出率、停留时间等关键指标。

垃圾流量检测方法

打开报告 -> 受众群体 -> 技术 -> 广告网络 -> 主机名,统计报表如下图所示:

report-with-spam

可以看到,只有181个会话的主机名是我的博客域名,即真实来到我博客的流量,也就是说有超过一半的流量属于垃圾流量。并且这些垃圾流量基本都出现了不同程度的数据异常,如新会话百分比为0%、新用户为0、跳出率为100%、平均会话时长为00:00:00。这些垃圾流量的主机名与博客域名无关,说明是第一类垃圾流量。出现这类数据的原因可能是:

  • 别的网站使用了和你网站相同的媒体资源ID,这种情况一般来说不可能,除非恶意为之;
  • 有人使用Google Analytics中的Measurement Protocol做机器生成的访问流量,而你的媒体资源ID不幸躺枪。

使用过滤器屏蔽垃圾流量

打开“管理”页面,在博客帐号的“所有过滤器”下添加新的过滤条件,使用预定义或自定义均可,基本配置如下所示:

exclude-spam-filter

然后把“可选择的数据视图”中的选项添加到“选定的数据视图”中,保存即可。

过段时间后再回来查看报表,就会发现垃圾流量消失的干干净净了:

report-without-spam

ANTLR 4权威参考读书笔记(6)

  • action 动作
  • clause 子句

监听器和访问者机制是极好的。大多数时候,我们可以用监听器或访问者来构建语言应用,它们让特定应用的代码置身于语法之外,使语法容易被阅读。

但有时候我们需要额外的控制权和灵活性。为了达到这个目的,我们可以直接在语法中嵌入代码片段(这些嵌入的代码片段被称为动作)。这些动作会被注入到由ANTLR工具生成的分析器代码中。这些被注入的代码在分析期间执行,并且能像其它任意代码片段一样收集信息或生成输出。结合语义谓词,我们甚至可以在运行时让我们语法的某部分消失!例如,我们可能想打开或关闭Java语法中的enum关键字,分析语言的不同版本。没有语义谓词,我们就需要两个不同版本的语法。

下面我们将实现一个简单的程序,读入数据行,然后打印出在特定列中找到的值。

在语法中嵌入任意的动作

如果我们不想付出构建语法分析树的开销,或者想要在分析期间动态地计算值或把东西打印出来,那么可以通过在语法中嵌入任意代码来实现。它是比较困难的,因为我们必须明白在语法分析器上的动作的影响,以及在哪里放置这些动作。

为了解释嵌入在语法中的动作,让我们先来看下文件rows.txt中的数据:

1
2
3
parrt   Terence Parr    101
tombu   Tom Burns       020
bke     Kevin Edgar     008

这些列是由TAB分隔的,每行以一个换行符结束。匹配这种类型的输入在语法上还是相当简单的。下面是此语法文件Rows.g的内容:

1
2
file : (row NL)+ ;    // NL is newline token: '\r'? '\n'
row  : STUFF+ ;

我们需要创建一个构造器以便我们能传递我们想要的列号(从1开始计数),所以我们需要在规则中添加一些动作来做这个事情:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
grammar Rows;

@parser::members {    // add members to generated RowsParser
    int col;

    public RowsParser(TokenStream input, int col) {    // custom constructor
        this(input);
        this.col = col;
    }
}

file: (row NL)+ ;

row
locals [int i=0]
    : ( STUFF
        {
            $i++;
            if ($i == col) System.out.println($STUFF.text);
        }
      )+
    ;

TAB  :  '\t' -> skip ;    // match but don't pass to the parser
NL   :  '\r'? '\n' ;      // match and pass to the parser
STUFF:  ~[\t\r\n]+ ;      // match any chars except tab, newline

在上述语法中,动作是被花括号括起来的代码片段;members动作的代码将会被注入到生成的语法分析器类中的成员区;在规则row中的动作访问的$i是由locals子句定义的局部变量,该动作也用$STUFF.text获取最近匹配的STUFF记号的文本内容。STUFF词法规则匹配任何非TAB或换行的字符,这意味着在列中可以有空格字符。

现在,是时候去思考如何使用定制的构造器传递一个列号给语法分析器,并且告诉语法分析器不要构建语法分析树了:

1
2
3
4
5
6
7
8
9
10
11
12
public class Rows {

    public static void main(String[] args) throws Exception {
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        RowsLexer lexer = new RowsLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        int col = Integer.valueOf(args[0]);
        RowsParser parser = new RowsParser(tokens, col);    // pass column number!
        parser.setBuildParseTree(false);    // don't waste time bulding a tree
        parser.file();
    }
}

现在,让我们核实下我们的语法分析器能否正确匹配一些示例输入:

1
2
3
antlr -no-listener Rows.g  # don't need the listener
compile *.java
run Rows 1 < rows.txt

这时你会看到rows.txt文件的第1列内容被输出:

1
2
3
parrt
tombu
bke

如果将上面命令中的1换成2,你会看到文件的第2列内容被输出;如果换成3,那么第3列内容将会被输出。

一夜成名:这需要好几年时间

英文原文:http://blog.codinghorror.com/overnight-success-it-takes-years/

Gmail的原首席开发者Paul Buchheit说过Gmail的成功花了很长时间

我们在2001年8月开始开发Gmail。很长一段时间里,几乎每个人都不喜欢它。有些人使用它因为搜索,但他们有着无尽地抱怨。很多人认为我们应该杀死这个项目,又或者重启它作为一个有本地客户端软件的企业产品,而不是这个疯狂的JavaScript东西。甚至在2004年4月1日当我们到达发布它的那个点时——在开始开发它两年半之后——Google内部的很多人都在预测它的死亡。他们觉得这个产品太怪异了,并且没有人想去更换电子邮件服务。我被告知我们永远不会得到100万用户。

但在我们发布后,除了因为各种原因讨厌它的人,反响出人意外地好。尽管如此,它还是经常被描述为“小众产品(niche)”和“不会被硅谷之外的人使用”。

现在,在我们开始开发Gmail差不多七年半后,我看到一篇文章叙述Gmail如何在去年增长40%,相比Yahoo的2%和Hotmail的-7%。

Paul已经离开Google,现在在从事他自己的创业公司FriendFeed(译者注:FriendFeed已于2015年4月9日关闭)。许多业内人士对待FriendFeed不太友善。Stowe Boyd甚至竟然称FriendFeed就是个失败(译者注:Stowe Boyd评论FriendFeed的文章已经被删除了)。Paul从容应对批评:

创建一个重要的新产品通常需要时间。FriendFeed需要继续追求创新,就像Gmail六年以前做的那样。FriendFeed显示了很好的前景,但它仍然是一个“在制品”。

我的预期是很大的成功需要好几年时间,没有许多反例(除了YouTube,但现在它其实还没有到达挣成堆钱的那个点)。Facebook成长非常快,但它此时已经五岁了。Larry和Sergey 开始开发Google在1996年——当我开始在那里是1999年,几乎没人听说过它。

一夜成名的观念非常具有误导性,而且相当有害。如果你开始新的东西,那会是一次长途旅行。没有借口去行动缓慢。相反,你必须行动的非常快,否则你将不会到达,因为它是一次长途旅行!这也是为什么节俭是重要的——你不想饿死在半山腰上

Stowe Boyd用一张Twitter和FriendFeed的流量对比图说明他关于FriendFeed的观点。这里请允许我把我自己的数据也加到Boyd先生的图上:

three-traffic-comparison

我觉得Paul的态度令人耳目一新,因为对于我们的创业公司Stack Overflow我也采用同样的态度。我没有期望或甚至渴望一夜成名。我计划的是花上几年的时间去打磨,持续地、稳步地提升。

这项商业计划和我的职业生涯发展计划没有太多区别:成功需要好几年时间。当我说年的时候,我是认真的!不是在说像“更聪明地工作,而不是更努力地工作”那样的陈词滥调。我是在说真正的日历年。你知道的,12个月的,365天的那种。你必须花上你生命的多年时间孜孜不倦地钻研这些东西,每天醒来后一遍又一遍地做它。每天练习和收集反馈去不断变得更好。有时它可能是不愉快的,甚至偶尔是很无趣的,但它是必需的。

这几乎不是唯一的或有趣的建议。Peter Norvig的经典用十年自学编程也谈到过这个话题,而且讲得比我更好。

研究人员发现在任何领域都需要大约10年时间才能培养出专业技能,包括国际象棋、音乐作曲、电报操作、绘画、钢琴演奏、游泳、网球、以及神经心理学和拓扑学的研究。关键是刻意(deliberative)练习:不仅仅是一次又一次地做它,而是用略微超出你当前能力的任务来挑战自己,尝试它,在做时和做后分析你的表现,并且纠正所有错误。然后重复。再重复。

似乎没有真正的捷径:即使是莫扎特,4岁的音乐天才,在他开始创作世界级音乐前也花了超过13年。甲壳虫乐队似乎以一连串的冠军歌曲(a string of #1 hits)横空出世,并且在1964年出现在《埃德·沙利文秀》。但其实自1957年以来他们就已经在利物浦和汉堡的小俱乐部里演出了,虽然他们在早期有广泛的吸引力,但他们最最成功的《Sgt. Pepper's Lonely Hearts Club Band》发布在1967年。

老实说,我期待着有一天醒来,从现在起的2年或3年之后,做着和今天我在做的完全相同的事:为Stack Overflow编写代码,增加另一个微小的改进或有用的功能。很明显我们想要成功。但在某种程度上,成功是无关紧要的,因为这个过程本身是令人满意的。每天醒来做你喜欢的事情——甚至更好的是,周围社区的人也喜欢它——这本身就是一种奖赏。尽管有着成吨的工作要做。

博客也不例外。我经常给有抱负的博客作者这个很重要的建议:如果你开始你的博客,在六个月内别指望有人来读它。如果你这样做,我可以保证你将会非常失望。 可是,如果你能坚持发布计划并且每周写1篇或2篇高质量的博文一整年……然后,也只有到那个时候,你才可以看到稀稀落落的读者。我开始这个博客于2004年,花了整整3年的时间,每周写3到5篇博文,才使得它在软件开发社区内流行开来。

我非常期望在这个博客上一直写,以一种形式或另一种,用我的余生。它是我是谁的一部分。至于那种戏剧性的成名方式,我不抱有任何幻想:归根结底,我只是在网上写博客的那个人

pearls-before-swine

那样挺好的对我来说。我从来没有说过我是聪明的。

不管你最终获得多少读者,或页面浏览量,或任何我们这周正在度量的高分排行榜 ,请记住,你正在做的事情是值得去做的,因为——嗯——你正在做的事情是值得去做的。

如果你一直这样坚持下去,谁知道会发生什么?很有可能某天你醒过来,发现自己一夜成名了。

ANTLR 4权威参考读书笔记(5)

ANTLR 4权威参考读书笔记(3)以及ANTLR 4权威参考读书笔记(4)中我们分别用访问者和监听器机制实现了计算器的解释执行和编译执行。但并没有给出这两种机制的太多细节,这次就来详细地讲讲。

ANTLR在它的运行库中为两种树遍历机制提供支持。默认情况下,ANTLR生成一个语法分析树监听器接口,在其中定义了回调方法,用于响应被内建的树遍历器触发的事件。

在监听器和访问者机制之间最大的不同是:监听器方法被ANTLR提供的遍历器对象调用;而访问者方法必须显式的调用visit方法遍历它们的子节点,在一个节点的子节点上如果忘记调用visit方法就意味着那些子树没有得到访问。

让我们首先从监听器开始。在我们了解监听器之后,我们也将看到ANTLR如何生成遵循访问者设计模式的树遍历器。

语法分析树监听器

在Calc.java中有这样两行代码:

1
2
ParseTreeWalker walker = new ParseTreeWalker();
walker.walk(new DirectiveListener(), tree);

类ParseTreeWalker是ANTLR运行时提供的用于遍历语法分析树和触发监听器中回调方法的树遍历器。ANTLR工具根据Calc.g中的语法自动生成ParseTreeListener接口的子接口CalcListener和默认实现CalcBaseListener,其中含有针对语法中每个规则的enter和exit方法。DirectiveListener是我们编写的继承自CalcBaseListener的包含特定应用代码的实现,把它传递给树遍历器后,树遍历器在遍历语法分析树时就会触发DirectiveListener中的回调方法。

calc-listener-hierarchy

下图左边的语法分析树显示ParseTreeWalker执行了一次深度优先遍历,由粗虚线表示,箭头方向代表遍历方向。右边显示的是语法分析树的完整调用序列,它们由ParseTreeWalker触发调用。当树遍历器遇到规则assign的节点时,它触发enterAssign()并且给它传递AssignContext这个语法分析树节点的上下文。在树遍历器访问完assign节点的所有子节点后,它触发exitAssign()。

listener-call-sequence

监听器机制的强大之处在于所有都是自动的。我们不必要写语法分析树遍历器,而且我们的监听器方法也不必要显式地访问它们的子节点。

语法分析树访问者

有些情况下,我们实际想要控制的是遍历本身,在那里我们可以显式地调用visit方法去访问子树节点。参数-visitor告诉ANTLR工具从相应语法生成访问者接口和默认实现,其中含有针对语法中每个规则的visit方法。

下图是我们熟悉的访问者模式操作在语法分析树上。左边部分的粗虚线表示语法分析树的深度优先遍历,箭头方向代表遍历方向。右边部分指明访问者中的方法调用序列。

visitor-call-sequence

下面是Calc.java中的两行代码:

1
2
3
EvalVisitor eval = new EvalVisitor();
// To start walking the parse tree
eval.visit(tree);

我们首先初始化自制的树遍历器EvalVisitor,然后调用visit()去访问整棵语法分析树。ANTLR运行时提供的访问者支持代码会在看到根节点时调用visitProg()。在那里,visitProg()会把子树作为参数调用visit方法继续遍历,如此等等。

calc-visitor-hierarchy

ANTLR自动生成的访问者接口和默认实现可以让我们为访问者方法编写自己的实现,让我们避免必须覆写接口中的每个方法,仅仅聚焦在我们感兴趣的方法上。这种方式减少了我们学习ANTLR必须要花费的时间,让我们回到我们所熟悉的编程语言领域。

ANTLR 4权威参考读书笔记(4)

ANTLR 4权威参考读书笔记(3)中的计算器是以解释的方式执行的,现在我们想要把它转换成以编译的方式执行。编译执行和解释执行相比,需要依赖于特定的目标机器。在这里我们假设有一台这样的机器,它用堆栈进行运算,支持如下表所示的几种指令:

指令 说明 运算元数目 用途
LDV Load Variable 1 变量入栈
LDC Load Constant 1 常量入栈
STR Store Value 1 栈顶一个元素存入指定变量
ADD Add 0 栈顶两个元素出栈,求和后入栈
SUB Subtract 0 栈顶两个元素出栈,求差后入栈
MUL Multiply 0 栈顶两个元素出栈,求积后入栈
DIV Divide 0 栈顶两个元素出栈,求商后入栈
RET Return 0 栈顶一个元素出栈,计算结束

做这个最简单的方法是使用ANTLR的语法分析树监听器机制实现DirectiveListener类,然后它通过监听来自树遍历器触发的事件,输出对应的机器指令。

监听器机制的优势是我们不必要自己去做任何树遍历,甚至我们不必要知道遍历语法分析树的运行时如何调用我们的方法,我们只要知道我们的DirectiveListener类得到通知,在与语法规则匹配的短语开始和结束时。这种方式减少了我们学习ANTLR必须要花费的时间,让我们回到我们所熟悉的编程语言领域。

这里不需要创建新的语法规则,还是继续沿用前文Calc.g所包含的语法,标签也要保留:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
grammar Calc;

prog
    : stat+
    ;

stat
    : expr                   # printExpr
    | ID '=' expr            # assign
    ;

expr
    : expr op=(MUL|DIV) expr # MulDiv
    | expr op=(ADD|SUB) expr # AddSub
    | INT                    # int
    | ID                     # id
    | '(' expr ')'           # parens
    ;

MUL : '*' ;

DIV : '/' ;

ADD : '+' ;

SUB : '-' ;

ID  : [a-zA-Z]+ ;

INT : [0-9]+ ;

WS  : [ \t\r\n]+ -> skip ;    // toss out whitespace

然后,我们可以运行ANTLR工具:

1
antlr Calc.g

它会生成后缀名为tokens和java的六个文件:

1
2
Calc.tokens         CaclLexer.java          CalcParser.java
CalcLexer.tokens    CalcBaseListener.java   CalcListener.java

正如这里我们看到的,ANTLR会为我们自动生成监听器基础设施。其中CalcListener是语法和监听器对象之间的关键接口,描述我们可以实现的回调方法:

1
2
3
4
public interface CalcListener extends ParseTreeListener {
    void enterProg(CalcParser.ProgContext ctx);
    void exitProg(CalcParser.ProgContext ctx);
    void enterPrintExpr(CalcParser.PrintExprContext ctx);

CalcBaseListener则是ANTLR生成的一组空的默认实现。ANTLR内建的树遍历器会去触发在监听器中像enterProg()和exitProg()这样的一串回调方法,如同它对语法分析树执行了一次深度优先遍历。为响应树遍历器触发的事件,我们的DirectiveListener需要继承CalcBaseListener并实现一些方法。我们不需要实现全部的接口方法,我们也不需要去覆写每个enter和exit方法,我们只需要去覆写那些我们感兴趣的回调方法。

在本例中,我们需要通过覆写6个方法对6个事件——当树遍历器exit那些有标签的选项时触发——作出响应。我们的基本策略是当这些事件发生时打印出已转换的指令。以下是完整的实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class DirectiveListener extends CalcBaseListener {

    @Override
    public void exitPrintExpr(CalcParser.PrintExprContext ctx) {
        System.out.println("RET\n");
    }

    @Override
    public void exitAssign(CalcParser.AssignContext ctx) {
        String id = ctx.ID().getText();
        System.out.println("STR " + id);
    }

    @Override
    public void exitMulDiv(CalcParser.MulDivContext ctx) {
        if (ctx.op.getType() == CalcParser.MUL) {
            System.out.println("MUL");
        } else {
            System.out.println("DIV");
        }
    }

    @Override
    public void exitAddSub(CalcParser.AddSubContext ctx) {
        if (ctx.op.getType() == CalcParser.ADD) {
            System.out.println("ADD");
        } else {
            System.out.println("SUB");
        }
    }

    @Override
    public void exitId(CalcParser.IdContext ctx) {
        System.out.println("LDV " + ctx.ID().getText());
    }

    @Override
    public void exitInt(CalcParser.IntContext ctx) {
        System.out.println("LDC " + ctx.INT().getText());
    }
}

为了让它运行起来,余下我们唯一需要做的事是创建一个主程序去调用它:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Calc {

    public static void main(String[] args) throws Exception {
        InputStream is = args.length > 0 ? new FileInputStream(args[0]) : System.in;

        ANTLRInputStream input = new ANTLRInputStream(is);
        CalcLexer lexer = new CalcLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        CalcParser parser = new CalcParser(tokens);
        ParseTree tree = parser.prog();

        ParseTreeWalker walker = new ParseTreeWalker();
        walker.walk(new DirectiveListener(), tree);

        // print LISP-style tree
        System.out.println(tree.toStringTree(parser));
    }
}

这个程序和前文Calc.java中的代码极度相似,区别只在12-13行。这两行代码负责创建树遍历器,然后让树遍历器去遍历那颗从语法分析器返回的语法分析树,当树遍历器遍历时,它就会触发调用到我们的DirectiveListener中实现的方法。此外,通过传入一个不同的监听器实现我们能简单地生成完全不同的输出。监听器机制有效地隔离了语法和语言应用,使语法可以被其它应用再次使用。

现在一切完备,让我们尝试着去编译和运行它吧!下面是完整的命令序列:

1
2
compile *.java
run Calc calc.txt

编译的输出结果如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LDC 19
RET

LDC 5
STR a
LDC 6
STR b
LDV a
LDV b
LDC 2
MUL
ADD
RET

LDC 1
LDC 2
ADD
LDC 3
MUL
RET

ANTLR 4权威参考读书笔记(3)

  • lexical 词法的
  • alternative 选项
  • notation 表示法
  • directive 指令
  • label 标签

了解ANTLR最好的方法就是实例。构建一个简单的计算器是个不错的主意。为了使它容易理解且保持简单,我们将只允许基本的算术运算符(加、减、乘、除)、括号表达式、整数和变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
grammar Calc;

prog
    : stat+
    ;

stat
    : expr
    | ID '=' expr
    ;

expr
    : expr ('*'|'/') expr
    | expr ('+'|'-') expr
    | INT
    | ID
    | '(' expr ')'
    ;

ID  : [a-zA-Z]+ ;

INT : [0-9]+ ;

WS  : [ \t\r\n]+ -> skip ;    // toss out whitespace

在上述的语法中,程序是由空格(换行符也被当作空格)终止的语句序列,语句可以是表达式或者赋值。那些以小写字母开头的像stat和expr是语法规则;由大写字母开头的诸如ID和INT为词法规则,用于识别标志符和整数这样的记号。我们用“|”分隔规则的选项,我们也可以用“()”把符号分组成子规则。例如,子规则('*'|'/')匹配乘法符号或者除法符号。

ANTLR v4最重要的新特性是它有能力处理(大多数类型的)左递归规则。例如,规则expr前两个选项就在左边缘递归地调用了expr自身。这种指定算术表达式表示法的方法比那些典型的自顶向下语法分析器策略更容易。当然,在这种策略下,我们需要定义多个规则,每个运算符优先级一个规则。

记号定义的表示法对那些有正则表达式经验的应该很熟悉。唯一不寻常的是在WS规则上的-> skip指令,它告诉词法分析器去匹配但丢弃空格,不要把它们放到记号流中,这样在语法分析树上空格就不会有对应的记号。(每个可能的输入字符都必须被至少一个词法规则匹配。)我们通过使用形式化的ANTLR表示法避免捆绑语法到某个特定的目标语言,而不是在语法中插入任意代码片段来告诉词法分析器去忽略。

这里是一些用来评估所有语法特性的测试序列:

1
2
3
4
5
193
a=5
b=6
a+b*2
(1+2)*3

把它们放入文件calc.txt中,然后执行以下命令:

1
2
3
antlr Calc.g
compile *.java
grun Calc prog -gui calc.txt

TestRig会弹出一个显示语法分析树的窗口:

calc-parse-tree

使用访问者模式计算结果

为了让前面的算术表达式语法分析器计算出结果,我们还需要做些其它的事情。

ANTLR v4鼓励我们使用语法分析树访问者和其它遍历器来实现语言应用,以保持语法的整洁。不过在接触这些之前,我们需要对语法做些修改。

首先,我们需要用标签标明规则的选项,标签可以是和规则名没有冲突的任意标志符。如果选项上没有标签,ANTLR只会为每个规则生成一个visit方法。

在本例中,我们希望为每个选项生成一个不同的visit方法,以便每种输入短语都能得到不同的事件。在新的语法中,标签出现在选项的右边缘,且以“#”符号开头:

1
2
3
4
5
6
7
8
9
10
11
12
stat
    : expr                   # printExpr
    | ID '=' expr            # assign
    ;

expr
    : expr op=(MUL|DIV) expr # MulDiv
    | expr op=(ADD|SUB) expr # AddSub
    | INT                    # int
    | ID                     # id
    | '(' expr ')'           # parens
    ;

接下来,让我们为运算符字面量定义一些记号名字,以便以后可以在visit方法中引用作为Java常量的它们:

1
2
3
4
5
6
7
MUL : '*' ;

DIV : '/' ;

ADD : '+' ;

SUB : '-' ;

现在,我们有了一个增强型的语法。接下来要做的事情是实现一个EvalVisitor类,它通过遍历表达式语法分析树计算和返回值。

执行下面的命令,让ANTLR生成访问者接口和它的默认实现,其中-no-listener参数是告诉ANTLR不再生成监听器相关的代码:

1
antlr -no-listener -visitor Calc.g

所有被标签标明的选项在生成的访问者接口中都定义了一个visit方法:

1
2
3
4
5
6
public interface CalcVisitor<T> extends ParseTreeVisitor<T> {
    T visitProg(CalcParser.ProgContext ctx);
    T visitPrintExpr(CalcParser.PrintExprContext ctx);
    T visitAssign(CalcParser.AssignContext ctx);
    ...
}

接口定义使用的是Java泛型,visit方法的返回值为参数化类型,这允许我们根据表达式计算返回值的类型去设定实现的泛型参数。因为表达式的计算结果是整型,所以我们的EvalVisitor应该继承CalcBaseVisitor<Integer>类。为计算语法分析树的每个节点,我们需要覆写与语句和表达式选项相关的方法。这里是全部的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class EvalVisitor extends CalcBaseVisitor<Integer> {
    /** "memory" for our calculator; variable/value pairs go here */
    Map<String, Integer> memory = new HashMap<String, Integer>();

    /** ID '=' expr */
    @Override
    public Integer visitAssign(CalcParser.AssignContext ctx) {
        String id = ctx.ID().getText();  // id is left-hand side of '='
        int value = visit(ctx.expr());   // compute value of expression on right
        memory.put(id, value);           // store it in our memory
        return value;
    }

    /** expr */
    @Override
    public Integer visitPrintExpr(CalcParser.PrintExprContext ctx) {
        Integer value = visit(ctx.expr()); // evaluate the expr child
        System.out.println(value);         // print the result
        return 0;                          // return dummy value
    }

    /** INT */
    @Override
    public Integer visitInt(CalcParser.IntContext ctx) {
        return Integer.valueOf(ctx.INT().getText());
    }

    /** ID */
    @Override
    public Integer visitId(CalcParser.IdContext ctx) {
        String id = ctx.ID().getText();
        if ( memory.containsKey(id) ) return memory.get(id);
        return 0;
    }

    /** expr op=('*'|'/') expr */
    @Override
    public Integer visitMulDiv(CalcParser.MulDivContext ctx) {
        int left = visit(ctx.expr(0));  // get value of left subexpression
        int right = visit(ctx.expr(1)); // get value of right subexpression
        if ( ctx.op.getType() == CalcParser.MUL ) return left * right;
        return left / right; // must be DIV
    }

    /** expr op=('+'|'-') expr */
    @Override
    public Integer visitAddSub(CalcParser.AddSubContext ctx) {
        int left = visit(ctx.expr(0));  // get value of left subexpression
        int right = visit(ctx.expr(1)); // get value of right subexpression
        if ( ctx.op.getType() == CalcParser.ADD ) return left + right;
        return left - right; // must be SUB
    }

    /** '(' expr ')' */
    @Override
    public Integer visitParens(CalcParser.ParensContext ctx) {
        return visit(ctx.expr()); // return child expr's value
    }
}

以前开发和测试语法都是使用的TestRig,这次我们试着编写计算器的主程序来启动代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Calc {

    public static void main(String[] args) throws Exception {
        InputStream is = args.length > 0 ? new FileInputStream(args[0]) : System.in;

        ANTLRInputStream input = new ANTLRInputStream(is);
        CalcLexer lexer = new CalcLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        CalcParser parser = new CalcParser(tokens);
        ParseTree tree = parser.prog();

        EvalVisitor eval = new EvalVisitor();
        // 开始遍历语法分析树
        eval.visit(tree);

        System.out.println(tree.toStringTree(parser));
    }
}

创建一个运行主程序的脚本:

1
2
#!/bin/sh
java -cp .:./antlr-4.5.1-complete.jar:$CLASSPATH $*

把它保存为run.sh后,执行以下命令:

1
2
compile *.java
run Calc calc.txt

然后你就会看到文本形式的语法分析树以及计算结果:

1
2
3
4
5
6
193
17
9
(prog (stat (expr 193)) (stat a = (expr 5)) (stat b = (expr 6))
 (stat (expr (expr a) + (expr (expr b) * (expr 2)))) (stat (expr
 (expr ( (expr (expr 1) + (expr 2)) )) * (expr 3))))

带权随机函数

  • 设计抽奖活动时,我们总是要控制抽奖物品出现的概率,让好的东西很难被抽到;
  • 设计游戏打怪时,我们要控制打怪时的命中概率,要控制宝物掉出的概率;
  • 网站的置顶广告,我们也要根据广告主的广告费用控制广告的出现时间;
  • 设计负载均衡算法时,我们要根据服务器的性能控制服务器被选中的可能。

深入思考这些需求,你会发现它们都有相通的概念:每次从多个候选项中随机选取其中一项,要求每个候选项的出现都有一定的概率。

假设有这样的候选项和对应概率:a:20%,b:25%,c:40%,d:15%。现在,把每个候选项的概率用一个称之为权重的正整数表示(最简单的方法是把百分符号去掉)。那么,

1
实际概率 = 候选项权重 / 权重总和 * 100%

事实上,权重的总和不一定要等于100,可以是任意大小。

算法描述

依次将各候选项的权重从原点开始放在x轴坐标上首尾相连。这样,每个候选项对应一个取值区间,在总区间范围内随机选取一个值,该值所在区间就对应了选中的项。

random-with-weight

Ruby代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def random(weight)
  # 获取所有候选项的权重总和
  total_weight = weight.inject { |r, e| r + e }

  # 随机选取一个介于0到权重总和之间的整数
  rand_value = rand(total_weight)  # [0, total_weight)

  # 扫描所有候选项,并且保留候选项权重的累积数。
  # 每当随机数小于累积数时,就停止并选出当前项。
  weight_barrier = 0
  weight.each_index do |i|
    weight_barrier += weight[i]

    break i if rand_value < weight_barrier
  end
end

该实现不能保证每个候选项都恰好按正确的比例被选中,但当次数足够多时,应该会十分接近预先设定的比例。

实际案例

要求写int[] get_weight(int[] weight)函数,返回的是权重的索引。其中weight是权重的数字数组,最终的结果是要大概保证按照给定的比例。

  • 比如weight为[1, 2, 2],那么权重比例为1:2:2,执行10次后,大概的输出是0 1 1 0 1 1 2 2 2 2;
  • 比如weight为[100, 0],那么权重比例为100:0,执行10次后,大概的输出是0 0 0 0 0 0 0 0 0 0;
  • 比如weight为[1, 1],那么权重比例为1:1,执行10次后,大概的输出是0 1 0 1 0 0 1 1 0 1。
1
2
3
4
5
6
7
8
9
10
11
12
def get_weight(weight)
  10.times.map { random(weight) }
end

weight = [1, 2, 2]
puts get_weight(weight).join(' ')

weight = [100, 0]
puts get_weight(weight).join(' ')

weight = [1, 1]
puts get_weight(weight).join(' ')

逻辑题-共打了多少鱼

abcde五人打渔,打完睡觉,a先醒来,扔掉1条鱼,把剩下的分成5份,拿1份走了;b再醒来,也扔掉1条,把剩下的分成5份,拿1份走了;然后cde都按上面的方法取鱼。问他们最少打了多少条鱼?

渔民 醒来时鱼的总数 取走的鱼数
a x1 = x (x1 - 1) / 5
b x2 = 4 * (x1 - 1) / 5 (x2 - 1) / 5
c x3 = 4 * (x2 - 1) / 5 (x3 - 1) / 5
d x4 = 4 * (x3 - 1) / 5 (x4 - 1) / 5
e x5 = 4 * (x4 - 1) / 5 (x5 - 1) / 5

由于扔掉1条鱼后,还能被分成5份,设渔民醒来时鱼的总数为remain,那么(remain - 1) % 5的值为0,即remain % 5的值为1。

最简单的方法就是枚举,最小值从1开始:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fishmen = [0, 0, 0, 0, 0]  # 渔民取走的鱼数
total = 1

while true do
  remain = total  # 渔民a醒来时鱼的总数
  5.times do |i|  # 5个渔民轮流取鱼
    break if remain % 5 != 1  # 如果不符合扔掉1条鱼后还能分成5份的条件,就枚举下个值
    fishmen[i] = (remain - 1) / 5  # 渔民取走的鱼数
    remain = 4 * fishmen[i]  # 渔民取走鱼后剩下的鱼数
  end
  break if fishmen[4] != 0  # 如果渔民e也取到了鱼,那么就得到了鱼的总数
  total += 1
end

puts total  # 结果是3121条鱼

上面的代码总过做了3901次循环,下面来做进一步的优化。

从表格可以看出,因为(x5 - 1) % 5 == 0,推导出x5 >= 6;又x1 % 5 == 1,因此x1的个位数必须是1或者6。所以,枚举的最小值可以从11开始,每次步进为5。优化后的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fishmen = Array.new(n, 0)
total = 11

while true do
  remain = total
  5.times do |i|
    break if remain % 5 != 1
    fishmen[i] = (remain - 1) / 5
    remain = 4 * fishmen[i]
  end
  break if fishmen[4] != 0
  total += 5
end

puts total

总的循环次数减少到1401次,减少了整整64%的循环。

推而广之:n个渔民打渔,每个渔民依次扔掉1条鱼后,把鱼分成n份,然后拿走其中一份,求最少打了多少条鱼?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fishmen = Array.new(n, 0)
total = 2 * n + 1

while true do
  remain = total
  n.times do |i|
    break if remain % n != 1
    fishmen[i] = (remain - 1) / n
    remain = remain - 1 - fishmen[i]
  end
  break if fishmen[n - 1] != 0
  total += n
end

puts total

这下子无论多少个渔民打渔都可以用这段代码搞定了。我试了试9个渔民,发现竟然可以打近3.9亿条鱼,那得有多少鱼啊!另外,计算时间也明显开始变长了。不知道还能不能做更进一步的优化。如果你有更好的算法,请快点告诉我吧!

写出受欢迎的编程文章的10个技巧

英文原文:http://www.devx.com/blog/2009/01/10-tips-for-writing-consistent.html

对于作者,这是一个可悲的事实。当谈到受大众欢迎时,不是所有的文章都是平等的,一些文章被证明比其它的更受欢迎。事实是,不管你选的主题有多好,或者你写的有多好,你都无法保证每次都能打出本垒打。尽管如此,如果你已经在写编程的文章(或者你正在考虑写),这里列出的技巧被证明能帮助文章从沉闷乏味的堆里跃升至最多查看次数列表的顶部。

1. 选择一个简练的话题

挑选一个简练的话题是艰难的,因为很多有趣的话题一点也不简洁,它们是冗长的和复杂的。有时候你可以创建很好的独立文章作为一个较长的话题,但通常不要这样做。相反,你可能需要写一个系列或一本书。要么选择别的,要么把这个话题分成简练的块。

接下来的几个技巧可以帮助你满足技巧#1的要求:

2. 增强现有的文档

一些最受欢迎的文章本质上是增强文档。那并没有什么错,因为技术文档通常是匆忙产生的,是不完整的,不是由开发者编写的,或缺乏相关的例子。在几乎所有情况下,文档(或文档的缺乏)给作者提供了丰富的话题。

3. 比较事物

另一个屡屡受欢迎的策略是写比较两个或多个受欢迎的项目的文章。这些可以是语言、语言版本、APIs、数据库、操作系统、框架、编程方法、模式——在快速变化的开发者世界中,有着无数的机会。挑两个或多个开发者使用的技术,并且写那种最好能帮助开发者转型或选择它们的文章。

4. 列个清单

你可能会认为这是陈词滥调,但“10 for/about”类型的文章往往表现的很好。(如果这篇博文做的很好,我会认为它验证了这个观点,如果没有的话,或许我会减少成“9个技巧……”)。编辑们和出版商们喜欢这些文章,因为读者喜欢它们。我怀疑读者喜欢它们是因为包含很多内容的文章增加了概率,因为这些文章至少包含有一个需要的或有趣的材料,但也许人们只是喜欢列表。无论如何……

在你有一个坚实的话题后,你准备开始写作,请记住这些观点:

5. 忽视历史

是的,我知道你认为每个人在切入正题前都需要了解特定主题的历史背景,但事实是,他们很少这样做。比起你在高中学习代数时让你的父亲解释数学的历史,你的读者不再想思考你的历史评论。这里有个读者行为分析的内部技巧:大部分读者从来没有读完过第一页。所以,如果你没有回答他们的问题,或立即抓住他们的兴趣,不管你的文章的其余部分有多么正确,他们都不会看。链接到历史,切入正题。

6. 避免“HelloWorld”例子

在你读过的文章和书里你看到过一千个“HelloWorld”的代码例子,但这并不意味着它们是好的!它们不是。没有人喜欢它们。对于学习编程的任何事情它们是完全无用的。它们也不是娱乐。完全有可能写出清晰而简单的既可以教又不烦闷的例子。

7. 说明你的观点

开发者喜欢代码,的确,但你也可以通过包含插图和截图帮他们节省时间和精力。这是因为他们中的许多人可能不会运行你那迷人的示例代码,但如果他们正在阅读你的文章,他们很可能对结果感兴趣。显示输入或输出无论何时都很重要。

8. 显示有趣的代码

许多技术作者似乎认为,在简短的解释之后提供大量的示例代码(或者更糟糕的是,只是显示代码而没有解释)将刺激他们的读者研究代码以获得启示。我向你保证那不是真的。最好的文章解释了话题,但只显示代码片断,然后解释或说明(或两者)代码做了什么,它如何与周围的代码或整体的话题适应,什么时候你应该使用它,什么时候不应该,也只有到那时——仅且当它是真正有用的时候——他们会向你打听更长的代码块。相反,只放有趣的代码在你的文章里,并将其余部分作为可运行的、完整的项目以供下载。

9. 化繁为简

避免冲动去告诉人们你的主题是多么地复杂。他们知道它是复杂的,或者他们很可能不会读你的文章。相反,想办法去让复杂的主题看起来更简单。

也许是所有技巧中最重要的一点:

10. 简明扼要

最受欢迎的技术文章只给读者他们需要的——没有更多。

最后,这是真的,有些文章很受欢迎,尽管它很少有甚至没有在这里列出的特性——但那并不是你可以控制的东西。尝试去写那种文章就像是博顺子,你会浪费大部分的时间。专注于基础,写大量的文章,然后其中的某些人将会成为赢家。

快乐写作。

在Application对象里存储数据的陷阱

看到Don't Store Data in the Application Object讲,在Application对象中存储共享数据会引起NullPointerException。顿时心里就咯噔了一下,用了四分之三秒,想起自己有个业余项目就干了这样的事。赶紧地测试看看。

打开应用,从MainActivity进入TxtViewerActivity界面(这里MainActivity主要是读取目录数据,然后保存在继承自Application的MainApp中,供TxtViewerActivity调用)。按手机Home键退出应用,这时你按菜单键可以看到该应用的缩图。然后在Eclipse中打开Window -> Show View -> Other -> Android -> Devices视图,双击窗口内的设备,然后点击设备下对应的进程,点击右上方红色的“Stop Process”图标。

android-devices

重新按菜单键打开应用,然后……然后果然在LogCat中看到了有NullPointerException的大段红色警告文字。

为什么会Crash的?

根本原因在于:当应用被kill掉后,通过菜单键重新打开时,应用不会开始重新启动。Android系统会新建一个Application对象,然后启动上次离开时的TxtViewerActivity以造成这个应用从来没有被kill掉的假象。因为没有经过MainActivity的数据读取,所以在TxtViewerActivity中读取数据当然要抛出异常了。

有没有替代方法呢?

  • 直接将数据通过Intent传递给TxtViewerActivity?当然也会碰到上述同样的问题。
  • 使用SharedPreferences?可惜只能存储boolean、int、long、float和String五种数据类型,不支持List的存储;
  • 使用持久化存储?也不支持List的存储,而且太笨重了;
  • 使用Singleton对象保存共享数据,然后通过Intent传递呢?这个想法不错,还可以将读取assets资源等操作移到该对象中,做到单一职责原则,改善设计。不过这样一来Singleton对象会对MainActivity的context有长期引用,容易造成内存泄露。如果不把读取操作放进去……那根本就不可能,你能让一个追求完美的程序猿忍受糟糕的代码设计吗!

幸好早就有人总结出来经验了:使用Application的context代替Activity的context。

创建Singleton对象,在Application对该对象保持引用,把原来存储在Application中共享的数据全部移到Singleton对象中,将Activity中读取assets资源等操作也放入该对象,Activity中原来对Application对象的访问改成通过Application对象对Singleton对象的访问。

这样修改后,不光解决了应用的崩溃,还预防了内存泄漏,更改进代码的设计。

代码下载:https://github.com/dohkoos/txtReader