一个月之前，我把之前知道的scala99除了最后两题都做了下。总体来说自己用Scala来解决一些算法问题上有了一些感觉。
scala99的问题分为List，Arithmetic，Logic，Binary Tree，Multiway Tree，Graph和Misc。树和图和之后的问题和算法关系大一些。以下列一些影像比较深的题目。
本次先是List相关。
Category: Scala
用DLX解sudoku(数独)
最近在做scala99，其中有一道题目P97是sudoku（数独）。一开始我想到的是列举每个空格的可选数字，选择可选数字最少的的格子开始填写。每次填写，修改关联格子的可选数字。再次尝试填写。这里无解条件是存在没有可选数字的格子。还有就是easy或者normal级别的数独一般可选数字都是1个，分批填写很快就能完成。hard或以上就没有那么幸运了，必须猜测然后验证，存在回溯。
这里描述的算法其实就是搜索+启发。启发是选择性地从最少可选数的格子开始。猜测+验证，感觉这个问题属于NP问题。事实上也确实是，而且可以转化为NP完全的精确覆盖问题（Exact Cover），所以这个问题也是NP完全问题。
P97给的答案有两个，第一个就是搜索+启发，第二个是DLX。DLX是Exact Cover的高效解法。本文就是讲如何用DLX来解数独问题的。考虑到scala99上第二个实现大部分都是可变数据，所以我用Java实现了相应算法。
finagle简单使用
在看awseome-scala的时候，正好看到了twitter的finagle。自己公司里貌似也有那种关注load balance等的解决方案，不过不是很容易理解。考虑到自己之前几个月都在弄电子技术了，重新弄点网络相关的把。
这次的任务是做了一个thrift+finagle的远程服务调用例子。其实不是很难，如果不是连续碰到finagle的坑的话。finagle是twitter开源出来的一个分布式系统解决方案，毕竟是大公司出来的东西，更新频率特别是文档很低，很多文档基本都是几年前，好在有代码……
rabbitmq在scala下的使用尝试
最近重拾scala，由于某些原因想要尝试了rabbitmq。于是便有了这块代码。
刚才重新看了rabbitmq的官网，上面关于scala的客户端的信息貌似更新了？之前那个lift-amqp太旧了，没法使用。不过没关系，这篇就当做了记录下如何在scala的环境下用rabbitmq的Java客户端。如果你想直接用现成的scala客户端，可以参考这里。
首先你要安装rabbitmq，这样之后好测试。mac下用brew安装命令是
|
1 2 |
$ brew update $ brew install rabbitmq |
05-05 学习记录
scala extractor and regex
最近遇到一个场景：输入三个数字，用逗号分隔，同时要求三个数字两两不相同。
常规解析需要分割出三个数字，转成整型，判断边界条件，最后判断两两是否相同。
重新温习了下scala的extractor，发现如下代码就可以清晰明了地解决这个场景：
04-23 学习记录
mongodb
最近回顾了下mongodb的安装，使用等。
ubuntu(12.04)下安装和启动
|
1 2 |
$ sudo apt-get install mongodb-server $ sudo mongod -f /etc/mongodb.conf |
默认会同时安装客户端，即命令mongo，换句话说是那个支持JavaScript的客户端。
macosx下安装和启动
|
1 2 3 |
$ brew update $ brew install mongodb $ mongod --config /usr/local/etc/mongod.conf |
brew update耗时会比较长，如果没有必要的话可以不做。
让dash搜索casbah
默认dash下是没有casbah的文档的，把casbah clone下来，尝试用mkScalaDocSet也失败了，casbah生成的文档多处出现不标准的XHTML。后来某一天发现dash支持Scala Docs，那么可以这么做：
- 进入Scala Docs，就是点击常规下载DocSets左边的Ruby, Java, Scala Docs导航栏中的Scala Docs
- 搜索casbah
- 找到你需要的casbah版本并下载，由于casbah有多个模块，大概要下3～4个
- 默认这些Scala Docs的前缀是scaladoc:，需要都改成casbah:，这样你就可以用casbah:搜索casbah多个模块了
注意，casbah的这个文档只是API文档，不是那种tutorial。不过一般来说应该够了。
海量积分排序的二分实现
简单描述下问题：有一个网站，现在有很多用户，每个用户有一个积分，要求在用户登录时显示用户的积分排名，用户的积分会有变动。注意考虑数据量比较大的场景。
原理是以树的方式来分解排名的计算。参考在这里。
实际代码分为三部分：
- 查询某个积分的排名
- 更新积分
- 构造积分树
查询积分排名
原理是计算所有右子树或者同级节点的和，再加1。每个节点包含当前积分或者积分段内的用户总数。右子树或者同级节点代表大于指定积分的积分节点。排名的实际含义就是计算所有大于自己积分的人的总数。最后加1是因为大于最大积分的人的总数为0，但是排名不能为0，所以实际显示是必须加1的。
这块实际依赖树的结构，可能是数组或者是链表，但通用逻辑如下（递归）：
|
1 2 3 4 5 6 7 8 9 10 11 |
in: current node, score if current node is score node if current node is left leaf return count of right sibling else # current node is right node, no right sibling return 0 else # current node is score range node if score in left subtree return count of score in left subtree + count of right subtree else # score in right subtree return count of score in right subtree |
scala模拟ketama算法
ketama是memcached客户端使用的一种一致性哈希算法。是为了解决余数实现分布不均匀的问题，在last.fm的一篇博客中首次提到。这里有一些介绍链接，其中第一篇是原博客。
- http://www.last.fm/user/RJ/journal/2007/04/10/rz_libketama_-_a_consistent_hashing_algo_for_memcache_clients
- http://blog.csdnnet/kangojian/article/details/6708460
- http://tech.idv2.com/2008/07/24/memcached-004/
原博客里面提到算法步骤如下：
- Take your list of servers (eg: 1.2.3.4:11211, 5.6.7.8:11211, 9.8.7.6:11211)
- Hash each server string to several (100-200) unsigned ints
- Conceptually, these numbers are placed on a circle called the continuum. (imagine a clock face that goes from 0 to 2^32)
- Each number links to the server it was hashed from, so servers appear at several points on the continuum, by each of the numbers they hashed to.
- To map a key->server, hash your key to a single unsigned int, and find the next biggest number on the continuum. The server linked to that number is the correct server for that key.
- If you hash your key to a value near 2^32 and there are no points on the continuum greater than your hash, return the first server in the continuum.
null-safe和scala的monad
长久以来，习惯了写如下的Java代码：
|
1 2 3 4 |
User user = userService.get(1); if(user != null) { doStuff(); } |
称之为null检查，亦有null != user的尤达式写法。
在学了Scala之后，知道了Option，改用如下写法：
scala版本的grails分页代码
大家平时见过这样的分页么？见过的话知道怎么写么？没见过的话有思路么？
|
1 |
Previous 1 .. 3 4 (5) 6 7 8 .. 10 Next |
就本人的话，在用grails时见到了这个强大的分页功能，但是对于里面的代码和思路一知半解。
今天心血来潮想要重新理解下原理，所以花了点时间分析了下实现，最终在回家的地铁上基本明白了其中的逻辑，特此写文分享。
在展示最终的scala代码之前，先说下分页中的几个概念，同时为了方便，这里取用grails中的变量名：