Monthly Archives: August 2012

写了个 web app

之前就想写个 web app 玩,但是由于可选的语言(Java,PHP,Python,Ruby,Scala 等等)、框架(Python 下就有 Django,Pylons,web2py,Flask 等)、数据库(主流还是 MySQL,但也有其它模型如 PostgreSQL 或 mongoDB)太多,于是一直没动手(The Dilemma of Choice 的典型表现)。然后决定与其分析完所有这些技术,还不如动手先写个简单的试试。于是从熟悉和喜好的角度选了 Python,从流行的角度选了 Django,从从众的角度选了 MySQL,Apache + mod_wsgi 作服务器,网页端 HTML 和 JavaScript 则是必备的。就写个最简单的,也就不考虑可测试性、可维护性和可扩展性的方面了。 需求是自发的,经常需要在 Linux,Windows,Mac 之间传些东西。文件的话一般用 Windows Share,有点麻烦,但用的机会也不多;文本(网址、程序片断、文献等)却是相当经常的。于是就写了个叫 web_clipboard 的 web app,一方把文本粘贴到网页上,另一方复制下来(当然网上有现成且强大的高端品,比如 pastebin,不过我需要的只是最简洁的)。用了 Django 的框架,加起来总共只用了百行左右的 Python,HTML template,JavaScript。实现的功能也极其简单,没有用户和登录,没有语法高亮,黑白灰3色界面,只显示最近10条文本,最简单的粘贴和复制功能(引入了 … Continue reading

Posted in Computer and Internet, Web | Tagged , | 2 Comments

variadic template of c++0x

用 c++0x 里的可变参数模板(variadic template)几乎可以模仿函数式语言的 list 了。看下面,用 variadic template 可以定义 fold left(foldl)如下(test.cpp 是使用实例): 不过由于没法 typedef 可变参数模板,做不到返回 list 形态的模板,因此 map 的定义还是困难的。 更多有趣的内容可以看 What Does Haskell Have to Do with C++? 这篇 blog。 完整的源代码放在 github 上了。 闲谈:现在 git 用的顺手了点,于是就开始用 github。git 的分布式开发的特性决定了它 branch 和 … Continue reading

Posted in Computer and Internet, Programming and Algorithm | Tagged , | 1 Comment

Linux 的 Socket 通信

Socket 不仅是网络通信工具,同时也是 *nix 系统下方便且通用的跨进程通信方式。 但是如果通信双方配合不当的话也会给系统造成负面效果。 在发送和接收端传输数据的时候,可以把双方的缓存合起来看作一个大的缓存。如果当接收端的处理速度跟不上发送端的发送速度的话,就会把双方的缓存用尽而造成发送端的阻塞。而如果发送端不幸又使用了阻塞的 Socket API 发送的话,就很容易引起其性能下降了。 根本的解决方案一是提高接收端处理速度,解决性能瓶颈;如果一做不到的话,二则是用非阻塞的方式发送数据。在二中,一是使用线程,二是使用异步IO,比如 libevent 库(资源方面,线程是线性扩展性的,而异步IO则可能达到次线性甚至常数的扩展性)。 对于简单的阻塞式的 Socket API,一个对应瞬时性的大容量的数据传输的方式是加大发送端的缓存(使用 setsockopt)。但需要注意的是 Linux 一般可以设置的缓存最大值往往不过数百kB,有时不够满足需求。如果需要更大的缓存则需要调整系统设置,可以参考 Boost socket performance on Linux。 需要注意的是,即使使用文件名作为地址的本地 Socket 通信(AF_UNIX,或 AF_LOCAL / AF_FILE),上面讨论的缓存和缓存设置同样起作用。

Posted in Computer and Internet, Operation System and Linux | Tagged , | Leave a comment

cJSON 链表的缺陷

cJSON 使用双向链表来表示 JSON 的 array 或 object,但在父节点中只保存链表的头指针。于是需要插入到链表尾端的操作,如 cJSON_AddItemToArray 和 cJSON_AddItemToObject 函数调用,所需的时间复杂度和 array 或 object 的当前长度成正比。其结果就是使用 cJSON 在一个 array 中插入 n 个元素的时间复杂度是 O(n2)。而如果对其做一个简单的修改,在 cJSON 的数据结构中加入链表的尾指针,就能得到常数的函数调用时间复杂度。这点实在是让我不得不认为是个设计缺陷。 起因是这样的,在一个嵌入式设备上,cJSON 生成 1MB 的 JSON 花了 10 秒。调查后发现的罪魁祸首就是 cJSON 里的这个链表。同时由于嵌入式设备 CPU 的 L1/L2 缓存普遍较小,cJSON 遍历链表时的 cache … Continue reading

Posted in Computer and Internet | Tagged | 1 Comment

JPL 的代码规范

好奇号上了火星。那让我们看看喷气推进实验室的代码规范 JPL Institutional Coding Standard。 规范强调的是可证明性。比如3和4要求所有循环都有循环上限,并且不允许递归,这是为了静态分析工具能够验证程序的运行时间和空间的上界;而5禁止使用动态分配内存,一是为了避免内存分配时的不确定性,二是为了能够验证程序运行空间的上界。 当然,上面几条规范主要是为了安全关键的软件,常规的软件开发不需要做到这个地步。但是可证明性的思想是非常有意义的。 后面的规范就平易近人多了,模块间只用IPC通信,共享数据的单一所有者,线程安全,尽可能避免锁和嵌套锁;尽可能小的作用域,检查所有输入参数和返回值,必须使用断言;等。 看不了这么多也可以看作为精简版的 The Power of Ten — Rules for Developing Safety Critical Code。 好奇号用的是 400MIPS 的 RAD750 抗辐射处理器,256kB EEPROM,256MB DRAM,2GB 闪存,VxWorks 实时操作系统。能源是放射性同位素热电机。

Posted in Computer and Internet, Programming and Algorithm | Tagged , | Leave a comment

ZOJ Problem Set – 3020 – Puzzle Quest

不知道多少人玩过 Puzzle Quest 这个游戏。这是个有日式画风,用宝石方块的对战方式来进行的RPG。一般的游戏模式需要进行消去,同时使用得到的宝石攻击对手。而怪物捕捉模式需要玩家将一块特定布局的棋盘上的宝石全部消去(GameFAQs 上有所有谜题的解答)。 ZOJ 3020 就是要求程序自动解这类的消去全部宝石的谜题(除去了爆炸骷髅这种宝石)。 最简单的解法当然就是深度优先搜索。流程代码还是比较简单的,就是检查每一种可能的操作和计算操作的结果,如果结果通过剪枝的话就迭代继续搜索。初步的剪枝算法也很简单,只要棋局中出现只有单个或两个的同种类宝石,就已经无解了。 深度优先搜索在比较简单的谜题上是没问题的,但是对一些复杂的谜题(一些需要10步以上操作的)就非常慢了。当一个谜题跑了10分钟还没结果的时候我放弃了,光靠优化算法的效率和使用更有效的复杂剪枝算法看来已经没法控制时间复杂度了。(之后看到别人给的代码,在深度搜索中加入了 hash表 作为棋局的缓存(类似动态规划了),能在3秒左右完成ZOJ的测试数据,但是在我的数据上仍然跑了1分钟多。) 于是对算法作了改动,改用启发式的最优最先搜索,由当前优先级最高的棋局继续搜索。这需要一个额外的判断棋局优先级的启发式算法(“看起来更有希望”的棋局有更高的优先级)。调查了几个花时间最长的谜题,加入两个条件,一个是棋局中剩余的宝石种类越少优先级越高(一是种类少一般剩余的宝石数量也少,另外也更方便接下去的消去操作),另一个是孤立的宝石距其它能凑成3个的宝石越远优先级越低(宝石分开的远的话很有可能在接下来的操作中没法把这些宝石凑在一起消除,鼓励程序优先消去这样的孤立宝石)。这样使程序的时间复杂度有了戏剧性的提高,能在1秒内跑完我全部的测试数据。 最后的成果是ZOJ上300毫秒的运行时间,之前ZOJ记录中最快的也需要2秒。 C++ 代码: 这类用程序自动解益智游戏的题还是相当有趣的。

Posted in ACM, Science | Tagged , | Leave a comment