一个月之前,我把之前知道的scala99除了最后两题都做了下。总体来说自己用Scala来解决一些算法问题上有了一些感觉。
scala99的问题分为List,Arithmetic,Logic,Binary Tree,Multiway Tree,Graph和Misc。树和图和之后的问题和算法关系大一些。以下列一些影像比较深的题目。
本次先是List相关。
Box Cat Happy Day
一个月之前,我把之前知道的scala99除了最后两题都做了下。总体来说自己用Scala来解决一些算法问题上有了一些感觉。
scala99的问题分为List,Arithmetic,Logic,Binary Tree,Multiway Tree,Graph和Misc。树和图和之后的问题和算法关系大一些。以下列一些影像比较深的题目。
本次先是List相关。
最近在做scala99,其中有一道题目P97是sudoku(数独)。一开始我想到的是列举每个空格的可选数字,选择可选数字最少的的格子开始填写。每次填写,修改关联格子的可选数字。再次尝试填写。这里无解条件是存在没有可选数字的格子。还有就是easy或者normal级别的数独一般可选数字都是1个,分批填写很快就能完成。hard或以上就没有那么幸运了,必须猜测然后验证,存在回溯。
这里描述的算法其实就是搜索+启发。启发是选择性地从最少可选数的格子开始。猜测+验证,感觉这个问题属于NP问题。事实上也确实是,而且可以转化为NP完全的精确覆盖问题(Exact Cover),所以这个问题也是NP完全问题。
P97给的答案有两个,第一个就是搜索+启发,第二个是DLX。DLX是Exact Cover的高效解法。本文就是讲如何用DLX来解数独问题的。考虑到scala99上第二个实现大部分都是可变数据,所以我用Java实现了相应算法。
在看awseome-scala的时候,正好看到了twitter的finagle。自己公司里貌似也有那种关注load balance等的解决方案,不过不是很容易理解。考虑到自己之前几个月都在弄电子技术了,重新弄点网络相关的把。
这次的任务是做了一个thrift+finagle的远程服务调用例子。其实不是很难,如果不是连续碰到finagle的坑的话。finagle是twitter开源出来的一个分布式系统解决方案,毕竟是大公司出来的东西,更新频率特别是文档很低,很多文档基本都是几年前,好在有代码……
最近重拾scala,由于某些原因想要尝试了rabbitmq。于是便有了这块代码。
刚才重新看了rabbitmq的官网,上面关于scala的客户端的信息貌似更新了?之前那个lift-amqp太旧了,没法使用。不过没关系,这篇就当做了记录下如何在scala的环境下用rabbitmq的Java客户端。如果你想直接用现成的scala客户端,可以参考这里。
首先你要安装rabbitmq,这样之后好测试。mac下用brew安装命令是
1 2 |
$ brew update $ brew install rabbitmq |
最近遇到一个场景:输入三个数字,用逗号分隔,同时要求三个数字两两不相同。
常规解析需要分割出三个数字,转成整型,判断边界条件,最后判断两两是否相同。
重新温习了下scala的extractor,发现如下代码就可以清晰明了地解决这个场景:
最近回顾了下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的文档的,把casbah clone下来,尝试用mkScalaDocSet也失败了,casbah生成的文档多处出现不标准的XHTML。后来某一天发现dash支持Scala Docs,那么可以这么做:
注意,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 |
ketama是memcached客户端使用的一种一致性哈希算法。是为了解决余数实现分布不均匀的问题,在last.fm的一篇博客中首次提到。这里有一些介绍链接,其中第一篇是原博客。
原博客里面提到算法步骤如下:
长久以来,习惯了写如下的Java代码:
1 2 3 4 |
User user = userService.get(1); if(user != null) { doStuff(); } |
称之为null检查,亦有null != user的尤达式写法。
在学了Scala之后,知道了Option,改用如下写法:
大家平时见过这样的分页么?见过的话知道怎么写么?没见过的话有思路么?
1 |
Previous 1 .. 3 4 (5) 6 7 8 .. 10 Next |
就本人的话,在用grails时见到了这个强大的分页功能,但是对于里面的代码和思路一知半解。
今天心血来潮想要重新理解下原理,所以花了点时间分析了下实现,最终在回家的地铁上基本明白了其中的逻辑,特此写文分享。
在展示最终的scala代码之前,先说下分页中的几个概念,同时为了方便,这里取用grails中的变量名: