箱猫日和

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中的变量名：