Program Efficiency: Algorithm Doesn't Matter So Much - SIGMOD 2014

上学期组团参加了SIGMOD Programming Contest 2014, 进入了Finalist. 因此6月23日至26日, 我在Utah州Snowbird度假村参加ACM SIGMOD/PODS 2014会议.

每年的比赛题目跟ACM-ICPC比较像, 就是给输入, 产生确定的输出. 比赛形式的不同在于, ICPC中选手要尽量快的写出一个运行速度可以接受的程序, 而在SIGMOD比赛里, 我们需要在一个 多月时间里写出一个在给定机器上运行速度尽量快的程序, 而且可以用任何手段(并行, 汇编, SIMD, 文件读写).

最终结果与之前的online测试结果基本一致, 获得了第四名. 听了其他选手的报告, 深深的感觉到, 压榨程序效率时, 算法并不怎么重要.

Monte Carlo Tree Search & Monte Carlo Ray Tracing

这学期有两个有意思的大作业都跟Monte Carlo有那么点关系.


人智的大作业是写一个Connect Four 游戏的AI. 当然由于原本这个游戏是有必胜策略 的, 所以老师对这个游戏做了小修改. 给了50个测试AI, 编号2~100的偶数, 越牛的编号越大, 让我们打着玩, 评测时用另外一批AI.

建议的方法是$\alpha-\beta$剪枝, 但是写出来之后效果不行, 貌似缺一个好的估价函数. 但是编估价函数又有点蛋疼....这时候 maskray, zxytim, blahgeek 纷纷表示Monte Carlo Tree Search很靠谱.

SIFT and Image Stitching

图像处理课期中要写一个图像拼接程序.

这方面的技术当然已经很成熟了, 开源界最著名的当属hugin, 拼全景图效果非常好. 在学术界也已经不是难题了, Lowe在IJCV2007的一篇 Automatic Panoramic Image Stitching using Invariant Features 是一个完整的流程介绍. MSRA的Szeliski有过一本几十页的 Image Alignment and Stitching: A Tutorial, 也详细的介绍了图像拼接的众多方法. 我基本就照着Lowe, Szeliski的一堆论文的方法在搞.