乐者为王

Do one thing, and do it well.

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会弹出一个显示语法分析树的窗口:

使用访问者模式计算结果

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

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))))

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

  • token 记号
  • ambiguity 二义性

安装ANTLR

ANTLR是由Java写成的,所以在安装ANTLR前必须保证已经安装有Java 1.6或以上版本。你可以到 http://www.antlr.org/download.html 下载ANTLR的最新版本,或者也可使用命令行工具下载:

1
curl -O http://www.antlr.org/download/antlr-4.5.1-complete.jar

antlr-4.5.1-complete.jar包含运行ANTLR工具的所有必要依赖,以及编译和执行由ANTLR生成的识别器所需的运行库。ANTLR工具将由语法文件描述的语法转换成识别程序,识别程序利用ANTLR运行库中的某些支持类识别输入的语句。该jar包还包含两个支持库:TreeLayout(一个复杂的树布局库)StringTemplate(一个用于生成代码和其它结构化文本的模板引擎)

现在来测试下ANTLR工具是否工作正常:

1
java -jar antlr-4.5.1-complete.jar  # 启动org.antlr.v4.Tool

如果正常的话会看到以下帮助信息:

1
2
3
4
ANTLR Parser Generator  Version 4.5.1
 -o ___              specify output directory where all output is generated
 -lib ___            specify location of grammars, tokens files
 ...

每次运行ANTLR工具都要输入这么长的命令是否有些痛苦?写个脚本来解放我们的手指吧!

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

把它保存为antlr.sh,以后就可以使用下列命令来运行ANTLR工具了:

1
antlr

执行ANTLR和测试识别器

先看下面这段用于识别像hello world那样短语的简单语法:

1
2
3
4
5
grammar Hello;               // 定义语法的名字

s  : 'hello' ID ;            // 匹配关键字hello,后面跟着一个标志符
ID : [a-z]+ ;                // 匹配小写字母标志符
WS : [ \t\r\n]+ -> skip ;    // 跳过空格、制表符、回车符和换行符

把以上语法保存为Hello.g,然后执行以下命令来生成识别器:

1
antlr Hello.g

该命令会在相同目录下生成后缀名为tokens和java的六个文件:

1
2
Hello.tokens        HelloLexer.java         HelloParser.java
HelloLexer.tokens   HelloBaseListener.java  HelloListener.java

现在开始准备编译由ANTLR生成的Java代码。先写个脚本把编译命令包装起来:

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

把它保存为compile.sh文件,然后你就可以用以下命令编译代码了:

1
compile *.java

到此,我们已经有了一个可以被执行的识别器,只缺一个主程序去触发语言识别了。

ANTLR运行库有提供称之为TestRig的测试工具,可以让你不创建主程序就能测试语法。TestRig使用Java反射调用编译后的识别器,它能显示关于识别器如何匹配输入的大量信息。

同样地,创建一个脚本grun.sh来简化以后的打字数:

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

现在,让我们来打印出识别期间创建的那些记号(记号是指像关键字hello和标识符world那样的词汇符号):

1
grun Hello s -tokens

敲入上述命令并按回车,接着输入以下内容:

1
2
hello world  # 输入并按回车
EOF          # Unix系统输入Ctrl+D或Windows系统输入Ctrl+Z并按回车

TestRig会打印出记号列表,每一行输出表示一个记号以及它的有关信息:

1
2
3
[@0,0:4='hello',<1>,1:0]
[@1,6:10='world',<2>,1:6]
[@2,13:12='<EOF>',<-1>,2:0]

这里详细讲解下[@1,6:10='world',<2>,1:6]的意义。@1表示记号索引(从0开始);6:10表示记号开始与结束的位置(从0开始);<2>表示记号类型,具体数值和类型存储在后缀名为tokens的文件中;最后的1:6表示记号在第一行(从1开始),从第6个字符开始(从0开始,制表符作为单个字符计算)。

除此之外,还可以以LISP风格的文本形式查看记号:

1
grun Hello s -tree

它会输出如下形式的记号:

1
(s hello world)  # (root children)

你也可以以可视化的方式查看语法分析树:

1
grun Hello s -gui

以下是TestRig可用的所有参数:

  • -tokens 打印出记号流。
  • -tree 以LISP风格的文本形式打印出语法分析树。
  • -gui 在对话框中可视化地显示语法分析树。
  • -ps file.ps 在PostScript中生成一个可视化的语法分析树表示,并把它存储在file.ps文件中。
  • -encoding encodingname 指定输入文件的编码。
  • -trace 在进入/退出规则前打印规则名字和当前的记号。
  • -diagnostics 分析时打开诊断消息。此生成消息仅用于异常情况,如二义性输入短语。
  • -SLL 使用更快但稍弱的分析策略。

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

  • grammar 语法,一种形式化(formal)的语言描述。
  • syntax 句法
  • phrase 短语
  • lexer 词法分析器
  • parser 语法分析器
  • parse tree 语法分析树,表示语法如何匹配输入的数据结构。
  • tree walker 树遍历器
  • top-down 自顶向下
  • listener 监听器
  • visitor 访问者
  • backtracking 回溯
  • semantic predicates 语义谓词

ANTLR v4是一款强大的语法分析器生成器,可以用来读取,处理,执行和转换结构化文本或二进制文件。通过语法文件,ANTLR可以自动生成词法分析器、语法分析树和树遍历器。

ANTLR v4的语法分析器使用一种新的分析技术称之为Adaptive LL(*)ALL(*),是v3 LL(*)的扩展,它可以在生成的语法分析器执行前在运行时动态地执行语法分析而不是静态地。

ANTLR v4极大地简化了用来匹配像算术表达式语法结构的语法规则。对于传统的自顶向下的语法分析器生成器像ANTLR v3,识别表达式的最自然的语法是无效的,v4则不然。ANTLR v4会自动地重写左递归规则为非左递归等价物,唯一的约束是左递归必须是直接的——规则立刻引用它自身。

此前,ANTLR v3用户必须用树构造操作来增强语法。现在,ANTLR v4会自动构建语法分析树,也会以监听器和访问者模式实现的形式自动生成树遍历器。所以,你不再需要构建树语法,可以用访问者模式代替。降低在语法中嵌入动作的重要性使得甚至可以在不重新编译生成的语法分析器的情况下在不同的应用中复用相同的语法。

ANTLR v3的LL(*)分析策略弱于v4的ALL(*),因此v3有时候需要依赖回溯去正确地分析输入的短语。回溯使得很难去通过生成的语法分析器步进调试语法,因为语法分析器可能会分析相同的输入多次(递归地);回溯也让语法分析器在无效的输入之上给出一个好的错误消息更难。

这本书里有什么?

免费在线文档提供了足够的资料用于学习基本的语法和语义,但没有详细地解释ANTLR的概念。只有这本书解释了如何识别语言的语法模式,以及如何用ANTLR语法表示它们。这本书也将帮助你充分的了解ANTLR,是成为高级用户的必读物。

这本书被组织成四个部分。

  • 第一部分介绍ANTLR,提供一些语言的背景知识,带你开始一场ANTLR功能之旅,让你尝下语法的滋味和能用它做什么。
  • 第二部分是关于使用ANTLR语法结合树遍历器设计语法和构建语言应用。
  • 第三部分首先展示了如何定制ANTLR生成的语法分析器的错误处理。接下来,你将学习如何在语法中嵌入动作,因为有时候这样做比构建语法分析树然后遍历它更简单有效。关于动作,你还将学习使用语义谓词更改语法分析器的行为去处理一些具有挑战性的识别问题。最后一章解决一些具有挑战性的语言识别问题,例如识别XML和Python中上下文相关的换行符。
  • 第四部分是参考章节,列出了所有关于使用ANTLR语法元语言和它的运行库的规则。

PBL文件格式解析

PBL文件是PowerBuilder库文件,在其中存储了应用程序所使用到的所有系统对象和用户自定义对象的集合,同时PBL文件中还存储了源代码控制信息(Source Code Control,简称SCC)。对其文件格式的研究,可以准确地了解程序结构并能对PBL文件中的对象进行修改,同时也有利于库文件的修复,程序动态执行等方面的工作。

PBL文件的存储结构

PBL文件存储信息时是以块(Block)为单位为对象分配存储空间的,每个块的大小固定为512字节,块号从0开始计算,块号与块首字节的偏移地址有如下关系:

1
块号 = 块首字节的偏移地址 / 512

整个PBL文件由Header块、Bitmap块、Node块、Data块组成。其中除Header块外,其它块均以链表结构组织,其中Data块是Node块中Entry表项的具体内容,是从属于Node块的。下图说明了这些块的关系。

图中Header块、首个Bitmap块及首个Node块在存储空间上是相邻的,其中Node块比较特别,占6个块共3072字节,其余块只占512字节,其空间大小及起始地址如下表所示:

块号 地址范围 描述
0 0000-01FF Header块
1 0200-03FF 首个Bitmap块
2-7 0400-0FFF 首个Node块

Header块解析

Header块是整个PBL的描述信息,它包含了PBL的版本标志,库注释,首个SCC数据块的偏移地址等信息。具体内容如下表所示:

块内地址范围 所占字节 数据类型 描述
0000-0003 4 char 'HDR*'
0004-0011 14 char 'PowerBuilder' + 0x00 + 0x00
0012-0015 4 char PBL格式版本(如0900表示9.0版本)
0016-0019 4 long 创建/修改日期时间
001A-001B 2 byte 保留
001C-011B 256 char 库注释
011C-011F 4 long 首个SCC数据块的偏移地址
0120-0123 4 long SCC数据块实际大小
0124-01FF 220 byte 保留

Bitmap块解析

Bitmap块中存放的是表示PBL文件存储空间的使用情况。该块数据结构如下表所示:

块内地址范围 所占字节 数据类型 描述
0000-0003 4 char 'FRE*'
0004-0007 4 long 下一个Bitmap块的偏移地址或0
0008-01FF 504 bit 位图(每个位标识一个块)

由上表可知,包含一个Bitmap块的PBL文件最多可使用504 * 8 = 4032个块。当文件空间超过4032个块时,就需要使用第二个Bitmap块,它的偏移地址由当前Bitmap块块内偏移0004-0007处的值表示。如果是最后一个Bitmap块,则对应的字节处为00 00 00 00,即偏移地址为0。这样就形成了Bitmap块的单向链表。

位图用于标识块的使用/空闲情况。在位图中为1的位,表示与该位序号对应的块已被使用;反之,表示对应块未使用。例如FF FF 40 00还原为位图则为11111111 11111111 01000000 00000000,该位图表示PBL文件共有18个块,其中的第16号块空闲未使用。

注意:在实际分析多个PBL文件后发现,位图中的位并不能真实反映对应块的空闲/使用情况,只是记录PBL文件使用了多少个块。

Node块解析

Node块是目录块,主要用于存放Entry目录表项。下表是Node块的数据结构:

块内地址范围 所占字节 数据类型 描述
0000-0003 4 char 'NOD*'
0004-0007 4 long 左Node块的偏移地址或0
0008-001B 4 long 父Node块的偏移地址或0
000C-000F 4 long 右Node块的偏移地址或0
0010-0011 2 short 块内可用空间(初始值3040)
0012-0013 2 short 按字母顺序最后一个对象名的位置
0014-0015 2 short 该Node块中的Entry表项数
0016-0017 2 short 按字母顺序第一个对象名的位置
0018-001F 8 char 保留
0020-00BF 3040 chunks Entry目录表

其中Entry目录表是顺序表。当一个Node块的空间不足以存储所有Entry表项时,可以再使用一个Node块来存储,并且Entry表项不能跨Node块存储,因此Node块中的空间不能完全利用,会有一定的剩余,这个值记录在块内偏移0010-0011处。

Node块的链接方式有些复杂,它使用一种称之为三叉链表(节点包含四个域:数据域、左指针域、右指针域、父指针域)的链式存储结构把所有Node块组织成为一颗二叉树,这可能是PowerBuilder为了提高查找速度而做的一些优化吧。

Entry表项解析

每个Entry表项对应于一个对象的源代码或PCODE的描述信息,因此Entry目录表就是整个库中各个对象的索引表,存储了各对象的索引信息。例如,在编程中创建一个名为“pbltest”的Window对象类型,那么在Entry目录表中要存放该对象的两个索引表项,分别为“pbltest.srw”用于存储源代码,“pbltest.win”用于存储PCODE。在Entry目录表中存储的对象有以下这些:

对象类型 源代码后缀 PCODE后辍
Application sra apl
Window srw win
DataWindow srd dwo
Menu srm men
Function srf fun
Query srq -
Structure srs str
User object sru udo
Pipeline srp -
Project srj -
? - pra
? - prp

Entry表项的具体数据结构如下表所示:

块内地址范围 所占字节 数据类型 描述
0000-0003 4 char 'ENT*'
0004-0007 4 char PBL格式版本(如0900表示9.0版本)
0008-000B 4 long 首个Data块的偏移地址
000C-000F 4 long 对象的实际大小
0010-0013 4 long 对象的创建/修改日期时间
0014-0015 2 short 对象的注释长度
0016-0017 2 short 对象名的长度
0018-???? ? char 对象名 + 0x00

这里需要说明的是,每个Entry表项的长度并不是固定的,它随着对象名的长度变化而变化,所以要读取下一个Entry表项,只能通过计算上一个Entry表项的长度即24 + 对象名长度来得 到,或者通过搜索下一个ENT*得到。

Data块解析

在Entry目录表中的各对象的实际数据内容是存储在Data块中的。Data块的数据结构如下表所示:

块内地址范围 所占字节 数据类型 描述
0000-0003 4 char 'DAT*'
0004-0007 4 char 下一个Data块的偏移地址或0
0008-0009 2 short 本块内存储的数据的实际长度
0010-01FF 502 char 对象的实际数据

由上表可知,若对象的数据内容在502字节以上时,就需用多个Data块存放,这些Data块形成一个单向链表。链表的最后一个Data块的0004-0007中存储的偏移地址为00 00 00 00,表示链表结束。0010-01FF处存放的是对象的实际数据,只有最后一个Data块的长度有可能小于502,且以0x00字节表示结束。

根据上面对PBL文件格式的解析,使用Ruby开发了一个小工具,用来输出PBL文件中存储的各种信息。源代码被放在GitHub上面,供大家参考。

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

带权随机函数

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

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

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

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

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

算法描述

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

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”图标。

重新按菜单键打开应用,然后……然后果然在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

一开始就编写优质的OO代码

英文原文:https://weblogs.java.net/blog/2008/10/03/writing-great-oo-code-day-one

没有获取经验的捷径。编写良好的面向对象代码需要经验。尽管如此,这里有三个实践可以帮助你一开始就有个良好的开端:

  1. 使用测试驱动开发(TDD)编写你所有的代码
  2. 遵循简单的规则
  3. 命令代替询问(Tell Don't Ask)

使用TDD编写你所有的代码

测试先行编写的代码和测试后行编写的代码是非常非常不同的代码。测试先行编写的代码是松耦合和高内聚的。测试后行编写的代码往往会破坏封装,当一些属性或私有方法需要被暴露给测试的时候,因为这些类没有被设计成要被测试的。如果你编写的代码测试先行,代码的依赖性会更好,你的代码将是松耦合和高内聚的。稍后详细讨论测试如何帮助你设计更好的代码。

遵循简单的规则

代码是简洁的,当它:

  1. 通过所有的测试
  2. 不包含重复代码
  3. 表达了所有的意图
  4. 使用了最少的类和方法

重要的是注意到我使用了一个有序列表。顺序很重要。带有单一main()方法的单一GodClass并不简单。它可以通过所有的测试,但在比“Hello, world!”更复杂的任何程序里它一定会包含重复代码和没有表达所有的意图。

我与简单的规则的斗争重点围绕在If Bug 。我不明白遵循简单的规则如何阻止某人编写大量的if代码。有人会说,我试过了,大量的if代码不会表达意图。但是,当你读到这样的代码

1
2
3
if (mobile.getType() == MobileTypes.STANDARD) {
    alert();
}

它实在是太容易看出意图了。无论该代码是在哪个方法的上下文中,如果mobile是STANDARD类型,那么警报。你还需要多少意图?

然后我灵光小闪。如果有那样的代码,那么在代码的其它地方肯定还有更多。可能是这样的代码:

1
2
3
if (mobile.getType() == MobileTypes.GAS) {
    registerGasReading();
}

1
2
3
if (mobile.getType() == MobileTypes.TEXT) {
    sendTextMessage();
}

1
2
3
if (mobile.getType() == MobileTypes.LOCATION) {
    notifyLocation();
}

你看见了吗?我当然知道。违反规则2。许多许多违反规则2。并且是违反规则2的最糟糕的那种。重复代码在许多不同的代码片段中。重复代码将非常非常难被找到。所以为了帮助防止这个,我列出来了。

命令代替询问

命令代替询问意味着不要询问一个对象的状态然后做些什么。应该命令那个对象去做些什么。这意味着所有这些if例子变成了:

1
mobile.alert();

1
mobile.registerGasReading();

1
mobile.sendTextMessage();

1
mobile.notifyLocation();

现在假设有一些if子句散落在有重复实现的整个代码中。在那个大量if代码的版本中,它们将非常难被找到,但在命令代替询问版本中,所有的实现都在Mobile类中。所有的都在一个地方寻找和消除。

聆听你的测试也将帮助你保持代码简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public interface Alarm {
    void alert(Mobile mobile);
}

public class Siren implements Alarm {
    public void alert(Mobile mobile) {
    if (mobile.getType == MobileTypes.STANDARD) {
        soundSiren();
    }
  }
}

public class SirenTest extends TestCase {
    public void testAlert() {
        LocationMobile mobile = new LocationMobile();
        Siren siren = new Siren();
        siren.alert(mobile);
        assert(sirenSounded());
    }
}

如果你仔细聆听你的测试,它会问你,“你为什么需要LocationMobile去测试Siren?”是呀,为什么呢?似乎Siren甚至不应该知道LocationMobile。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LocationMobile {
    private Alarm alarm;
    public LocationMobile(Alarm alarm) {
        this.alarm = alarm;
    }
    public void alert() {
        alarm.alert();    // alert on Alarm no longer needs a mobile
    }
}

public class LocationMobileTest extends TestCase {
    public void testAlert() {
        Alarm alarm = EasyMock.createMock(Alarm.class);
        alarm.alert();
        EasyMock.replay(alarm);
        Mobile mobile = new LocationMobile(alarm);
        mobile.alert();
        EasyMock.verify(alarm);
    }
}

看上去我仅仅互换了依赖。作为Alarm依赖Mobile的替换,现在有了Mobile依赖Alarm。如果你仔细看第一个测试,真正的依赖是Siren知道LocationMobile。一个具体类依赖于另一个具体类。这违反了依赖倒置原则 (DIP)。第二个例子是LocationMobile依赖接口Alarm。一个具体类依赖一个抽象。这满足了DIP。

如果你使用TDD编写你所有的代码,遵循简单的规则,以及命令代替询问,那么你会在那条成为一个更好的OO程序员的路上。良好的OO代码容易阅读和维护,但是可能难于编写。至少开始是这样。你写得越多,你将会变得更好,你将得到的经验也越多。与此同时,这些实践会让你在你的路上走得更好。

Ruby调试工具概览

调试Ruby代码最简单的方式就是使用puts或p方法。当有很多变量需要查看时,到处添加puts或p方法就可能变的不那么实际。幸好,Ruby社区提供了许多强大的调试工具。

Ruby 1.8+时代

调试Ruby代码使用ruby-debug。调试Rails代码则是pry-nav。不过在Ruby 1.9出来后ruby-debug就有问题了,于是就有了ruby-debug19,一个针对Ruby 1.9的ruby-debug移植版本。

Ruby 1.9.2+时代

等到Ruby 1.9.2发布,ruby-debug彻底歇菜,然后debugger就出现了。pry-nav也不好使了,还好有pry-debugger

Ruby 2+时代

新的Ruby调试工具byebug来了。虽然byebug也能调试Rails应用,但它不提供语法高亮,所以使用pry-byebug是个更好的选择。

Ruby 1.8+ Ruby 1.9 Ruby 1.9.2+ Ruby 2+
Ruby ruby-debug ruby-debug19 debugger byebug
Rails pry-nav pry-nav pry-debugger pry-byebug

其它

Pry其实不是纯粹的调试工具,它只是IRB的替代品,所以缺乏必要的调试指令。pry-nav、pry-debugger和pry-byebug做的只是分别把ruby-debug、debugger和byebug中的step、next、continue等指令添加到Pry中。

  • pry-nav = Pry + ruby-debug
  • pry-debugger = Pry + debugger
  • pry-byebug = Pry + byebug

如果要调试view怎么办?可以使用Web Console。在view里面加上<%= console %>,当view出现异常时,就会在异常界面下方,出现一个网页版的IRB,方便调试。Web Console默认只接受localhost的请求,假如需要让别的IP也能访问的话,可以这样做:

1
2
3
class Application < Rails::Application
  config.web_console.whitelisted_ips = '192.168.0.100'
end