Goodbye,Google Reader

今天早上,把Google Reader的订阅迁移到鲜果,顺便整理了Reader里边的RSS订阅,略为增长了一点,到153个,主要增加了许多国内著名互联网公司的团队博客。 鲜果是把订阅和RSS订阅分开的,对于我来说,这显得很不习惯。对于鲜果来说,想打造社交阅读平台,又不得不保留RSS订阅这种传统模式,也是挺无奈的。

另外,看过Feng写的那些写过博客的人们,我也发现了有不少人的博客很久之前就停止更新了。 博客这东西,在微博,微信等新媒体的冲击下,更显得步伐缓慢,似乎不适应新时代的要求。但只有这些写下的文字,才显得有点沉淀, 也只有部分通过写博客获得了某些真实东西的人才坚持下来。

分享一下我的RSS订阅.

Google Reader即将关闭,阅读还将继续~

读书会,爱读书

话说,很久没有更新博客了,真是惭愧呀。

今天下午,在部门里边小范围举行了一场读书分享会。我把最近读的一本书,java解惑跟大家分享一下。 主要使用了书中的一些范例,跟大家一起学习探讨,分享会下来,大家都觉得挺高兴的。

我的主要目的也达到了,活跃一下大家的气氛,接下来计划每周简单搞一次,或许再弄点吃的,好好享受这个过程。 当然,这个需要持续进行,还少不了更多人的支持,慢慢把范围和影响扩大,逐渐成为一个招牌节目:)

java解惑也是好几年前的书了,很早之前就听过,这次是在地铁上拿电子版在看,基本上我只能答对里边一半左右的谜题, 感觉对于java这么古板的语言,坑都不少,跟何况c++这样的庞然大物? 总体来说,我给这本书评4颗星,推荐级别。

下周的读书会,讲一本java网络编程的入门书籍。

判断循环菜单的思考

今天下午的时候,在执行gem clean命令看到包依赖的时候,突然想起关于循环菜单的老问题。

无限级菜单的问题

很多系统的菜单都要求是无限级的,也就是可以很多层的父子菜单关系。 在进行数据存储的设计的时候,以数据库为例,通常都会给菜单表增加一个父菜单的字段,用来标识从属于哪个菜单。

这里就要求菜单的配置不能出现循环,例如某个菜单的父父菜单是它的子菜单,这是不允许的。 但有时候难免出现一些错误,特别不是通过可视化界面增加菜单的时候。我们的系统也曾经出现过,例如见定位数据问题

如何判断循环

就拿定位数据问题来说,当时时间比较急就没多想,直接参考了项目中已有的逻辑。

考虑整个菜单结构是一棵树的话,它的判断逻辑的思路是,第一次把根结点去掉(最顶层的菜单), 第二次把剩余的树的根结点去掉,以此类推,直到最后没有结点(没有循环),或没有结点可以删除(出现循环)。 写成伪代码的话,大约是这样的:

hasDel = true

do
  hasDel = false
  for 结点 in 
    if 结点 has not 父节点
      删除结点 and hasDel = true
    end
  end
while hasDel

if 还剩下结点
  出现循环
else
  没有循环
end

因为每次操作都要循环剩下的整个树,循环的次数很关键,如果树有3层,扫描3次即可,如果层次很深,扫描的次数就比较可观了。

另一个思路

以其中某个结点为例,它有父节点..一直到根节点,或者出现循环。 如果不是循环,则整结点都可以去掉。这样的话,只需要遍历整棵树,对未处理的结点,进行循环判断即可,而处理过的(去掉的)可以忽略。

伪代码如下:

for 结点 in 
  if 结点已经被标识为已处理
    continue
  else 
    判断结点到根结点是否存在循环(如在路径上遇到已处理的直接返回false)
    if 存在循环
       出现循环
    else
       标记结点到根结点为已处理
    end
  end
end

问题现在就回到如何判断循环链表,这其实是个经典的面试笔试题了,我在网上挑了其中一个解答:判断循环链表 对于我们的情况,在遇到已处理结点的时候,直接就可以说明没有循环了,这里可以小优化一下。

效率分析

我们粗略的分析一下,外层循环的数量级是整个树的结点数,判断循环的逻辑是和结点的深度有关系的, 以极端的情况为例,只有1层的话,很明显,相当于扫描一次结点。如果是个非常深的结点(都是单子结点),就最后一个的结点的话,循环判断的次数也是和结点数成线性的。

结点越深,循环判断的次数就越多,跟结点到根节点的长度成正比,但一次排除的结点也越多。总体还是跟总的结点数成线性正比的。 相对于原来的处理方式,平均效率就是它的最好效率。

小结

判断链表是否存在循环这种面试题,还是有点实际用处的,以前真的没特别留意。 算法这东西,真的是无处不在的呀。

这些天,我们用到的算法

平时做的应用,的确很少涉及非常具体的局部算法。不过最近一段时间还是遇到了一些,稍微整理一下,留个纪念。

产品的组合生成

举个例子,手机的颜色有黑白的,内存有16G,32G的,那么就有黑色16G,黑色32G,白色16G,黑色32G等组合项, 当然属性可能不止两项,想列出所有的组合项。

如果只有两种属性,很简单

for(属性 in 属性1)
    for(属性 in 属性2)
       // TODO 得到组合项

但是,如果有不定项的话,就不能这么写了。

这需要知道点回溯法的技巧,我是用了非递归的方式编写的:

    public static List<List<String>> merge(List<String>... ls) {
        int len = ls.length;
        int[] pos = new int[len];//对i而言,表示第i种属性当前选择是哪个值
        Arrays.fill(pos, 0);
        String[] r = new String[len];//存放待生成的组合项

        List<List<String>> res = new ArrayList<List<String>>();
        int k = 0;//当前正在遍历第几种属性
        while (k >= 0) {
            while (pos[k] < ls[k].size()) {
                r[k] = ls[k].get(pos[k]);
                if (k == len - 1) {//是否已经是最后一个属性
                    // 找到一个组合项,复制到res里边去
                    pos[k] = pos[k] + 1;
                } else {
                    k++;//当前位置的属性已经选择,处理下一种属性
                }
            }
            pos[k] = 0;
            k--;//当前位置的属性已经遍历完,需要回溯到上一种属性去
            if (k > 0) {
                pos[k] = pos[k] + 1;
            }
        }
        return res;
    }

说真的,即使加了注释,没有相关的算法基础,也是不容易看清楚的,所以有同事看到这个写法,在大呼救命。

请求URL参数匹配

最近有需求,要对请求里边的参数做匹配,规则是这样的:

例如有下面三条规则(其中问号表示变量,参数的顺序没关系):

  • User=?&Password=BB&CurrentTab=LOG&CurrentTab2=LOG
  • User=?&Password=?&CurrentTab=LOG1
  • User=?&Password=?&CurrentTab=LOG

如果请求参数是XX=222&User=Q&Password=BB&CurrentTab=LOG,则只能匹配第三条,因为第一条多一个参数,第二条的值是LOG1,对应不上。
如果请求参数是User=QQ&CurrentTab=LOG1&Password=AA,同样只能匹配到第三条。

有个非常简单的思路,就是把参数拆开,然后一个个匹配。但是由于业务的请求数非常大,担心对系统是否有影响。

于是,弄了个测试原型,开50个线程的线程池,跑500个任务,每个任务跑1w次,匹配3个配置项。整个框架代码是这样的:

    public void work() throws Exception {

        final String match1 = "User=?&Password=BB&CurrentTab=LOG&CurrentTab2=LOG";
        final String match2 = "User=?&Password=?&CurrentTab=LOG1";
        final String match3 = "User=?&Password=?&CurrentTab=LOG";

        ExecutorService pool = Executors.newFixedThreadPool(50);
        int tasksize = 500;
        final CountDownLatch latch = new CountDownLatch(tasksize);

        long s = System.nanoTime();
        for (int k = 0; k < tasksize; k++) {
            pool.submit(new Runnable() {
                @Override
                public void run() {
                    Random r = new Random(100000000);
                    for (int i = 0; i < 10000; i++) {
                        String toMatch = "XX="
                                         + r.nextInt()
                                         + "&User=AA&Password=BB&CurrentTab=LOG";
                        // TODO 测试toMatch
                    }
                    latch.countDown();
                }
            });
        }

        latch.await();
        System.out.println(System.nanoTime() - s);
    }

先用最简单的方法来做基准测试,有时候最简单的方法就可以满足要求了,粗略的代码如下:

                        Map<String, String> matchs = new HashMap<String, String>();
                        String[] split = toMatch.split("&");
                        for (String mss : split) {
                            String[] split2 = mss.split("=");
                            matchs.put(split2[0], split2[1]);
                        }
                        similar(match1, matchs);
                        similar(match2, matchs);
                        similar(match3, matchs);
    
                        ....

    private boolean similar(String match, Map<String, String> matchs) {

        String[] ms = match.split("&");
        for (String m : ms) {
            String[] split2 = m.split("=");
            if (!matchs.containsKey(split2[0]))
                return false;

            if (!"?".equals(split2[1])) {
                if (!split2[1].equals(matchs.get(split2[0])))
                    return false;
            }
        }
        return true;
    }                        

在我的机器上简单跑一下,大约要28s。这个算法非常暴力,用split和map结构搞定了。 如果用StringTokenizer的话,还能快些,我试了一下,把第一步split换了的话,大约需要25s. 我觉得这个效果也还是可以接受的。

下面再用纯手工操作字符串的方式,代码如下:

                        UrlMatcher matcher = new UrlMatcher(toMatch);
                        matcher.match(match1);
                        matcher.match(match2);
                        matcher.match(match3);

    class UrlMatcher {
        private String toMatch;
        int[] pos = new int[20];
        int ps;

        public UrlMatcher(String toMatch) {
            int ss = 0;
            this.toMatch = toMatch;
            int len = toMatch.length();
            int st = 0;
            int ed = 0;
            for (int i = 0; i < len; i++) {
                char c = toMatch.charAt(i);
                if (c == '=') {
                    ed = i - 1;
                    pos[ss++] = st;
                    pos[ss++] = ed;
                    st = i + 1;
                    pos[ss++] = st;
                } else if (c == '&') {
                    pos[ss++] = i - 1;
                    st = i + 1;
                }
            }
            pos[ss] = len - 1;
            ps = (ss + 1);
        }

        public boolean match(String m) {
            int len = m.length();
            int st = 0;
            int ed = 0;
            int vs = 0;
            int ve = 0;

            for (int i = 0; i < len; i++) {
                char c = m.charAt(i);
                if (c == '=') {
                    ed = i - 1;
                    vs = i + 1;
                } else if (c == '&') {
                    ve = i - 1;

                    if (!match2(m, st, ed, vs, ve)) {
                        return false;
                    }

                    st = i + 1;
                }
            }
            return match2(m, st, ed, vs, len - 1);
        }

        boolean match2(String m, int st, int ed, int vs, int ve) {
            boolean ma = true;
            for (int i = 0; i < ps; i = i + 4) {
                if (pos[i + 1] - pos[i] == ed - st) {
                    int sst = st - pos[i];
                    for (int j = pos[i]; j <= pos[i + 1]; j++) {
                        if (toMatch.charAt(j) != m.charAt(sst + j)) {
                            ma = false;
                        }
                    }

                    if (ma) {
                        if (ve == vs && '?' == m.charAt(vs)) {
                            return true;
                        } else {
                            if (pos[i + 3] - pos[i + 2] == ve - vs) {
                                int vst = vs - pos[i + 2];
                                for (int j = pos[i + 2]; j <= pos[i + 3]; j++) {
                                    if (toMatch.charAt(j) != m.charAt(vst + j)) {
                                        return false;
                                    }
                                }
                                return true;
                            } else {
                                return false;
                            }
                        }
                    }

                }
            }
            return false;
        }
    }                       

代码比较粗糙,对某些情况不是很严格,但不影响总体的性能评测,这个逻辑不到2s,要快15倍以上。 这个写法的特点是:使用数组而不是Map,使用标记位置而不是截取字符串,一次扫描。

不过,这个代码很粗糙,不要太当真。

看看我机器上显示的虚拟机负载情况。

图1:最简单的做法 简单方法+多线程

图2:手工打造,相对的内存消耗小些 手工打造+多线程

图3:还是手工打造,不过单线程,相对来说CPU使用率就小很多了 手工打造+单线程

小结

经常听到算法没什么用,算法没地方使用的论调,我也都一笑置之。 不过,我也承认,在现在的工作中,的确很少会直接面对非常具体的局部算法。 但我还是不能赞同上面的观点,毕竟有些场景还是不得不考虑的:

  1. 做不到,没有算法的支持,根本不知怎么写好
  2. 做不好,简单的实现没法满足,需要高效的算法

手绘的思维导图:程序员的思维修炼

手绘的思维导图

先看看今天早上手绘的作品,没有工具绘制的工整,但感觉效果更棒!

程序员的思维修炼

再谈谈这本书

这本书感觉就是从小工到专家的续作,但不是只有程序员才能阅读并受益的书籍,推荐指数:5个星星。

书的主题是围绕德雷福斯技能模型,区分L型和R型思维方式,讲述如何学习的技能。在实践方式上,我重点谈谈我印象比较深的几个方法。 这些方法的操作性也比较强:

  1. 晨写,早上第一件事,只写不审查
  2. 自由写,就是写博客的习惯
  3. SMART任务
  4. SQ3R主动阅读
  5. 手绘思维导图
  6. 以教代学,说出来
  7. 冥想,关注呼吸,类似自我催眠的技巧
  8. GTD,不要在头脑保存列表

1和2是记录和积累,3是目标管理,4和5,6是增强学习效果,7和8是注意力管理。 现在来说,关于晨写和SMART,我没什么使用经验,正在学习。