xiaoR's Blog

Java与模式之重逢

在很久以前,人们对世界的抽象还停留在比较原始的阶段。还流行过一句话，程序＝数据结构＋算法。随着时间的推移，人们认识到数据和行为的统一性,用类来封装数据，隐藏数据,并且对行为建模。这种更高级的ADT应该是OO的最基本形态.用类继承的方式来渐进式地描述现实生活中的概念.对概念之间的差别用子类覆盖父类某一个方法的途径来表达.这就是所谓的面相对象三大特征"封装，继承，多态".当这个概念被提出时,人们就像回到初恋(自行脑补食神中的沙滩场景),世界一下子就明亮了起来。然而现实还是很骨感的,多重继承深深的打击了人们(初恋往往都是苦涩的)。于是乎站在神坛的4人帮就站出来说:你们这般low X,你们必选要按照一定的“模式”来和异性相处才能更好的向往未来。作为工业界的新生Java君当然会响应这个号召,而去更近一步明确确认了subType(Interface)和subClass之间的职责。这也是为啥模式起于C＋＋却在Java这发扬广发(自己脑补的,带主观排定).那时候你可能会有

继续阅读

走进OCaml的世界之环境搭建

1.What is OCaml

当你看到这的时候话多话少都对OCaml有一定的了解,更详尽的内容在这里.用一句OCamler的话就是

let ocaml 'a =
           powerful and beautiful

2.为什么要学习OCaml

Why not!!!!

OCaml拥有如此之多powerful的特性：

Camlp4(一个类似Lisp的宏(神一般的存在)),官方Wiki介绍

very fast

多范氏：A functional programming language descendent of ML,imperative, and object-oriented

A powerful type system(得益于ML的体系)

强大的编译系统：包含交互式顶层解释器(interactive toplevel interpreter)，字节码编译器(bytecode compiler)，

以及最优本地代码编译器(optimizing native code compiler)。

编译后的本地代码性能甚至超过C/C++(可以通过C++ OCaml Performance作为关键词搜索),参考地址

--注:这里并不是说OCaml的性能就超过C/C++,只想突出其编译器的强大。

--引用Mark在测试的一段说明:

The results were extremely surprising to me,
and I did spend some time profiling to try to figure out just why the OCaml was so much faster.
The specific reason was that the Caml code did some really clever stuff - it basically did something like local constant propagation that
were based on be able to identify relations between subscripts used to access different arrays, and having done that,
it could do some dramatic code rewriting that made it possible to merge loops, and hoist some local constants out of the restructured merged loop

巨大并强悍的标准库

跨平台

....................

3.安装

说了这么多,现在就开始安装吧

目前OCaml最新的版本是4.00.1,与2012-10-05发布.可以在这里找到相应的下载,按照自己的操作系统下载相应的发行包。这里采用编译源代码来安装，安装的平台是Ubuntu。

*下载并解压源代码

wget http://caml.inria.fr/pub/distrib/ocaml-4.00/ocaml-4.00.1.tar.gz
tar zxf ocaml-4.00.1.tar.gz
cd ocaml-4.00.1

*根据根目录下的INSTALL文件,确保使用中MAKE和C编译器,在Ubuntu上都带有.OK在根目录下执行

./configure

默认会安装在/usr/local下，其他的一些配置选项会根据系统自动进行检测,如果想要图形方面的支持确保提供X11的库文.可以通过

apt-get install libx11-dev

进行安装

配置完成如果看见** OCaml configuration completed successfully **说明配置成功，输出的最后OCaml会根据当前的系统列举出配置的摘要，大概如下(因系统环境而异)

** Configuration summary **

Directories where OCaml will be installed:
binaries.................. /usr/local/bin
standard library.......... /usr/local/lib/ocaml
manual pages.............. /usr/local/man (with extension .1)
Configuration for the bytecode compiler:
C compiler used........... gcc
options for compiling..... -fno-defer-pop -Wall -D_FILE_OFFSET_BITS=64 -D_REENTRANT
options for linking....... -Wl,-E -lm -ldl -ltermcap -lpthread
shared libraries are supported
options for compiling..... -fPIC -fno-defer-pop -Wall -D_FILE_OFFSET_BITS=64 -D_REENTRANT
command for building...... gcc -shared -o lib.so -Wl,-rpath,/a/path objs
Configuration for the native-code compiler:
hardware architecture..... amd64
OS variant................ linux
C compiler used........... gcc
options for compiling..... -Wall -D_FILE_OFFSET_BITS=64 -D_REENTRANT
options for linking....... -lm
assembler ................ as
preprocessed assembler ... gcc -c
assembler supports CFI ... yes
native dynlink ........... true
profiling with gprof ..... supported
Source-level replay debugger: supported
Additional libraries supported:
unix str num dynlink bigarray systhreads threads graph
Configuration for the "num" library:
target architecture ...... amd64 (asm level 1)
Configuration for the "graph" library:
options for compiling ....
options for linking ...... -lX11
The "labltk" library: not supported

*Standard OCaml Develop Tools

ocaml	topleveltop
ocamlrun	bytecode interpreter
ocamlc	bytecode batch compiler
ocamlopt	navite code batch compiler
ocamlc.opt	optimized bytecode batch compiler
ocamlopt	optimized navite code batch compiler
ocamlmktop	new toplevel constructor

按照INSTALL文件的说明

make world    #bytecode compiler
make opt     #optimizing native code compiler
make opt.opt #一个更快版本的编译器(尤其对于大文件的编译,编译速度回加快),其中ocamlc.opt取代ocamlc(bytecode),ocamlopt.opt取代ocamlopt(native-code)
make world.opt #一个更便捷的命令式,包含上述的所有编译器包含了上诉的编译器.

执行

make world.opt

等,编译完成没有提示错误,执行

make install

到此OCaml就安装完成了。

4.HelloWorld

写个HelloWorld测试下OCaml具有REPL的交互环境叫做Toplevel(貌似都成了函数式语言的标配)输入ocaml,你将会看见如下输出

$# ocaml
        OCaml version 4.00.1
#

输入语句：Printf.printf "%s%s\n" "Hello" "World" ;;

解析器会给出这个语句的反馈: HelloWorld- : unit = ()

全部的内容如下

$ ocaml
        OCaml version 4.00.1
# Printf.printf "%s%s\n" "Hello" "World" ;;
HelloWorld
- : unit = ()
#

这里注意的整个表达式没有()也没有,这和传统的C类语言很大的不同,在OCaml中 f g 3 和f (g 3)是截然不同的两个表达式.其中f g 3表示f是一个函数并且接受两个参数,后者f (g 3)表示f是一个函数只接受一个参数(g 3)的结果会作为f的参数使用

在g 3中3作为g函数的一个参数

刚开始有点不习惯(和Lisp中的S表达式一样),但是习惯之后会发现这是具有很强的表达的能力很接近自然语言

OCaml每个表达式都是用;;作为输入的结束

OCaml是静态强类型语言,如果使用一个整数和一个浮点数相加它并不会帮你做隐式的类型转换这和大多数的静态类型语言不同(如java,c++等)

如：1+1.0;;

报错: 1+1.0;;

^^^

Error: This expression has type float but an expression was expected of type int

所以只能通过显示(手工的进行转换) i+ int_of_float 1.0;;

关于OCaml的语法细节下次在详细说明

OCaml默认的Toplevel不具有历史记录的功能,可以通过安装ledit来补充这一点

apt-get install ledit

然后使用toplevel的时候使用

ledit ocaml

退出toplevel可以使用

#quit;; #这样这一有一个#
exit 1;;
#两个命令使用其中一个就可以

5.简单测试

都说OCaml的速度很快,光说无凭,写个程序来和C较量下.测试的内容是斐波那契数列,计算器第40位是多少。先来看看其数学上的定义

第一场：递归对比(统一采用系统自带的time做统计)

首先是C,采用G++编译器，－ｏ做为参数编译的结果为cf。代码如下

#include <stdio.h>

int fib(int n) {
    if(n==0){
      return 0;	
    }
    if(n==1){
         return 1;
    }
    return fib(n-1)+fib(n-2);
}

int main(){
    int n=40;
    printf("%d\n",fib(n));
    return 0;
}

输出如下：

$ time ./cf
102334155

real	0m1.067s
user	0m1.064s
sys	0m0.004s

接着是OCaml,采用ocamlopt编译,-o做为参数，编译的结果是of代码如下

let rec  fib n = match n with
     0->0
    |1 -> 1
    |n-> fib(n-1)+fib(n-2);;

let _ =
    Printf.printf "%d\n" (fib 40);;
exit 1;

输出如下

$ time ./of
102334155

real	0m0.609s
user	0m0.608s
sys	0m0.000s

这一场测试OCaml胜出，而且速度差不度是C的两倍。这时候可能C的人不愿意说：递归不是C的强项,我们可以通过优化算法来提示速度.(这里计算的数值不是很大,直接采用循环进入第二轮).

第二场:循环对比

首先是C,采用G++编译器，－ｏ做为参数编译的结果为cf2。代码如下

#include <stdio.h>
int main(){
     int fib[41] = {0,1};
     int i=0;
     for(i=2;i<41;i++)fib[i] = fib[i-1]+fib[i-2];
     printf("%d\n", fib[40]);
     return 0;
}

输出如下

$ time ./cf2
102334155

real	0m0.019s
user	0m0.000s
sys	0m0.000s

我艹,C的速度真不是盖的,速度直接完爆了递归的版本。

接着是OCaml(采用ocamlopt编译,-o做为参数，编译的结果是of2)，OCaml表示压力不大，你改算法，我也改而且还是用递归,代码如下:

let fib_help f= match f with
      [|a;b|]->[|b;a+b|]
     |_->raise(Invalid_argument "f must be a int array");;

let rec fib n = match n with
        1->[|0;1|]
       |n->fib_help( fib(n-1) );;

let _=
     Printf.printf "%d\n" (fib 40).(1);
exit 0

输出如下：

time ./of2
102334155

real	0m0.002s
user	0m0.000s
sys	0m0.000s

这次两者的差距相差没有第一场那么明显,OCaml有时候越快，有时候是C越快,只能算平手。

6.写在最后

测试的结果并不全面速度上也不是绝对的,但是由上面两个测试可以看出只要编译器做好优化，用单层递归写的程序与用单层循环写的程序效率相差不是很大，但是从代码的理解上来说递归更能体现其数学的含义更具有可读性。而且在数值的计算上考验更多的是编译器层面上的优化，推荐阅读下老赵的这篇文章.

在不损失代码的阅读性和性能的情况下代码的效率还能做到和C相当不得不说OCaml确实是一门非常的强大的语言，这也许国外好多金融公司都采用OCaml来作为开发语言。现在就有一门如此强大的语言在你面前，亲，你心动了吗？