scala99解题小结(List)

一个月之前,我把之前知道的scala99除了最后两题都做了下。总体来说自己用Scala来解决一些算法问题上有了一些感觉。

scala99的问题分为List,Arithmetic,Logic,Binary Tree,Multiway Tree,Graph和Misc。树和图和之后的问题和算法关系大一些。以下列一些影像比较深的题目。

本次先是List相关。

Read More

用DLX解sudoku(数独)

最近在做scala99,其中有一道题目P97是sudoku(数独)。一开始我想到的是列举每个空格的可选数字,选择可选数字最少的的格子开始填写。每次填写,修改关联格子的可选数字。再次尝试填写。这里无解条件是存在没有可选数字的格子。还有就是easy或者normal级别的数独一般可选数字都是1个,分批填写很快就能完成。hard或以上就没有那么幸运了,必须猜测然后验证,存在回溯。

这里描述的算法其实就是搜索+启发。启发是选择性地从最少可选数的格子开始。猜测+验证,感觉这个问题属于NP问题。事实上也确实是,而且可以转化为NP完全的精确覆盖问题(Exact Cover),所以这个问题也是NP完全问题。

P97给的答案有两个,第一个就是搜索+启发,第二个是DLX。DLX是Exact Cover的高效解法。本文就是讲如何用DLX来解数独问题的。考虑到scala99上第二个实现大部分都是可变数据,所以我用Java实现了相应算法。

Read More

finagle简单使用

在看awseome-scala的时候,正好看到了twitter的finagle。自己公司里貌似也有那种关注load balance等的解决方案,不过不是很容易理解。考虑到自己之前几个月都在弄电子技术了,重新弄点网络相关的把。

这次的任务是做了一个thrift+finagle的远程服务调用例子。其实不是很难,如果不是连续碰到finagle的坑的话。finagle是twitter开源出来的一个分布式系统解决方案,毕竟是大公司出来的东西,更新频率特别是文档很低,很多文档基本都是几年前,好在有代码……

Read More

rabbitmq在scala下的使用尝试

最近重拾scala,由于某些原因想要尝试了rabbitmq。于是便有了这块代码
刚才重新看了rabbitmq的官网,上面关于scala的客户端的信息貌似更新了?之前那个lift-amqp太旧了,没法使用。不过没关系,这篇就当做了记录下如何在scala的环境下用rabbitmq的Java客户端。如果你想直接用现成的scala客户端,可以参考这里

首先你要安装rabbitmq,这样之后好测试。mac下用brew安装命令是

Read More

05-05 学习记录

scala extractor and regex

最近遇到一个场景:输入三个数字,用逗号分隔,同时要求三个数字两两不相同。
常规解析需要分割出三个数字,转成整型,判断边界条件,最后判断两两是否相同。
重新温习了下scala的extractor,发现如下代码就可以清晰明了地解决这个场景:

Read More

04-23 学习记录

mongodb

最近回顾了下mongodb的安装,使用等。
ubuntu(12.04)下安装和启动

默认会同时安装客户端,即命令mongo,换句话说是那个支持JavaScript的客户端。

macosx下安装和启动

brew update耗时会比较长,如果没有必要的话可以不做。

让dash搜索casbah

默认dash下是没有casbah的文档的,把casbah clone下来,尝试用mkScalaDocSet也失败了,casbah生成的文档多处出现不标准的XHTML。后来某一天发现dash支持Scala Docs,那么可以这么做:

  1. 进入Scala Docs,就是点击常规下载DocSets左边的Ruby, Java, Scala Docs导航栏中的Scala Docs
  2. 搜索casbah
  3. 找到你需要的casbah版本并下载,由于casbah有多个模块,大概要下3~4个
  4. 默认这些Scala Docs的前缀是scaladoc:,需要都改成casbah:,这样你就可以用casbah:搜索casbah多个模块了

注意,casbah的这个文档只是API文档,不是那种tutorial。不过一般来说应该够了。

海量积分排序的二分实现

简单描述下问题:有一个网站,现在有很多用户,每个用户有一个积分,要求在用户登录时显示用户的积分排名,用户的积分会有变动。注意考虑数据量比较大的场景。

原理是以树的方式来分解排名的计算。参考在这里
实际代码分为三部分:

  • 查询某个积分的排名
  • 更新积分
  • 构造积分树

查询积分排名

原理是计算所有右子树或者同级节点的和,再加1。每个节点包含当前积分或者积分段内的用户总数。右子树或者同级节点代表大于指定积分的积分节点。排名的实际含义就是计算所有大于自己积分的人的总数。最后加1是因为大于最大积分的人的总数为0,但是排名不能为0,所以实际显示是必须加1的。
这块实际依赖树的结构,可能是数组或者是链表,但通用逻辑如下(递归):

Read More

scala模拟ketama算法

ketama是memcached客户端使用的一种一致性哈希算法。是为了解决余数实现分布不均匀的问题,在last.fm的一篇博客中首次提到。这里有一些介绍链接,其中第一篇是原博客。

原博客里面提到算法步骤如下:

  1. Take your list of servers (eg: 1.2.3.4:11211, 5.6.7.8:11211, 9.8.7.6:11211)
  2. Hash each server string to several (100-200) unsigned ints
  3. Conceptually, these numbers are placed on a circle called the continuum. (imagine a clock face that goes from 0 to 2^32)
  4. 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.
  5. 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.
  6. 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.

Read More

null-safe和scala的monad

长久以来,习惯了写如下的Java代码:

称之为null检查,亦有null != user的尤达式写法。
在学了Scala之后,知道了Option,改用如下写法:

Read More

scala版本的grails分页代码

大家平时见过这样的分页么?见过的话知道怎么写么?没见过的话有思路么?

就本人的话,在用grails时见到了这个强大的分页功能,但是对于里面的代码和思路一知半解。
今天心血来潮想要重新理解下原理,所以花了点时间分析了下实现,最终在回家的地铁上基本明白了其中的逻辑,特此写文分享。

在展示最终的scala代码之前,先说下分页中的几个概念,同时为了方便,这里取用grails中的变量名:

Read More