Category: Scala

  • scala99解题小结(List)

    一个月之前,我把之前知道的scala99除了最后两题都做了下。总体来说自己用Scala来解决一些算法问题上有了一些感觉。 scala99的问题分为List,Arithmetic,Logic,Binary Tree,Multiway Tree,Graph和Misc。树和图和之后的问题和算法关系大一些。以下列一些影像比较深的题目。 本次先是List相关。

  • 用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安装命令是 $ brew update $ brew install rabbitmq

  • 05-05 学习记录

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

  • 04-23 学习记录

    mongodb 最近回顾了下mongodb的安装,使用等。 ubuntu(12.04)下安装和启动 $ sudo apt-get install mongodb-server $ sudo mongod -f /etc/mongodb.conf 默认会同时安装客户端,即命令mongo,换句话说是那个支持JavaScript的客户端。 macosx下安装和启动 $ 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的。 这块实际依赖树的结构,可能是数组或者是链表,但通用逻辑如下(递归): 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…

  • 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…

  • null-safe和scala的monad

    长久以来,习惯了写如下的Java代码: User user = userService.get(1); if(user != null) { doStuff(); } 称之为null检查,亦有null != user的尤达式写法。 在学了Scala之后,知道了Option,改用如下写法:

  • scala版本的grails分页代码

    大家平时见过这样的分页么?见过的话知道怎么写么?没见过的话有思路么? Previous 1 .. 3 4 (5) 6 7 8 .. 10 Next 就本人的话,在用grails时见到了这个强大的分页功能,但是对于里面的代码和思路一知半解。 今天心血来潮想要重新理解下原理,所以花了点时间分析了下实现,最终在回家的地铁上基本明白了其中的逻辑,特此写文分享。 在展示最终的scala代码之前,先说下分页中的几个概念,同时为了方便,这里取用grails中的变量名: