帖子

目前显示的是 三月, 2014的博文

绘制二叉树

图片
最近我在学习二叉树相关的很多算法,于是我就在想,能不能把二叉树画出来看看。比如下图这样:问题的细化我们想要在一个平面的画布上绘图,比如一个800像素x600像素的bitmap。首先把这个画布切成一个个正方形的格子(tile)。每个格子的大小比如是20x20。每个格子里面只放一个二叉树节点。我们需要寻找一个算法,给二叉树的每个节点计算出一个(x,y)的值,来对应我们画好的格子。一旦把(x,y)的值确定下来,剩下就是画圆圈、画线的工作了,就简单多了。那么依据什么规则来确定x,y的值呢?Trees impose a distance on the nodes; no node should be closer to the root than any of its ancestors.Nodes at the same level of the tree should lie along a straight line, and the straight lines corresponding to the levels should be parallel.The relative order of nodes on any level should be the same as in the level order traversal of the tree.For a binary tree, a left child should be positioned to the left of its parent and a right child to the right.A parent should be centred over its children.A subtree of a given tree should be drawn the same way regardless of where it occurs in the tree.根据上面的第二条规则,y的值其实很容易获得,它就对应节点的level值。所以对二叉树进行层序遍历即可。所以问题的核心是给每个二叉树节点计算横坐标x的值!一个最直接的做法是,直接以中序遍历的序号作为横坐标的值。用这样的算法,画前序遍历为{2,1,6,4,3,5,8,7}的二叉搜索树,结果为:用这样的算法,画前序遍历为{…

一些技术视频资源

最近在国外一些网站上找到了一些很有趣的视频资源。一. USENIX的会议视频。USENIX原名Unix Users Group,在它的网站上能下载到从2008年到现在的所有会议视频 https://www.usenix.org/conferences/multimedia ,一般是480p的 。由于我个人比较喜欢读usenix的paper,它比较偏工业界。所以我很喜欢看他们的演讲。二. Google Developers At Youtube有每年Google各种技术会议的视频。比如Google I/O,Dev Summit等。很多都是720p的高清。三. MIT算法系列入门:6.046和6.006。进阶:6.854/18.415J: Advanced Algorithms (Fall 2013)。这个课2013年的视频在youtube上"Karger Skoltech"的Channel里。https://www.youtube.com/watch?v=QnPl_Y6EqMo&list=PL2B4EEwhKD-NbwZ4ezj7gyc_3yNrojKM9 可惜清晰度很低。高级:6.851: Advanced Data Structures 。 这个课的视频有720p高清版,但是内容确实非常难。他讲的东西是我在任何书上都学不到的,所以耐心听吧。

在windows下使用llvm+clang

图片
clangFreeBSD和Mac下C/C++语言的默认编译器。如果你在苹果下做过开发,那么应该对它很熟悉。
这套工具链有很多优点:
代码很新,架构优良。 错误信息更友好。 静态检查功能更强大。 版权限制小,易于自定义模块来扩展它的功能。 背后有Apple和Google这两家商业公司的大力支持。比如XCode现在只支持clang而不支持gcc。 支持JIT。这使得C/C++可以像java那样半编译半解释,一次编译到处执行。 支持所有主流的操作系统。 clang只是一个前端,它背后用来生成二进制机器码的叫llvm。
llvm+clang 在windows下有两种,一个是用mingw编译的,使用gcc的头文件和库。一个是用vc编译的,使用vc的头文件和库。
mingw版本的下载地址是:http://llvm.org/releases/3.6.1/LLVM-3.6.1-win32.exe 这是由官方提供的
vc版本的下载地址是:
google drive下载
这是我自己编译的,32位版本。 想自己编译clang的可参考我之前的文章.
我建议你安装vc版本的。
因为优点是:
它编译出来的是更原生态的程序。不依赖于mingw,只依赖于vc的dll。 我自己编译的这个版本功能更全,包含了llvm的JIT执行器、clang的扩展工具(如把老风格的代码转换成c++11)等等。 性能更高。 但也有一些缺点:
必须依赖于visual studio。请先安装visual studio再安装llvm。 没有安装visual studio的可以从微软的官方网站下载: http://www.microsoft.com/en-us/download/details.aspx?id=40778 。
如果已经有visual studio但是版本不是2013的,请安装vc 2013的可再分发包:http://www.microsoft.com/en-us/download/details.aspx?id=40784
clang安装好以后,你可以先打开它下面的bin目录看一眼,里面有30多个exe。主要比较常用的是:
clang: C语言编译器,类似于gccclang++: C++编译器,类似于g++。clang++只是clang的一个别名。lld: 链接器,类似于ld。但是默认不用它,默认用…

在windows下用vc编译llvm+clang

图片
1. 安装cmake(www.cmake.org)和python、perl 2. 安装visual studio 3. 下载源代码aria2c -x 5 -j 5 -k 1M http://releases.llvm.org/4.0.1/llvm-4.0.1.src.tar.xz
aria2c -x 5 -j 5 -k 1M http://releases.llvm.org/4.0.1/cfe-4.0.1.src.tar.xz
aria2c -x 5 -j 5 -k 1M http://releases.llvm.org/4.0.1/compiler-rt-4.0.1.src.tar.xz
aria2c -x 5 -j 5 -k 1M http://releases.llvm.org/4.0.1/lldb-4.0.1.src.tar.xz
aria2c -x 5 -j 5 -k 1M http://releases.llvm.org/4.0.1/lld-4.0.1.src.tar.xz
aria2c -x 5 -j 5 -k 1M http://releases.llvm.org/4.0.1/clang-tools-extra-4.0.1.src.tar.xz
aria2c -x 5 -j 5 -k 1M http://releases.llvm.org/4.0.1/polly-4.0.1.src.tar.xz
aria2c -x 5 -j 5 -k 1M http://releases.llvm.org/4.0.1/openmp-4.0.1.src.tar.xz

全部解压之后,按照下面的规则放置

mv cfe-4.0.1.src llvm-4.0.1.src/tools/clang
mv compiler-rt-4.0.1.src llvm-4.0.1.src/projects/compiler-rt
mv clang-tools-extra-4.0.1.src llvm-4.0.1.src/tools/clang/tools/extra
mv lldb-4.0.1.src llvm-4.0.1.src/tools/lldb
mv openmp-4.0.1.src llvm-4.0.1.src/projects/openmp
mv lld-4.0.1.src llvm-4.0.1.sr…

在tomcat应用中获得原始IP

Apache/Nginx 通常被放在tomcat前作为http代理。例如:browser -> apache -> tomcat 但是缺点是丢失了很多原有的网络信息:ip、hostname、protocol(用的是http还是 https)比如,当java程序想生成http重定向请求的时候会遇到麻烦。因为HTTP头部的Location字段的值必须是绝对URL。重定向的问题勉强可以交给前面的proxy来解决(让apache重写header),但是藏在http body中的各种链接问题就棘手多了。比如当从一个html页面载入一个外部资源时,资源的链接到底是写http的还是https的呢?通过修改apache和tomcat的配置,可以让这个问题得到较为完美的解决。首先是要apache把这些丢失的信息通过http header发到后面去。一. Host字段HTTP头部的Host字段用来写网站的域名。如果服务器(此处指tomcat)需要支持virtual host,即同一个IP服务多个域名,那么这个字段很重要。在配置mod_proxy时加上ProxyPreserveHost,就会让apache往后端转发的时候,Host字段依然填它从browser收到的那个域名。二. Apache默认会发送的字段默认情况下apache在做http逆向代理时会给后端发送以下字段X-Forwarded-For client的IP地址X-Forwarded-Host client所请求的域名,即client发来的的http header中Host字段的值。X-Forwarded-Server 这台代理服务器(apache)的域名。三. 需要添加的纵使有了以上信息,我们还是不知道client用的到底是http还是https访问的apache。所以要加下面这行:RequestHeader set X-Forwarded-Proto "https" env=HTTPS这行代码的意思是,如果当前含有"HTTPS"这个环境变量,那么往后端转发请求时,在头部加上X-Forwarded-Proto字段,值为"https"。类似的还可添加其它信息。如HTTPS/SPDY的具体信息,假如前端用的是spdy,那么当前请求不仅具有HTTPS这个环境…

AWS又“试用”了一年

这两天把我个人网站的服务器挪了一下。原因是amazon web service一年的免费试用马上就要到期了,所以我就又申请了一个新账号,继续试用。哈哈。不用换信用卡,换一个新的email就行了。这次重做系统的时候,我考虑再三,最终选用了32位的Linux。因为amazon ec2免费的实例只有600MB内存,而对于大多数程序来说,64位的要比32位的占用更多内存。(因为指针变大了)然后我开通了RDS服务,就不自己建mysql server了,确实省事不少。先用着再说吧。顺便,AWS China的小哥打电话告诉我,最多2-3个月内,中国区就要正式商用了。然后我又看了下Google App Engine,这个比较讨厌的是和Google Apps捆绑销售了。要在Google App Engine上绑定域名,必须先把域名绑到Google Apps上去。而Google Apps已经没有免费版。