用 Q 求解回文数等
有人用 J 语言来解决欧拉问题 36，我用 Q 语言的解法为：
q)0 {x+y*(all yy=reverse yy:string y)&all b=reverse b:(-32+b?1b)#b:0b vs y}/ til 1000000
或者
q)sum where {all (x=reverse x:string x),b=reverse b:(-32+b?1b)#b:0b vs x} each til 1000000简要说明一下：
是否是十进制的回文数：{all x=reverse x:string x}
是否是二进制的回文数：{all b=reverse b:(-32+b?1b)#b:0b vs x}
产生一百万以下的数组：til 1000000
如果用 K 语言来写，肯定跟 J 语言一样短而晦涩。Q 语言的可读性还是强不少的。
他还做了第35题，用 Q 语言实现如下：
q) repu:{raze $[1<n:count x;x {x[y] ,/: repu x _y }/: til n;x]} /全排列
q) primes:00b,999998#1b / 初始化质数标志位
q) {$[primes[x];primes[x*2_til floor 1000000%x]:0b;0b]} each 2+til 499999 / 标记非质数
q) sum where {all `boolean$ primes "I"$repu string x} each til 1000000 /
Q 还是相当精炼的语言，唯一的不足是不知道怎么实现惰性求值，或者协程(concurrence)，有的话可以进一步提高效率。
davies 发表于 2008 年 06 月 10 日 | 0 条留言
云图的颜色映射算法Jet
在绘制云图等时，需要用颜色来表征一维数值的大小，如果用灰度表示，那映射非常简单，可以是线性映射。如果用彩色来表示，则需要一个从一维数值到三维RGB颜色空间的映射，希望该映射能够覆盖大部分颜色空间，并且在不同区间都能比较明显地反映数值变化。
Matlab中绘制云图时，默认采用的是jet映射算法，随着数值的增大，颜色从蓝到红，即由冷色到暖色。它是让三原色RGB分别由小到大，保持一段之后再由大表小，并且将三原色的这种变化错开，否则就成了灰度了。
在Matlab中该算法描述实现：
function J = jet(m) %JET Variant of HSV. % JET(M), a variant of HSV(M), is an M-by-3 matrix containing % the default colormap used by CONTOUR, SURF and PCOLOR. % The colors begin with dark blue, range through shades of % blue, cyan, green, yellow and red, and end with dark red. % JET, with no arguments, is the same length as the current colormap. % Use COLORMAP(JET). % % See also HSV, HOT, PINK, FLAG, COLORMAP, RGBPLOT. % Copyright 1984-2002 The MathWorks, Inc. % $Revision: 5.7 $ $Date: 2002/04/01 21:01:50 $ if nargin < 1 m = size(get(gcf,'colormap'),1); end n = ceil(m/4); u = [(1:1:n)/n ones(1,n-1) (n:-1:1)/n]'; g = ceil(n/2) - (mod(m,4)==1) + (1:length(u))'; r = g + n; b = g - n; g(g>m) = []; r(r>m) = []; b(b<1) = []; J = zeros(m,3); J(r,1) = u(1:length(r)); J(g,2) = u(1:length(g)); J(b,3) = u(end-length(b)+1:end)
对应的C++实现为：
该代码可以在我的代码仓库中下载。
davies 发表于 2007 年 08 月 18 日 | 1 条留言
D语言的现状与前途
D语言是被设计用来取代C/C++进行系统级开发的语言，由著名的C/C++编译器大牛Walter Bright设计和实现。D语言借鉴了C、C++、Java和C#等静态类型语言以及LISP、Python和Ruby等动态类型语言的优点，具有一系列非常吸引人的特性：它具有C/C++语言的进行底层开发的能力(能够直接嵌入汇编)，又具有大量Java和C#的开发特性(比如自动垃圾回收，delegate等)，还可以进行函数式编程，同时在语言级别支持一些数据结构(比如哈希字典，复数和元组等)，软件工程方面的契约编程和单元测试等也引入其中。
这种种特性让D语言看起来非常吸引人，仿佛看到了系统开发的救世主，很多厌烦了C++和Java等的程序员投入到它的社区中，创立了很多相关的项目，主要是把C/C++的库移植到D语言中来，也有人进行正式的项目开发。
D语言的是由Walter Bright一个人设计和实现的，它的编译器DMD只开放了前端部分的源代码，可能是因为后端部分是他认为最后技术含量的部分，毕竟是从十几年的C/C++编辑器开发中积累起来的。D语言规范和DMD实现是典型的个人项目，一条单一的开发主线，版本好不停往上涨，变化频繁。他在2007年年初的时候发布了1.0版，本以为会是一个里程碑似的版本，给D语言的发展注入新的活力。可在1.0发布之后又在快速更新，现在已经更新到1.013版，从更新日志来看，语言本身的变化依然非常频繁，甚至关键字和操作符的变化都很快。
由于D语言本身和DMD编译器的过于不稳定，让一些热心的D语言开发者很郁闷，为了解决某个Bug而跟新编译器后，却使得原本在1.0下能够编译通过的代码在新版本的DMD下不能编译。3月11日，D语言的长期用户Chris Miller不得不再次在D语言的新闻组中发言要求DMD和D语言规范增加分支(DMD needs branches)，以获得一个相对稳定的D语言版本，引来大水滔天，几乎所有人都支持这个请求。可Walter这个老顽固却死活不开窍，坚持使用他传统的C/C++项目开发方式，以为只要每次发布前都保证通过所有测试用例可以保证版本的向前兼容，甚至使用了-v1参数来获得一个相对稳定的1.0版本支持，其事实上效果相当差，还会给代码维护带来很大问题。为了让他明白创建分支的好处，很多人跳出来动之以情晓之以理，而他总是抱着解决某几个Bug就能解决稳定性的思路来回答。无奈决定权掌握在他一个人手里，大伙只能干着急，甚至有人提出了要单立门户的想法，可是没有后端部分的源代码，同时还要受到版权的限制，只能放弃。
Walter Bright是编译器的高手，这一点毋庸置疑，可他单枪匹马想独自一人创立一个被广泛使用的语言，还是相当难的，尤其是现在这种半开放源码方式和一根筋的不合作作风，要想D语言盛行几乎不可能。回想一下当前一些非常成功的项目，比如Linux和Python等，虽然当初只是一个人的创意，后来的发展也主要由创始人来把握方向，但它们在已开始就是一种完全开放的姿态，很快的吸引到大量的志同道合之式来合作开发，形成庞大的社区，最后走向了成功。
D语言本是非常有前途的，C/C++和Java等的众多弊病注定了需要一个新的更好的语言来取代，可由于Walter Bright的个人因素会导致他终究只能是少部分人的玩具，难以大面积推广应用。另外，随着JIT(实时编译)等优化技术的发展，并非要将静态类型语言编译成本地可执行代码才能够获得足够高的执行效率，动态语言同样可以用来进行对性能要求较高的系统开发，就更没有D语言的生存空间了，将是Python等动态语言的天下，非常看好和期待PyPy的进一步发展。
davies 发表于 2007 年 04 月 23 日 | 6 条留言
dp.SyntaxHighlighter: 用JavaScript进行语法加亮
浏览 Python 大牛 limodou 的 blog 时，了解到了一个用JavaScript进行语法加亮的开源软件dp.SyntaxHighlighter，它自动对 HTML中用 textarea 的内容进行进行语法加亮，效果很棒，真是相见恨晚。
一年前我在开发 BlogXP 时就想要给blog做一个语法加亮的功能，当时只实现了Python的，而且用起来也不方便。当时想到的最好方案就是用JavaScript来做，服务器端存储的是源代码的原始文本，在客户端用JavaScript将其渲染出好看的样式。那会不太会用JS，也就没做，居然都没到网上去好好找找，否则早发现了。
用法相当简单，在页面魔板中加入dp.SyntaxHighlighter 的CSS和 JS链接，将裸代码放到blog中，并用textarea包围，设置一个名字比如code，设置class为相应的语言名称即可，它的网站上有很清晰的用法说明。还能方便地查看原始代码和打印。
目前官方支持的语言有：
- C#
- VB & VB.NET
- Delphi, Pascal
- Java, JavaScript
- PHP
- Python
- SQL
- XML, HTML, XSLT and any other XML style code
很奇怪居然没有C/C++，可能作者认为用C#的即可。我在Java的基础上改了改，只是加入两条正则表达式即可，很快就搞定了，它的扩展性的确非常棒。如果能像Vim那样支持各种各样的语法那就更爽了，哈哈
另外，官方的版本中默认用粗体显示Python的关键字，会导致出现竖直滚动条，我把粗体去掉了。还有一个问题是原始代码放在TEXTAREA中，如果在某些JavaScript不能运行的环境中会显示为一个框，默认还是能够修改的，可以通过设置 readonly 属性来稿定。
花了点时间把以前贴在 Blog 中的代码都改了一下，现在看起来漂亮太多了。
davies 发表于 2006 年 09 月 14 日 | 0 条留言
第二次 Code Jam 经历
Google Code Jam 2006 刚刚结束资格赛，我的第二次Code Jam经历也画上了句号。
这一次是全球范围的比赛，比上次Code Jam China 2005难不少，三道练习题就让人望而生畏。第一个是变形的网络流，系统学习过算法的人可能会比较熟悉，我也是在最近两个星期的学习之后才基本掌握的。郁闷的是前两天作了一份解答却通不过系统测试，还找不出错在哪:(。第二题是字符串处理，或许可以用效率不太高的搜索解决，但也不简单。第三题是动态规划，改进的汉内塔问题，做得基本顺利，却也是花了三个多小时完成。
两周前还特意从图书馆借来了MIT的算法导论第二版，E文的，巨厚重。扎进去看了一通，收获不少。好多算法虽然动了，却还不熟练，无法满足TopCoder竞赛这样的高强度要求。要在一个小时内完成三道题，必须是看完题后就能有明确的算法，实现过程中还不能出问题才行。
Revv是昨天早上去做的，相当不爽，第一题就花了40分钟，导致第二题没有时间完成。我是晚上在实验室做的，结果比Revv更惨，第一题花了40多分钟而且还没做完，赶紧看了第二题，用暴力法来解，也是在时间结束后才刚刚通过样例测试，显然已经出局了。
前天在Code Jam 上练习时出现意外，导致原来的ID没法打开题目了，于是又注册了一个ID，作为备用。昨晚在经历的惨烈的失败后，把这个备用ID也拿出来用了。第一题还比较顺利，用了大概13分钟。有趣的是第二题，居然和我刚才做过的那个第二题是一样的，直接拿来用，并再测试了一下，这时才发现刚才用的暴力解法并不能通过样例测试，求解N=16时超时了，此时的复杂度是16！。只能重头再来，在纸上演算了很多遍后，最后发现这个题还是可以用DP(动态规划)来减少计算次数的，赶紧实现之。在结束前5分钟总算完成了，提交。看了一下得分，两道题共500分左右，排名在1500左右，要想晋级，必须前面有一半人通不过系统测试，并且我都要pass。
系统测试的结果已经出来了，我刚才登陆进去发现Ranking已经变成了1531，黄色，想起昨天Revv还说我是Yellow来着。在TopCoder，黄色是属于中等的级别。资格赛只取前1000名晋级，我已经被淘汰了。去看了看测试结果，失败的果然是一大片，当然也包括我的第二题。居然是在最后一个测试项目上失败了，N=1的特殊情况。再去看了看题目，还是不明白为什么是那样的结果。
第二次Code Jam经历就这样结束了，我目前的水平也就这样了，同时也说明还有很大上升空间，呵呵。这阵子恶补了一下算法，收获还是挺大的。要再接再厉，再在TopCoder上奋战一段时间，提高自身的算法能力，也算是给以后找工作时的面试做准备，加油！
davies 发表于 2006 年 09 月 7 日 | 6 条留言
第 1 / 6 页 | 下一页