从用缓存优化函数性能说说第三方框架的使用

导读

前面两篇文章分别从计算机及领域知识编程语言本身的角度聊了聊写代码要考虑的事儿。但是理解了计算机系统、领悟了领域知识、精通了某门编程语言就够了么?我在编程到底难在哪里的回答里说,软件开发是搭积木式的,如果你想搭得好又有价值,一个合理的办法是在已经搭好的基础上继续搭,而不是把所有东西自己重新搭一遍。JDK和.NET Framework都是这种已经搭好了的最基本的架子。想想软件发展了几十年,各式框架已经一应俱全,基本想做个任何事情都已经有现成的框架可用。当然,如果你觉得现在已经搭好的东西就是坨屎,当然可以也应该自己搭个更好的。但是现实的情况大都是:人家明明已经搭好那么多各式各样的建筑并欢迎你去添砖加瓦,结果只是因为自己不知道、不了解那些东西的存在,自己重头搭了个双层火柴盒还觉得不错。软件开发显然比在minecraft里搭积木要复杂且抽象些。随之而来的一个问题就是:可应用框架的地方并不显而易见,尤其是当你觉得自己写一个更快的时候。这也是本文将要讨论的重点。(在校生请不要误会,在校生请夯实基础并从基础搭起,能搭多少搭多少。)

引子

假设我们发现这个下面开平方函数很慢,比如要一秒,我们Profile之后发现函数慢在Math.sqrt这个第三方函数上,遗憾的是下层Math库的作者声称他那边儿没有进一步提速的空间了,而且他已经不再维护了。然而我们死活就是想要提高这个函数的性能,怎么办?

public double sqrt(final double n) {
    return Math.sqrt(n);
}

代码 1

解决方法倒是有不少的,比如升级硬件,比如换一个更快的库,比如开多线程,或者把Math的作者高薪挖过来。只是这些方案的成本都不低。考虑到这个函数是个纯函数,又考虑到内存并不是很贵,如果又能和用户确认一下他们的输入并不是随机的,有比较高的重复度和局域性的话。把这个函数的运算结果保存下来或许是最多快好省的方案了。实现起来也很简单(注:请无视代码2的拆装箱损耗,那不是问题重点)。

private final Map<Double, Double> rootMap = new ConcurrentHashMap<>();

public double sqrt(final double n) {
    return rootMap.computeIfAbsent(n, Math::sqrt);
}

代码 2

这个实现的一个问题就是它只加不删。如果用户真能保证他们的输入有比较高的重复性的话这个问题倒不大。但是保不齐存在一个2B用户没按约定使用,系统最后就OOM了,然后常见的后果是这个软件员会被拉出来背内存泄漏导致宕机的锅。所以保险起见应该给这个Map设定一个上限。到了就把老化的结果删除。(注:请无视代码中try..finally及iterator的用法,那也不是重点)

private final Map<Double, Double> rootMap = new LinkedHashMap<>();
private final int maximumSize = 1000;

public double sqrt(final double n) {
    try {
        return rootMap.computeIfAbsent(n, Math::sqrt);
    } finally {
        if (rootMap.size() > maximumSize) {
            rootMap.remove(rootMap.keySet().iterator().next());
        }
    }
}

代码 3

如果用户只要求精确到小数点后两位就够了。那么一个简单的提高命中率的改进就是把参数先进行舍入再执行运算。

private final Map<Double, Double> rootMap = new LinkedHashMap<>();
private final int maximumSize = 1000;

public double sqrt(final double n) {
    final double r = round(n, 2);
    try {
        return rootMap.computeIfAbsent(r, Math::sqrt);
    } finally {
        if (rootMap.size() > maximumSize) {
            rootMap.remove(rootMap.keySet().iterator().next());
        }
    }
}

public double round(final double n, final int scale) {
    return new BigDecimal(Double.toString(n))
              .setScale(scale, BigDecimal.ROUND_HALF_UP))
              .doubleValue();
}

代码 4

好了,到目前为止,在不考虑线程安全性的前提下,我对这个函数结果留存的实现方案算是比较满意了。然后才是本文的正题:代码4的问题是什么?如何解决?

问题在哪儿

业务逻辑不明确

想象一下,如果你第一次看到这个代码4,你能否一眼看出哪些代码是业务逻辑的需要,哪些不是?

这还仅仅是为保存一个方法的执行结果,就多出了十几行代码。这还没打Log呢,还没处理异常呢,还没加调用信息统计呢,还没做运行时Profiling呢,还没保证多线程安全呢。

请想象一下,你把上面的这些附加功能都按从代码1到代码4的实现方式加上去,这代码还能看么?

解决思路很简单:业务逻辑应该与非业务逻辑分离

代码冗余、维护成本高

软件开发的一个基本的原则就是写的代码要测试一下。你自己写了个round方法,你就得写相应的测试覆盖这个函数吧。你代码多,测试也会多。这都是实现上的成本。

另一方面,这回的情况是这样:你在实现这个功能的时候,发现需要这个round方法,于是自己写了一个。另一个程序员在界面显示的时候为了做截断可能也会自己写个round方法。大家在同一个Team、同一个代码库上工作,最好是不要出现这种很多人做重复性的工作。怎么解决呢?可以写个utils包,每个人想到什么感觉可能对别人也有用的东西就放在里面。

但是这其实是个悖论,如果一个程序员在实际项目上连类似这种round的方法都去自已写,有两种可能:一、公司什么库都不让用或是用之前要走半年流程什么的,这个可以通过跳槽来解决。二、意味他并没有事先查找可用utils的意识,没有这种意识的话,就算有别的成员放在项目内utils包里他大概也是不会找的。当然,这个情况可以这样解决:谁写了之后,大家开个会广告一下。最终结果大概会是:程序员们为了不开会,非常自觉地都不再写任何utils了。

更好的办法就是,只要有哪个著名的开源库里有的,大家就都不要自己写这种常见的功能。当然这个办法对于一小部分人来说也会有问题:谁知道我要的东西在哪个开源库里有?这个问题只有Google和Stackoverflow能回答。然后Google之后发现了一堆库可以用的,那么用哪个呢?

如果就是不乐意用别人的东西,非想要自己写,也行。在Team里找一两个最NB的人专门负责这些低层框架上的东西。并给所有人做好Training。

最要不得的就是想到什么就写什么。就像代码4那样。它看上去代码质量也挺高,Style也挺不错,目测也没Bug,但是成本高,没法维护、不好拓展。

可重用性差

考虑一下,如果你需要把Math类里的所有函数都做这样的处理呢?我猜会不会有人想用Map<String, Map<String, Object>>什么的?而且只改一个文件就行了呢!

再考虑一下,如果这个函数的调用会抛出异常呢?你是想把异常也保存一下呢?还是想下次重试呢?

上面的Map使用的是最简单的FIFO策略,如果你需要LRU呢?

还有,你这里把round之后的结果当Key,如果有的需要用toString()的结果当Key呢?

你每种情况具体分析分别实现还是为之写个通用框架呢?

在别人的肩膀上搭积木

善用第三方库

这个世界上的肩膀很多,如果想搭好自己的积木就要找到合适的肩膀,最重要的一步是找到那个重复出现的问题是什么,找到那个模式(不限于设计模式,也包括规范、代码模式等)。

限定大小的Map就是个会重复出现的问题。round一个double值也是个会重复出现的问题。显然这些问题Apache和Google都遇到过,并把他们的库公开了出来给大家用。用上之后代码就可以简化很多。(注:Guava也有类似的Map)

import org.apache.commons.math3.util.Precision;
import org.apache.commons.collections4.map.LRUMap;

private final Map<Double, Double> rootMap = new LRUMap<>(1000);

public double sqrt(final double n) {
    return rootMap.computeIfAbsent(Precision.round(n, 2), Math::sqrt);
}

代码 5

这个例子很容易,但是实现中的情况会比这个复杂得多。复杂的不是要实现的功能本身,最难是你能不能找到模式,找到可以重用的现成的东西,然后最重要的:用对。不要拿着锤子看什么都像钉子。比如,如果你觉得Java 8的Stream不错。但是把Stream这样用就不对了。(注:代码来自Stackoverflow的某问题的回答)

// BEING: Wrong usage example
public Double round(final Number src, final int scale) {
    return Optional.ofNullable(src)
                   .map(Number::doubleValue)
                   .map(BigDecimal::new)
                   .map(dbl -> dbl.setScale(scale))
                   .map(BigDecimal::doubleValue)
                   .orElse(null);
}
// END: Wrong usage example

代码 6

这个代码就是在风格或某一特性上走极端了。

剥离非业务逻辑

代码5仅仅是用上了些第三方的库,代码相对简洁了些。但是比代码1还是复杂了3倍。而且你一眼看去,很容易就产生误解,把rootMap当成了核心。而其实Math::sqrt才是。

现在我们目标很明确,就是要让我们的代码只做我们需要做的事情,让库和框架去解决别的和业务本身没关系的问题。代码5做到了一部分,但是不彻底,而且还有侵入性(你要用一个框架就要对现有代码大动干戈的性质)。有没有办法让代码回到代码1的程度呢?

有人可能想到了。AspectJ可以做到。只要在项目里放一个这样的Aspect,然后就直接用代码1就是了。(注:此为示意代码)

@Aspect
@Component
public class StoreMethodResult {
    private final Map<Double, Double> map = new LRUMap<>(10000);

    @Around("execution(* *.Calculator.*(..)) && args(value,..)")
    private Object round(ProceedingJoinPoint pjp, double value) 
        throws Throwable {
        return map.computeIfAbsent(Precision.round(value, 2), v -> {
            return (Double) pjp.proceed(new Object[]{v});
        });
    }
}

public class Calculator {
    public double sqrt(final double n) {
        return Math.Sqrt(n);
    }
}

代码 7

我们解决了代码4的问题,成功把它简化回到了代码1的程度。但是这样搞会引入两个新问题:

  1. StoreMethodResult和Calculator是两个类。单看Calculator你是无法知道Calcuator在执行的时候它的结果会被保存下来。所以你给代码1加一个能力、功能、机制的时候,还是最好在Calculator本身上留下点儿线索。一个代码是注释。更好的办法是用Annotation。按这个思路做下去,就会需要一个Annotation Driven的Aspect。
  2. 代码7本身也存在类似代码4的问题:它也是在重新造轮子。这个轮子叫缓存(Cache)。

通用化方案

这个函数调用结果保存下来的需求实在是太广泛了,肯定已经有现成的通用解决方案了啊。Spring Cache就是其中的一个方法。使用Spring Cache和Spring Boot的实现方式就是这样:

@SpringBootApplication(scanBasePackages = {"your.package.name.*"})
@EnableCaching
public class Application {
    @Bean
    public CacheManager getCachemanager() {
        final SimpleCacheManager simpleCache = new SimpleCacheManager();
        simpleCache.setCaches(Lists.newArrayList(
      new ConcurrentMapCache("math")));

        return simpleCache;
    }

    @Cacheable(value = "math", 
        key = "T(org.apache.commons.math3.util.Precision).round(#n, 2)")
    public double sqrt(final double n) {
        return Math.sqrt(n);
    }
}

代码 8

代码看着好多,但是前面的都是初始化Cache的部分。对于sqrt函数而言,只需要放个@Cachable就行了。

用Spring Cache不是目的,少写代码也不是重点。请注意在这个实现方案下,函数与其附加能力是放在一起的,而与主要业务逻辑又是分离的。这才是重点。库和框架的使用,应该是为了让你更高效地写出更可读、更少Bug的代码。如果你用一个框架之后,发现代码比之前更不好读,你可能得想想你有没有用对,或是你选择的这个框架本身的设计理念是不是合理。但是代码好不好读这个事儿有些主观,有人反而会觉得用了一堆他不会正确使用的框架的代码才是不好读的。我就呵呵了。相关讨论请参考本系列第一篇《从开平方说说写代码应该考虑的事儿》。

JSR-107 JCache

在程序中Cache结果的能力是如此基本,人们早在2001年就开始了把它放在Java框架里的讨论,即JSR-107。但是不知道是不是因为用的人太多,争论过于激烈,这个JSR在2012年才发布了早期预览草案。直到2014年3月才发布了最终版。

Spring Cache是在2011年引入到Spring 3.1 M1的。Spring Cache本身不是缓存框架,它是各种缓存框架与Spring的胶水(虽然它也自带了个实现,但是功能性要差很多)。Spring Cache的实现和JSR中推荐的做法非常相近,再从Spring Cache发布和JSR的时间线看来,或许Spring Cache在推动JSR-107的进程上也发挥了不小的作用。

在2014年4月,JSR-107最终发布的一个月之后,Spring就在4.1版中提供了对JSR-107的支持

然而JCache毕竟和Spring Cache还不是完全一致的。所以使用JCache实现的版本看上去会有些不一样。(注:CacheManager的创建还是需要的,只是略去了。)

@CacheResult(
        cacheName = "math", 
        cachedExceptions = { IllegalArgumentException.class })
public double sqrt4(@CacheKey final double n) {
    return Math.sqrt(n);
}

public double roundedSqrt(final double n) {
    return sqrt3(Precision.round(n, 2));
}

代码 9

不难发现JCache的Annotation和Spring Cache的用法略有不同。于是产生了下面几个不同:

  1. 由于自定义key表达示的缺失不得不引入一个新的函数来实现Round的行为。
  2. cachedExceptions的出现又让我们相对比较容易地处理异常。
  3. 独立的@CacheKey的用法相对直观,但是灵活度不足。

各有各的优劣。没有哪一个是完美的。在实际使用中应该根据实际需要选择最合适的框架。需要注意的是,这种使用方式上的不同,对于框架的选择一般是次要性因素。其使用方式上的不同,往往是其设计理念与目标的不同的外在体现而已。而设计理念与目标,才是选择框架的主要指标与标准。

 综述

像本文这样举一个例子,说明正确使用库与框架带来的诸多好处,是件很容易的事儿。然而实际这样做起来绝不会像说起来这么简单。因为你不仅仅要完成需求,还要识别出其中的模式与通用部分,查找可用的库或框架,然后再学习这些库的正确使用方式并集成到你的项目中。从代码4到代码8,代码没多,但是其实是比自己写一个更难,所花的时间也更多。(尤其是你还并不知道也还不会用那些框架的时候)。然而这些多出来的步骤都不是障碍,最大的障碍是心魔。

当你千辛万苦调了几天Bug把代码跑通大功告成之后,是觉得这是结束?还是刚刚开始?愿意不愿意想一想有没有别的方法做同样的事儿?愿意不愿意去把各个方案比较一下?愿意不愿意承认自己一开始拍脑袋想到的办法可能不是最合适的?如果是项目工期十分紧张的情况下呢?如果你的同事、你的领导甚至整个公司都并不赏识你的做法,只求一个个的项目能按时上线呢?如果你现在已经处于天天加班,天天调试老代码又不敢大改的窘境了呢?

那些都不是真的困境,那些都是自己的心魔。

从一个小函数说说编程语言的学习

PHP是世界上最好的语言[1]。

——有人说

编程语言层面上的东西根本不是重点,把基本功打好,学一门新的语言就是信手拈来。

——又有人说

这俩梗好老。

——我说

引言

上一篇文章《从开平方说说写代码应该考虑的事儿》讨论了如何熟悉并利用领域知识和计算机知识编写更高质量代码。这一篇也是从一个非常简单的编程问题开始,通过分析针对这个问题的不同实现方式,阐释学习一门语言都要学些什么以及怎么样才算熟悉了一门语言。

注:本文无意嘲讽《21天精通XXXX》系列,毕竟或许还是有人可以做到的,尤其是在现在这种有人只要用过就敢妄称精通的大环境下。本文只是想说明一些显而易见却又被人熟视无睹的事实。

一个简单的问题

不少人可能毕业之后就从来没写过哪怕排序之类的基本算法,这很正常,但是没人用不到各类Containers(Collections)。而且,但凡是代码写得足够多又不勤于复制粘贴的懒人,就少不得写些工具类把一些常用操作独立出来。比如这样一个函数:

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
}

我常常拿这个简单的函数当面试题,基本没有人猜不出来这个函数是要干什么,倒是会有个别人表示不知道前面的<T>是干什么用的。有性子急的可能很迅速地就构思出了如下实现,然后下一秒就发现坑在哪儿了。(简洁起见,本文所有代码略去参数为null之类的边界检查):

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    for (int index : indexes) {
        if (index < list.size())
            list.remove(index);
    }

    return list;
}

代码 1

显然上面的代码结果是不正确的。我们下面就来一步步地分析,看这个函数在Java里应该如何实现,都有哪些坑。主要意图是在这个过程体会,怎样才是充分地并合理地利用一个语言本身的理念与机制去解决问题。我也建议各位看官也先想一想自己心中的答案是什么再往下看。

先说需求到底是什么?

一说到“正确”,一说到“方案”,不少有经验的程序员的标准回答就是“看情况(It depends)”。看什么情况?看到底是要解决什么问题。我曾经也很喜欢这样回答问题,听上去多特么严谨。但是有时候这么说就不合适了,比如面试的时候这么回答就是犯傻,把到手的按自己能力方向展开并引导面试节奏的机会拱手还给了面试官。知道什么情况就说什么。没有具体上下文,要么自己假设一个;要么说自己的实现方式为了通用起见,所以牺牲了这些、这些、这些。即使不是面试,也不要说“看情况”,除非你真打算把情况一一列举出来并分情况讨论,你乐意说可能听的人也没耐心听,因为问问题的人一般只需要其中一个情况,你不嫌累,听者也会嫌烦。

回到问题上来。所以这个函数的需求是什么?需求就是函数签名所描述的那些。就像Array.Sort,它需要知道具体被使用的环境吗?它只要做到最好就是了。

函数签名能告诉你的,并不仅仅是行为,而且可以有实现细节。比如:

  1. 它是一个泛型函数:这大概是一个Util方法。
  2. 它返回一List<T>:所以它应该生成一个新的List<T>,意思应该是不要动参数List。
  3. 下标集合也是List:所以可能有重复,要处理。

等等。

正确性

代码1的问题是,它没有意识到删除了一个元素之后,后面的元素的下标就都变了,而且没有处理参数下标重复的问题。(还有别的问题后面再讨论)

于是一个简单的改进就可以同时解决上面的两个问题。

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    Collections.sort(indexes);
    for (int i = indexes.size() - 1; i >= 0; i++) {
        final int index = indexes.get(i);
        if (index < list.size())
            list.remove(index);
    }

    return list;
}

代码 2

这个没什么难的,所有人都可以做到这一步。遗憾的是不少人走到这一步就不再走了。因为它已经是正确的了(如果先不考虑对参数的改动)。我不知道是不是因为喝了Bert Lance那句“If it ain’t broke, don’t fix it.”毒鸡汤,并成功解释成了“如果它没坏,就不要改进它,不要重构它,不要动它!而且我也只能做到这里了!

正常情况下,如果并不需要复杂设计与编码就可以做到O(n)的函数,还是不要一开始就写成O(n^2)的好吧?代码写成这样,好意思在文件头上留下自己的名字么?(要不要加是另一回事儿。)

线性时间复杂度

在上面的代码基上,一个可以提高性能的改进是这样的:把要排除的元素标记成null。然后找出不是null的元素。

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    for (final int index : indexes) {
        list.set(index, null);
    }
    final List<T> result = new ArrayList<>();
    for (final T value  : list) {
        if (value != null)
            result.add(value);
    }

    return result;
}

代码 3

这个代码有两个问题:

  1. 性能还不是O(n)。
  2. 显然如果参数list里本来就有null就不行了。

问题1后面会展开讨论。对于问题2,理论上,可以用一个自己私有的对象实例代替null。

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    final T DELETE_MARKER = new T();    // Compile Error
    for (final int index : indexes) {
        list.set(index, DELETE_MARKER);
    }
    final List<T> result = new ArrayList<>(list.size());
    for (final T value  : list) {
        if (value != DELETE_MARKER)
            result.add(value);
    }

    return result;
}

代码 4

但是很可惜的是,由于Java的类型擦除机制,类似上面的方式在Java里是不可行的,因为T在运行时不存在。想知道T是什么?在Java里你得多传一个Class参数进来。而C#里上面的代码是可行的(当然需要额外泛型约束才能编译通过,但那不是重点,重点是C#可以知道T具体是什么)。

既然这种方式遇到了些障碍。我们就换一个思路:这个函数一共就俩参数,不for这个就只能for那个。(如果你解决问题真是这么个思路还是不要当程序员了。)

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    final List <T> result = new LinkedList<>();
    for (int i = 0; i < list.size(); i++) {
        if (!indexes.contains(i)) {
            result.add(list.get(i));
        }
    }

    return result;
}

代码 5

代码5的结果正确,但是性能又退化成O(log(n))或O(n^2)了。想想,为什么是有“或”?为什么有两种情况?

通用性(独立于参数实现)

请思考如下几个问题:

  1. list.contains的复杂度是多少?
  2. list.get的复杂度是多少?

List的某些操作的时间复杂度取决于其实现方式,甚至还会依赖于调用者的使用模式。对于JDK中常见的几个List实现,在本文的使用方式下,他们的理论上的时间复杂度会是这个样子的(有没有哪个跟算法书上说的不一样?请想想为什么):

ListOperations

图1

也就是说,代码5的时间复杂度会依赖于传入参数的类型。这显然不够理想。有没有办法让这个函数的运行效率无关参数类型呢?

问题1出在List的contains方法上,无论在哪种实现方式下,它都是O(n)复杂度的。好像无解啊?那有没有什么Container的contains方法是O(1)的?当然有啊:

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    final List <T> result = new LinkedList<>();
    final Set<Integer> indexesSet = new HashSet<>(indexes);
    for (int i = 0; i < list.size(); i++) {
        if (!indexesSet.contains(i)) {
            result.add(list.get(i));
        }
    }

    return result;
}

代码 6

问题2出在get操作上,LinkedList的get慢,但是ArrayList的get是O(1)的啊。所以心够宽的话,大不了可以先把整个list复制到一个新的ArrayList里不就结了?没错,但是那代码太美我不敢贴上来。那有没有别的方法呢?想一想现在的情形:我们无论如何是要遍历整个list,而且应该只需要遍历一遍。

这明明就是Iterator的地盘啊。所以用iterator就好了啊。

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    int index = -1;
    final Iterator<T> iterator = list.iterator();
    final Set<Integer> indexesSet = new HashSet<>(indexes);
    final List<T> result = new LinkedList<>();
    while (iterator.hasNext()) {
        final T item = iterator.next();
        index++;
        if (!indexesSet.contains(index))
            result.add(item);
    }

    return result;
}

代码 7

有经验的程序员其实一开始想的就是这个方法。这就是有经验的程序员和菜鸟的差距。到这一步,这个函数在功能上性能上都达到了预期的要求,而且做到了不依赖具体参数类型。面试的时候,如果有人能在15分钟内做到这一步,我就已经很高兴了。

但是,本文的重点要讲的,还没有开始。上面只是热身:熟悉问题本身。

正题才刚刚开始:那都是Java代码吗?

上面的确都是Java代码,因为它们都符合Java 8语言规范啊,能编译,能运行。但是不觉得有什么问题么?就这么简单的一个问题,怎么需要这么多代码呢?感觉什么地方不太对啊。

感觉不对是因为,这种代码,也不是Java,这是几乎所有OO编程语言及其框架的公共子集。它没有充分利用Java Collections Framework所提供的各类机制,上面的那些代码,放在C#里,放在Python里,放在C++里,仅仅需要修改一下语法和类名就可以同样地正确工作起来。如果学一种语言只是学到这门语言的这样的公共语言部分,其实就可以解决所有编程问题,不再学习任何新的语言点也能写出所有需要写的代码来,只是写起来就像上面一样——繁复。学一门语言,如果只是学到这种“公共子集”程度,的确是可以“一通百通”,信手拈来,几个小时学完。但是这离学会那门语言,还差得很远。

本文要实现的这个函数,大概算是最普通的编程问题了,它所涉及的,是几乎每个Java程序员天天都要使用到的东西。也就是JCF的那些接口,那些类。我说上面的代码没有充分利用Java,所以我们看看JCF的三个主要接口里都有些什么?请仔细看一遍下面两张图,有没有哪个函数名让你眼前一亮或是一头雾水的感觉呢?各位看官看这些方法的时候请思考下面几个问题:

  1. 了解这些API的用法,是否需要依赖工作上的项目提供特别的机会?
  2. 你觉得需要几年的工作经验才能让一个人知道并能在合适的时候正确地使用这些函数?
  3. 知道这些函数的使用,算熟悉Java?精通Java?还是没有直接关系?

JCFInterfaces

图 2

图中,绿色高亮的是Java 8新引入的接口。黄色高亮部分是辅助性函数,就是那种你完全不知道、不使用,也能无障碍地写出Java代码的函数。没高亮的函数,是必须要有的,也必然会用到的,也是那种每个人都不得不知道的,所谓的语言公共子集部分。当然,如果有人说他连remove方法都用不着,或是说从来只用iterator,我也并不觉得奇怪。

充分利用Java

我们看到List接口里有个比较特别的ListIterator或许不是所有人都知道。我们也来看看这个ListIterator和Iterator比有什么特别的地方。注意:ListIterator继承Iterator。

ListIterator

图3

所以稍微对Java多熟悉一些,就可以知道,从ListIterator是可以在遍历一个List的过程中知道当前index而不需要自己维护一个index变量的。于是我们的代码可以简化成:

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    final ListIterator<T> iterator = list.listIterator();
    final Set<Integer> indexesSet = new HashSet<>(indexes);
    final List<T> result = new LinkedList<>();
    while(iterator.hasNext()) {
        if (!indexesSet.contains(iterator.nextIndex())) {
            result.add(iterator.next());
        }
    }

    return result;
}

代码 8

如果用Java 8,那也可以通过新的removeIf来实现(想想这个函数线程安全吗?):

private static int index = -1;
public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    index = 0;
    final Set<Integer> indexesSet = new HashSet<>(indexes);
    final List<T> result = new LinkedList<>(list);
    result.removeIf(t -> !indexesSet.contains(index++));

    return result;
}

代码 9

如果喜欢用Stream呢,还可以写成这样:

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    final Set<Integer> indexesSet = new HashSet<>(indexes);

    return range(0, list.size())
            .filter(i -> !indexesSet.contains(i))
            .mapToObj(list::get)
            .collect(toList());
}

代码 10

然而不幸的是,这个代码又出性能问题了。因为它依赖了输入参数list的get方法。在前面的代码中,我们说过,总是可以把list先Copy到一个新的ArrayList中。但是如果传入参数本来就是ArrayList就是多余的了。所以要么就先检查一下参数类型是instanceof ArrayList不就结了?但是如果参数是个自定义的List呢?要不要先给参数做个Quick Perf测试来侦测其get方法是不是O(1)的再来决定要不要先Copy到ArrayList中呢?

在一个成熟的框架里写代码的一个好处是:你可以先假设你遇到的一切General的问题都已经有人遇到过了,而且很可能已经在框架层解决了。你只是得:

  1. 先意识到这个是General的问题。
  2. 形式化规范化这个问题。
  3. 然后用正确的姿势Google一下看看有没有人已经解决了。

比如代码10中的特定方法的性能问题,JDK已经意识到这个问题并且帮你解决了,有个专门的无方法接口叫RandomAccess用来标识一个List的get方法的时间复杂度是不是O(1)或比随机多次get快(详参文档)。那么代码中就可以用这个接口做为判断标准:

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    final Set<Integer> indexesSet = new HashSet<>(indexes);
    final IntStream indexesToSelect = range(0, list.size())
            .filter(i -> !indexesSet.contains(i));

    if (list instanceof RandomAccess) {
        return indexesToSelect.mapToObj(list::get)
                              .collect(toList());
    } else {
        final List<T> accessList = new ArrayList<>(list);
        return indexesToSelect.mapToObj(accessList::get)
                              .collect(toList());
    }
}

代码 11

当然,这个代码正确工作的前提是,那个自己实现了一个List接口的人,也知道正确地使用RandomAccess接口。

好了,代码8到代码11展示了如何充分使用Java框架来解决这个问题。但是不幸的是,有些代码变得更恶心了(脸好疼)。每种方式都有自己的优劣,应当在使用的时候根据实际需要选择合适的方案。

LinkedList vs ArrayList

以上我们分析过参数的具体类型会对函数性能产生的影响。但是还没有具体讨论过以上代码3至代码9中所创建的临时List对象的选择问题。有心的人可能已经发现,有的用的是ArrayList有的用的是LinkedList。那么用得对吗?更进一步,什么叫用对?

Java自带了这两个主要的List的实现。从图1中可以看出他们在性能上的差别。理论上,我们可以根据自己的使用方式,根据是get操作多还是add/remove操作多来决定是用LinkedList还是用ArrayList。这是我们以上分析的主要依据,如果你Google网上的类似问题,这也是大家的建议。

但是问题是,这个依据对吗?add/remove多的时候,用LinkedList就一定好吗?还有什么其它会影响性能的因素呢?

CPU缓存命中率

CPU缓存命中率主要取决于:所需要访问的数据的大小,在内存中的分布及最重要的访问模式。那么具体到这个函数的CPU缓存命中率,主要受List本身(不包括各个List项T本身)在内存中的分布的影响。请试着想象一下他们两者在内存中的分布情况。大体会如下两图所示。

ArrayList内存分配示意图:

ArrayListMemory

图 4

LinkedList内存分配示意图:

LinkedListMemory

图 5

所以最糟糕的情况会是什么样的呢?你每次访问的LinkedList中的一个Node都Miss CPU的所有一、二、三级缓存。当然实际一般不会这么糟糕,但是绝对比ArrayList要糟糕。缓存不命中的后果就是从内存中读取数据。从内存读又怎么了呢?我们得先看看CPU缓存的访问速度与内存访问速度的差距才能回答这个问题。

从下图可以看出各级缓存结构的访问延迟(Core i7):

AccessLatency

图 6

不难看出,根据问题规模的不同,内存访问会比CPU缓存慢3至50倍。那么这会对LinkedList的性能产生多大的影响呢?看访问延迟,估计有最大50倍性能差吧。不过性能上的事儿,必须要测试一下才知道。

在当前所实现的except函数的环境中,使用List的方式是创建一个默认大小的List,然后只增加不删除。我们就来模拟这个使用方式的下,不同List实现随着问题规模增长时性能的变化。结果如下图所示:

AppendBenchmark

图 7

从图中不难看出,在问题规模比较小(小于一两百万数据)的时候,LinkedList有些许优势,而当问题规模大于五百万数据之后,由于数据局部性不足及CPU缓存容量的限制,LinkedList的性能下降得非常快。(据图可以估计出测试平台的CPU L3缓存大小,不是Core i7)

所以简单起见,你可以在所有的情况下都使用ArrayList,而不用太担心其插入、删除的理论性能比较低的事儿,其数据的局部性可以把大O的系数拉到很低。如果你的所预见的使用情况都只有不到几万数据量的话,用LinkedList也是不错的。当然其实这么少的数据,随便你用什么都可以。

上面这个结论对所有语言都是成立的。如果想深入了解,可以参考《Number crunching: Why you should never, ever, EVER use linked-list in your code again》。Bjarne Stroustrup也在其讲座中表达过同样的观点

有人可能会问,那根据输入的大小选择合适的List实现不就结了吗?也行,就是代码会变得貌似一坨屎,而且还得根据CPU型号选取临界值。如果不想自己的母亲时不时被后来看代码的人问候,还得写注释解释清为什么这么做。另外,调用的人也会很不爽,他会面临这么个问题:这个函数有时候返回LinkedList有时候返回ArrayList。我想多数人会希望API的行为是下面几者之一:
  1. 一直返回一种实现。
  2. 参数是什么类型,也返回什么类型。
  3. 不依赖任何List实现,让调用者根据结果自行构建List。

这样这个API的行为才是可控的。

Java有两个List实现!太漂亮了!

这里想说些题外话,我们如果退一步想想,上面代码复杂度问题的根源,其实是Java本身造成的。它自带了两个List的实现,于是有心的Java程序员们在写代码的时候,无时无刻不在想着:我这回应该用哪个实现呢?但是写C#、写Python什么的,你完全不用考虑这个问题。因为它们都只自带了一种List。因为LinkedList实在是没什么存在的必要。大概唯一的好处就是强迫一部分过于懒惰Java程序员们动动脑子。在某人不小心用了LinkedList,搞出个大大的性能问题,经过简单的分析就可以知道他写的那个List处理函数是多么的糟糕:一个不小心就把一个O(n)的函数用出了O(n^2)的效果。自此LinkedList臭名昭著:性能杀手,效果拔群。于是JDK又引入了RandomAccess接口给这俩List擦屁股。说你们应该在写函数时候多多考虑一下非RandomAccess的List的感受嘛,你看我连接口都设计给你了,你不用?怪我喽?

如果对此有话题有兴趣,可以参看这个知乎问题下面的前五个回答。为什么那么多公司不用 .NET,而选择 PHP、JSP,是 .NET 有什么缺点吗?(这个问题虽然都没问Java,下面一群回Java的,呵呵)有个回答说的好:“.NET的问题就在于不能有效提高使用者的智商。”。Java不仅能,而且擅长。

想我写了快十年C#代码,其间几乎没有细想过List的实现是用数组更好还是用链表更好这个问题(毕竟也很少直接用List)。然而写Java的第一天我就意识到了。这个问题在Stackoverflow上很火。其中有一个排名不高的的回答有些碍眼。他说,LinkedList的作者Joshua Bloch(此人也是Effective JavaJava Concurrency in Practice两本书的作者),发过这样一条Twitter

Does anyone actually use LinkedList? I wrote it, and I never use it.

看这语气,说像是在说:“我写了个用于IQ测试的Java类,你们通过了吗?”

通过以上二节的分析,主要并不是想解释如何在LinkedList和ArrayList之间做取舍,而是想说明一个事实:这些分析里有计算机本身的约束,也有不少是Java语言本身的一些细节,而不同的语言里,针对同一个问题会有不同的设计,不同的细节。如果不了解这些细节,并不能用合理的方式使用这门语言。而这些才是学习语言的难点。(PHP充斥着各种细节,所以成了最好的语言。)

掌握一门语言的法门,只能靠深学活用。能通过一个下午熟悉的,只有语法而已。而语法本身,常常并不是一门语言最重要的部分。甚至连重要都算不上。

接口隔离原则

前面讨论了Java里两个List的现实之间的取舍问题。一个终级解决办法就是不做取舍,让调用方自己去从结果集构建List,如果他需要一个List的话。意思就是说,我们不要求参数是List,也不返回一个List。而只使用完成这个函数所必须的操作(同时不损失性能)。这就是最小接口依赖原则的含义。哪么哪些接口是我们为了实现这个函数所必须要使用的呢?其实就一个:遍历。于是我们的except函数可以被简化成这样。

public Iterable<T> except(Collection<T> list, Set<Integer> indexes) {
}

indexes的参数变成了Set,也更符合这个操作本身的要求。直接返回一个Iterable,可以让使用者按自己的要求和具体环境选择下一步所需要的具体数据类型。我们来考虑如何实现这个函数,虽然从语法上,直接返回一个List是合法的,但是显然已经不符合我们的目标。所以,在这个版本的实现中,真的需要返回一个纯粹的Iterable才能达到效果。(思考题:如果有个子类重写了这个函数并返回一个具体的List,是否算违反了里氏代换原则?)

public static <T> Iterable<T> except(Collection<T> list, Set<Integer> indexes) {
	final Iterator<T> iterator = list.iterator();
	final Set<Integer> validIndexes = indexes.stream().filter(i -> i < list.size() && i >= 0).collect(toSet());

	return () -> new Iterator<T>() {
		private int cursor = 0;

		@Override
		public boolean hasNext() {
			return cursor < list.size() - validIndexes.size();
		}

		@Override
		public T next() {
			while (validIndexes.remove(cursor))
				move();

			return move();
		}

		private T move() {
			cursor++;
			return iterator.next();
		}
	};
}

代码12

这还是用Java 8写的,都写了这么长,如果用老Java,代码将更长。解决长代码的方式也很简单,就是看看这个代码是不是承担了太多的责任。但是这么简单的操作,你说它承担了太多的责任,这不是搞笑么?但是它的确是的。它做的事情,至少可以分成这两步:

  1. 求indexes的补集。
  2. 按indexes选取元素。

于是这个操作可以被分解成这样:

public static <T> Iterable<T> except(Collection<T> list, Set<Integer> indexes) {
    return select(list.iterator(), 
              range(0, list.size()).filter(i ->
                      !indexes.contains(i)).iterator());
}

public static <T> Iterable<T> select(Iterator<T> list, Iterator<Integer> orderedIndexes) {
    return () -> new Iterator<T>() {
        private int cursor = 0;

        @Override
        public boolean hasNext() {
            assert list.hasNext();
            return orderedIndexes.hasNext();
        }

        @Override
        public T next() {
            while (cursor < orderedIndexes.next()) {
                cursor++;
                list.next();
            }

            return list.next();
        }
    };
}

代码 13

情况看上去更糟糕了-_-,但是这个新的select函数在通用性上显然比except要高得多,它也可以被except之外的其它的集合操作函数所使用。其它的集合操作函数,只是需要先通过纯粹的数学运算计算出要提取的元素的位置,然后最后调用select函数。

但是,即使这样,这个3行的except,跟它所需要解决的问题相比,也还是没必要地复杂了。

Iterable vs List

使用Iterable相比使用List,除了缩小了接口依赖之外,其实还有几个的不小的好处。

  1. 延迟求值。意思是这个函数本身运行时间变成了O(1)。
  2. 内存占用从O(n)减小到了O(1)。因为只返回了一个Iterable,而没有返回任何数据。

但是这些好处不是没有代价的。使用Iterable也会带来几个不小的问题。

  1. 隐式依赖参数列表。
  2. 不可重复使用。
  3. 非线程安全。
  4. 由于3,所以不可并行化。

第一点很明显,就当成思考题吧。第二点给个使用环境当引子。

private static <T> void printTwice(Iterable<T> items) {
    items.forEach(s -> System.out.println(s));
    items.forEach(s -> System.out.println(s));
}

代码12和代码13与之前的代码相比,在上面的使用方式下会具有不同的结果。而这个结果是编码者不想看到的。(C#里近似的接口IEnumerable,由于合理的接口设计,没有这个问题。)

可并行性

对于性能要求比较高的环境,可代码本身的并行性也会一个重要的代码可用性及质量的考量。如果用Java 8的流实现,并且实现成纯函数,好处之一就是可以比较简单地支持多线程并行计算。基于代码10,可以通过一个函数完成并行化。如代码14所示:

public static <T> Collection<T> except(List<T> list, Set<Integer> indexes) {
    return range(0, list.size())
                .parallel()
                .filter(i -> !indexes.contains(i))
                .mapToObj(list::get)
                .collect(toList());
}

代码 14

然而如果想把使用Iterator的代码并行化就没有那么轻松写意了。如果你有兴趣的话,可以写一个可并行化的Iterator试试。

Java vs .NET

写了12个版本的Java代码了,断断续续地花了好几天。代码越来越长,却始终找不到一个简洁、高效、灵活、可扩展的实现方式。想想就觉得火大。C#程序员可能早就憋不住了,这个问题的C#版实现方式不要太简洁。

public static IEnumerable<T> except<T>(IEnumerable<T> items, ISet<int> indexes)
{
    return items.Where((t, i) => !indexes.Contains(i));
}

看着这代码,顿时觉得写代码还是那么的美好,而且它具有一切好处:线性时间、延迟求值、参数无关、最小依赖等。写法也简单到我都不屑于提取出来一个函数。想想真心疼Java程序员们。不过或许这就是Java提高使用者智商的方式呢!再说了,我们都知道语言层面的东西都是不重要的。对吧?(这么想心里会舒服些,毕竟我也在写Java。)

如果你在写C#,可能不自觉地就免费地获得了不少的好处,这是一种幸福。但是这并不表示应该在写代码的时候可以无视上述的那些潜在问题。否则就成了Java程序员所鄙视的那种只会拖拖控件的码农界食物链末端生物。

.NET自动地为程序员们做了很多事情,而且做得很出色。但是做得太好,好到程序员代码写烂了它都能工作得还不错,结果不小心把不少.NET程序员都给惯傻了,傻到出点儿问题都不知道怎么下手处理,然后还反过来骂.NET是垃圾。而Java程序员从一上手写代码开始,就要开始解决这样那样的问题,水平慢慢地就被迫堆高了。其后果就是.NET始终被Java压制,这大概是微软始料未及的吧。

那些事儿

在引言里说过,这篇文章只是想说说那些显而易见的事儿。然而一千个人眼中有一千个哈姆雷特。所以我担心不说得清楚些,还是会有人不知道我在说在什么。本文的目的不是解释这个except函数在Java里怎么写也不是为了展示Java里多样的写法。本文要说的那些事是:

  1. 编程没有简单问题,再简单的问题都有多种解法适用于不同的环境。
  2. 学习一门语言从来不是一个简单的事儿。但是学习到这个语言的公共部分是个很简单的事儿(就像大牛们宣扬的,你基本功扎实的话,一两天的事儿)。
  3. 学习一门语言到公共部分就可以解决你工作上的所有问题,而且在这个层次,的确可以说用什么语言写代码都是无所谓的。(因为你总是可以自己搞定剩下的语言特定部分——大凡都通过重新造轮子的方式。)
  4. 深入学习一个语言,从来不是一个简单的事儿。(那怕简单如Java都是这样,我也没有深入学习过Java,我只是简单了解了一下JCF,然后看了点Best Practice而已。)
  5. 在你把一个语言学到一定深度之前,你可能会看到一些代码看不太懂。这个时候正确的积极的心态是承认自己的水平不够,而不是抱怨这个代码的可读性太差、搞得别人都看不懂。
  6. 最好等真精通了一门或几门语言之后再谈论什么一通百通,否则对于个人成长而言遗患无穷。(以Java为类,感觉对java.lang,java.util,java.io包里的所有最新的类的所有方法都了解并能合理使用才能算熟悉级别的吧。)
  7. 选择一门表达力强并且适用你个人理解力极限的编程语言,可以提高效率、节省时间、延长生命、早下班、赚更多的钱。(没最后两点大概没有人关心吧。)
  8. 公司不幸用了Java你也得适应。

参考书目

Cay S. Horstmann, Gary Cornell. Core Java 2, Volume II – Advanced Features (《Java2核心技术 卷II:高级特性》)

Richard Warburton. Java 8 Lambdas: Functional Programming for the Masses (《Java 8 函数式编程》)

Joshua Bloch. Effective Java Second Edition (《Effective Java中文版》)

Randal E. Bryant, David R. O’Hallaron. Computer Systems – A Programmer’s Perspective Third Edition (《深入理解计算机系统》)

Thomas H. Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms Second Edition(《算法导论》)

Donald E. Knuth. The Art of Computer Programming Vol 1: Fundamental Algorithms Third Edition (《计算机程序设计艺术 卷1:基本算法》)

从开平方说说写代码应该考虑的事儿

引言

很少有程序员需要自己写开平方函数,因为基本所有的语言都自带开平方的函数。更不用说1999年发布的SSE指令集,从CPU指令的级别上支持了开平方运算。当然这依然阻挡不住程序员们探索各种开平方方法的热情。其中最著名的当属John Carmack在开发Quake III时写的那段用精度换速度的Magic Code。如果你更关心如何提高开方函数的速度,你可以参考这篇比较各种方法速度文章,其中有些比单纯地使用CPU指令sqrtss开平方更快。

本文的关注点并不是速度,你甚至可以在本文中看到或许是业界最慢的一些方法。本文专注从软件工程领域的各各视角考量几种风格迥异的开平方函数,通过它们展示如何让代码的可重用度更高、使用上的灵活性更强、复杂度更低,以便于理解及维护。你总是可以在需要的时候,比较容易地提高一个具有高可维护性、设计良好的系统的性能。而一个系统一但由于代码质量上的问题,进入了一种难于理解、难于维护、难以变动、不可重用、无法预测运行结果的状态,如果再想提高其性能什么的,基本上就只能重写了。

导读

本文代码使用的语言是F#。但是你不必担心自己是否学过这个语言,当英语起来应该不会有什么问题。 本文中的示例与求解思路主要来自《Structure and Interpretation of Computer Programs 2nd Edition》,书中使用的是Scheme语言;类似地,那本书是某大学的计算机专门的入门教材,甚至不要求读者有编程经验。但是会需要微积分的基本知识,否则你应该只能搞懂第一个函数。

如果你很熟悉F#,那太好了,本文中的代码都是我一边看F#编程参考一边写的。如果有什么更好的实现方式,也希望你能指出来。

如果你根本不是计算机专业的,本文也值得一读,它或许能解释为什么你的那些计算机专业的同学们既不会修电脑修手机,也无法帮你找回被你遗忘的某网站的密码。因为下面这些才是他们所能解决的问题。

问题引出

求平方根运算的方法有很多,我们初中的时候就学习过手算开平方,还发过一个小册子,上面有各种数据表,用来直接查询一些数的平方根等。但是那些方面都不能方便才用于计算机:手算开平方规则较多,数据结构也复杂,代码量会很多;查表法需要过多的数据存储空间,也不切实际。

非计算机专业的人,很容易错估计算机领域问题的复杂度,一方面是因为人们总是喜欢这样做:先把问题在自己熟悉的领域重新定义,然后用自己在这个领域所熟悉的知识解决这个新问题,并声称原来的那个问题应该也具有同等的复杂度,并可以类似地解决掉。逻辑不好的人会很吃这套。

事实上,很多计算机专业人士在这方面也不惶多让。通常而言,在计算机领域,针对一个问题,找到一个可行的方案通常都是很简单的,并不需要什么高深的知识和精巧的构思。比如,如果你并没有高等数学的知识,仅仅用初、高中数学知识,你或许可以自己想出折半查找法求x的根,在[0,x)区间内以二分法搜索解,并得出像下面这样的代码:

open LanguagePrimitives

let inline abs x = if x > GenericZero then x else -x
let sqrt_v0 x = 
  let rec search f a b = 
    let close_enough target tolerance value =
      (abs (target - value)) < tolerance
    let avg = (a + b) / 2.0
    if a - b |> abs |> close_enough 0.0 0.001 then
      avg
    else
      match f avg with
      | v when v > 0.0 -> search f a avg
      | v when v < 0.0 -> search f avg b
      | v -> avg
  let half_interval_method f a b =
    let valueA = f a
    let valueB = f b
    match (valueA, valueB) with
    | (x, y) when x < 0.0 && y > 0.0 -> search f a b
    | (x, y) when x > 0.0 && y < 0.0 -> search f b a
    | (x, y) ->
      invalidArg "a" "f a must be of different sign with f b."
  half_interval_method (fun v -> v * v - x) 0.0 x

代码1

这个代码可行,结果也正确,只是有些小问题,比如:代码量多、速度慢、精度低。通常人们不把代码量当问题,因为它不能当作任何标准的度量;如果同时又对性能也没有什么过高要求的话,那么这段代码堪称完美。只是如果哪天需要改进其精度,会发现性能会随精度要求的提高而急剧下降。如果又想同时改进其性能,基本就只能整个重写一遍。这种半调子代码,几乎是所有软件项目的潘多拉魔盒,一但被打开,就会变得无法收拾。

问题的根源

写出高质量的代码,是每个软件工程师的职责,一个软件工程师的水平也可以通过其代码质量而得到体现。所以其实没有人会刻意地去写出像上面那样的半调子代码。出现这样的代码的原因,更多是非主观因素。比如相关知识储备不足、比如项目本身风格约束、比如工程进度的压迫等等。他们专注于问题本身,并尽自己所能写出了自己最满意的代码,却可能意识不到它其实是有多糟糕。这也是软件工程和土木工程的最显著不同:土木危楼,一目了然;软件危机,至死方现。

除了对计算机本身和软件工程本身的研究,多数软件工程项目都不仅仅需要软件方面的知识,更需要把软件工程知识与相关领域知识结合起来才能发挥其价值,这也是软件开发工作相比其它工作最特殊的地方之一。所以人们常说搞软件的要一直学习,这是没错的,因为在软件业,任何已经解决过的问题都不是问题,一方面是要学习如何解决这些问题,另一方面,如果想创造出些新的价值出来的话,势必要做一些别人没有想过、没有做过的事情。这些是题外话。

问题分析

求平方根函数,就是这种跨领域问题,解决起来总有两方面的基本工作要做:

  1. 熟悉领域知识。
  2. 找到这个问题在计算机领域的合适的解决方式。

开平方是一个数学问题,在着手设计并编写代码之前,从数学分析的角度深入而全面地了解一下这个问题是必不可少的。在这方面的工作都没有做充分的情况下,就会产生出类似上面的代码。

问题的解决大体如是:对问题本身有一个大局观,才能从中找到更合适的解决方案,同时也可以避免陷入自己的先入为主的知识体系的牛角尖而无法自拔。在这个阶段,有这样几个核心问题要回答:

  1. 问题所在领域的知识有哪些?
  2. 哪些知识可以更好地解决这个问题?
  3. 问题的环境(上下文)是怎么样的(问题没有普适的解法,所以需要针对具体环境)?

这些问题或许有些抽象而空洞,我们下面就开始一步步地求解开平方问题。最后这个函数写成什么样都不重要,重要的是我们如何走到那一步的,以及为什么要走那一步。

问题的求解

基本需求

回到问题上来。我们的目标是希望有一个函数,可以用来计算一个数的平方根,并需要满足以下的要求:

  • 时间复杂度在特定精度下为常量并稳定。
  • 可以灵活地调整所需要的精度。
  • 其他程序员能看得懂。

折半查找法并不符合前两个基本要求。所以它不是一个好的方法。

古巴比伦算法

我们只要简单地搜索一下就可以知道常见的开平方解法有哪些。而且不难发现有些方法在计算机系统上实现起来比折半法还要简单。比如公元前2000年,美索不达米亚人所使用的古巴比伦算法。而且不需要什么高深的数学知识,只是我们初高中没有学习过,不广为人知而已。

其计算过程很简单,如果我们猜g是x的一个根,那么\frac{g+\frac{x}{g}}{2}会是一个更好的根。用代码实现起来也很简单:

let square x = x * x
let sqrt_v1 x = 
  let rec sqrt_it guess =
    if (abs (square guess - x) / x) < 0.001 then
      guess
    else
      sqrt_it ((guess + x / guess) / 2.0)
  sqrt_it 1.0

代码2

代码2中我们把1.0当作所有数的平方根的初始猜测,然后迭代上面的算法直到误差小于0.001。这个函数基本满足前两个需求。只是没有背景知识的话,有些不太好看懂。对于一些对代码质量没有要求的环境,这个函数也已经完美了。

但是我们希望代码好读一些。而有心的人也会问,巴比伦人的算法的原理是什么。这些问题都还没有解决。

函数抽象

一个非常简单的提高代码可读性的手段是给你读不懂的部分起一个名字。

open LanguagePrimitives

let average x y = (x + y) / (GenericOne + GenericOne)
let close_enough target tolerance root = 
    (abs (target - root) / target) < tolerance 
let avg_damping f = fun x -> average x (f x) 
let sqrt_v2 x = 
  let getNext = avg_damping (fun v -> x / v)
  let rec sqrt_it guess =
    if square guess |> close_enough x 0.001 then
      guess
    else
      sqrt_it (getNext guess)
  sqrt_it 1.0

代码3

与前一个版本相比,这个函数其像仅仅是提取出了几个独立的小函数,给他们起了更明白的名字而已。有没有独立的函数,有没有名字都不是重点。每个语句都可以被提取成一个单独的函数,但是那样做一点意义都没有。重点是:哪些需要被提取出来,哪些不需要。引导你做出那些决定的策略才是重点。很多人不屑于做这种小函数的提取,尤其是在这些函数只有自己用的时候。但是有些有价值的东西,只有你这样做了之后才会发现。

比如上面的代码,经过整理之后,你就会发整个代码段中,与开平方运行有关的只有加粗的那个函数。这是一个非常强的信号,这个sqrt_v2函数的求解过程应该有着某种通用性。这个感觉没有错,那通用的部分就是求解方程的不动点。合理的函数提取就是过程抽象的手段,而提取之后又可以发现新的模式可以进一步抽象。过程抽象本身可以推进过程抽象。

于是那个通用的部分就又可以被提取出来了。于是开平方的代码本身就只剩一行了。它的含义就是:函数y=\frac{y+\frac{x}{y}}{2}的不动点,就是x的根。

let rec find_fix_point f guess = 
  let next = f guess
  if close_enough next guess 0.001 then
    next
  else
    find_fix_point f next

let sqrt_v3 x = 
  find_fix_point (fun v -> average v  (x / v)) 1.0

代码4

比较代码2、3、4,这三个版本的代码都源自古巴比伦算法。只是代码4具有更高的:

  • 可重用性:find_fix_point, avg_damping, close_enough都是通用方法。
  • 稳定性:基本可以在3次迭代内得到的一个很近似的解。
  • 可读性:代码量少,含义明确。

剩下的两个问题

根据我们之前提出的需求,代码4还存在两个主要的问题。

  • 可维护性比代码1低:因为依赖更多的领域知识,如果不知道古巴比伦算法,基本看不懂这个代码是怎么写出来的。
  • 其精度不可灵活控制:其内部使用了0.001来判断一个解是不是够好。但是显然对于计算\sqrt{0.0001}就不能正常工作了。

这两个问题是在我们选择古巴比伦法之前没有遇见到的。在软件开发的过程时常会出现类似这种状况:有些问题只有做出来甚至上线之后才会出现

这两个问题不是数学问题,而是纯粹编程实现上的问题。这也正是我们在分析领域问题时所需要注意的,如何把领域问题与计算机系统结合起来,并找到可能存在的问题及适合的解决方案的地方。

类似的,常见的计算机系统在数学领域的约束还有:

  1. 数值表示的精度。
  2. 数值表示的范围。
  3. 数值运算的截断误差。
  4. 不同数值运算间的速度差异。
  5. 数值求值策略对数学公式的敏感性。(等价的数学公示可能会有不同的运算结果。有些是数学本身的问题,有些有计算机系统约束的问题。)

我们下面继续分别解决这两个问题。但是不要忘了基于上面的话,它告诉我们:我们为解决这个两问题而引入的技术,很可能会带来新的问题。这是不可控的。只有做了才能发现。这是软件工程复杂性的另一个体现。《Principles of Computer System Design》一书对此进行了更详尽透彻的讨论。在此就不展开了。

牛顿法

当把一个函数化简到代码4的样子,我们不难又可以发现:如果我们不是要开平方,是要开立方。唯一需要改的地方很可能就是那个不动点方程。但是古巴比伦人没有给出开立方的迭代求解方法。即使有立方的,那任意次方的呢?更进一步地,有没有一个不动点方程可以求解任意一元多项式方程呢?牛顿说有:

假设a是对方程 f(x)=0的一个估算解,且f(x)可导,令:

b=a-\frac{f(a)}{f

那么b是个比a更好的近似解,其中f'(a)是 f(x) 的导函数 f'(x)在a点的值。

很少有编程语言能在语言层面支持求导运算。但是任何语言都可以根据导数的如下定义:

Dg(x)=\frac{g(x + dx) - g(x)}{dx}

实现出一个求取函数f导数值的函数:

let deriv f dx = fun x -> (f (x + dx) - f x) / dx

并得到一个使用牛顿法的开平方函数:

let newton_method f = 
  let Df = deriv f 0.001
  find_fix_point (fun x -> x - f x / Df x) 1.0

let sqrt_v4 x =
  newton_method (fun y -> y * y - x)

代码5

我们看到这个版本书使用的函数y=y * y - x就是解为x的方程本身。那么即使你不明白牛顿法的工作方式是什么,你大概也可以猜到求立方根的方法可以写成这样:

let cube_root x =
  newton_method (fun y -> y * y * y - x)

代码6

看上去,基本所有的可导函数的解都可以用牛顿法解。但是事情其实不会这么简单。但是对牛顿法的深入讨论不在本文的讨论范围内。如果有兴趣可以自行参看微积分相关书籍。

另外需要注意的是,在代码5中的Df函数中,又引入了一个新的精度假设值0.001。我们提高了代码的可读性和可扩展性,但是进一步损害了其精度(4次迭代之后在小数点第9位会体现出来)。之后会介绍可以解决这个问题的一个方案。

无限延迟求值流

对于精度问题,有一个看似十分简单且可行但是实际没有太大价值的解决方案:把精度当参数之一。它只是把同样的问题抛给了调用者而已。而对调用者而言,我相信他们更希望拿到一个解之后才能真正确定这个解够不够好,他们也无法预知对所有定义域都合理的精度是什么。当然,他们可以简单地选择一个绝对足够好的精度,比如7位。但是这样做的后果就在是一些并不需要这么好的精度的情况下产生了额外的无用运算。

考虑到开平方运算是迭代进行的,一个思路就是把迭代过程中的每个值都返回给调用者,并在调用者需要下一个更好的解的时候才进行下一步的计算,直到调用者满意为至。

当一个思路产生之后,无论你脑子里是否能立马闪现出具体实现方案,一个好的习惯就是在先计算机领域看看,有没有合适的技术与理念可以用来实现这个思路的,并和你自己的方案进行比较、甄选。然后再着手实现。思路的寻找往往是最难也是最有价值的部分。如果你总是想到什么就做什么,可能所有问题倒是也都可以解决,但是在这个过程中很难会有思路上、水平上的提升。把一年的工作经验用十年,就是这个意思。

了解到计算机系统中可以用来实现上面所述思路的概念至少有:

  1. 流(Stream – a view of system structure):具有的延时求值特性。
  2. 按名调用(Call by name – an evaluation strategy)
  3. 协程(Coroutine – a language feature)

Stream会更适合实现我们所需要的功能。它不依赖于语言,而且应用广泛。LINQ, Reactive Extensions都是基于Stream View设计的。

参考《SICP》上的流实现,不难构建出如下的Stream类和用之实现的Stream化的Sqrt函数:

type Stream<'a>(empty:bool, head:'a, tail:unit -> Stream<'a>) = 
  new(head:'a, tail:unit -> Stream<'a>) = Stream(false, head, tail)
  member this.Head = match empty with 
                      | false -> head
                      | true -> invalidOp "An empty stream has no head."
  member this.Tail = tail()
  member this.IsEmpty = empty
  member this.iterate action = 
    if not empty then 
      action this.Head; this.Tail.iterate action
  member this.iterateWhen action condition = 
    if not empty then
      action this.Head;
      if condition this.Head then
        this.Tail.iterateWhen action condition
  static member Empty = 
    Stream<'a>(true, Unchecked.defaultof<'a>, 
               fun unit -> invalidOp "An empty stream has no tail.")
  static member Map func (s:Stream<'a>) = 
    if not s.IsEmpty then 
      Stream(func(s.Head), fun () -> Stream.Map func s.Tail)
    else
      Stream.Empty
  static member Infinit producer head = 
    let rec stream = 
      fun () -> Stream(head, fun () -> stream() |> Stream.Map producer)
    stream()

let sqrt_stream x =
  let inline avg_damping f = fun x -> average x (f x)
  let getNext = avg_damping (fun v -> x * 1.0 / v)
  Stream.Infinit getNext 1.0

代码7

在这个版本的开平方函数中,没有任何精度设定,也就没有实现上的精确度损失。但是限于我目前的F#水平,我相信这个Stream的实现并不简洁,欢迎大家给出改进建议。(这遍文章里的F#代码大概占我写过的全部F#的50%,选F#只是因为我觉得照搬书上的Scheme代码和用我熟悉的语言解决这么简单的问题都很无聊。)

符号求导

在上面的牛顿法一节中,我们为了求解函数的导数而引入了一个新的精度假设值并导致了一定的精度损失。其根本原因是我们其实根本没有求解出导函数,而是利用了计算机强大的运算能力直接计算出指定点的导数值而已。

如果我们能把导函数方程先求解出来,并用这个导函数计算导数,就不会再有那个精度误差了。也就是说。我们希望能把方程f(x)=ax^2+bx+c当参数,并求解出f(x)=2ax+b这个导函数。

高级编程语言基本都自带表达式解析库。F#也不例外。所以符号化求导实现起来也并不复杂,至少不用自己写词法分析器。你当然可以自己写一个彰显实力,只是不太好读的代码多了也就不好管理了。但是需要避免的状况是:你自己写的一个,仅仅是因为你不知道语言里自带了个库,或是不屑于用。这种情况很常见,比如一个例子是:

let abs a = if a > 0 then a else -a

你看不出来问题在哪?那说的就是你。

在F#中实现符号求导,我们只需要把所需要用的如下求导法则

  • \frac{dc}{dx}=0
  • \frac{dx}{dx}=1
  • \frac{d(u+v)}{dx}=\frac{du}{dx}+\frac{dv}{dx}
  • \frac{d(uv)}{dx}=u(\frac{dv}{dx})+v(\frac{du}{dx})

代码化成一组模式匹配:

let inline sum     e1 e2 = <@@ (%%e1: float) + (%%e2: float) @@>
let inline sub     e1 e2 = <@@ (%%e1: float) - (%%e2: float) @@>
let inline product e1 e2 = <@@ (%%e1: float) * (%%e2: float) @@>

let rec deriv (body:Expr) (p:Var) =
    match body with 
    | Var(x) ->
        if x = p then <@@ 1.0 @@> else <@@ 0.0 @@>
    | ValueWithName(x) ->
        <@@ 0.0 @@>
    | SpecificCall <@ (+) @> (_, _, [lArg;rArg]) ->
        sum (deriv lArg p) (deriv rArg p)
    | SpecificCall <@ (-) @> (_, _, [lArg;rArg]) ->
        sub (deriv lArg p) (deriv rArg p)
    | SpecificCall <@ (*) @> (_, _, [lArg;rArg]) -> 
        let pl = product lArg (deriv rArg p)
        let pr = product rArg (deriv lArg p)
        sum pl pr
    | _ -> invalidArg "body" ("Invalid body: " + body.ToString())

let derivE (exp:Expr) = 
    let (var, body) =
        match exp with 
        | Lambda(var, body) -> (var, body)
        | _ -> invalidArg "exp" ("Invalid exp: " + exp.ToString())
    let derivBody = deriv body var
    Expr.Lambda(var, derivBody)

let sqrt_v5 (y: float) = 
 let exp = <@ fun x -> x * x - y @>
 let f  = exp |>           EvaluateQuotation :?> ( float -> float )
 let Df = exp |> derivE |> EvaluateQuotation :?> ( float -> float )
 find_fix_point (fun x -> x - f x / Df x) 1.0

代码8

现实的项目中没有人会用符号求导技术来写个开平方函数。因为它比前面的版本要慢上1000倍。但是符号求导所带来的灵活性使得这个框架可以用来解决比开平方复杂得多的问题。

这个版本的代码没有使用流,如果需要,可以把它也实现成一个流。在软件工程领域,不同技术方案基本都可以合并而生成一个新的方式。而在非软件工程领域,这种合并常常会由于物理法则的约束而无法达成。这是软件工程复杂性的又一个体现。

综述

本文的主要意图是阐释,充实自身业务领域知识与计算机领域知识对于编写高质量代码的必要性,使用合适的方案解决一个问题能带来多方面的好处。这似乎是一句废话,但是其实这只是一个认识陷阱:人们,尤其是经验越丰富的人,一但认为自己理解了什么,或是利用起了他们的既往经验,他们就常常停止了探索,停止了学习,停止了思考。这对于软件开发是非常有害的。

但是另一方面,如上的发现问题、解决问题、发现新问题的循环是没有尽头的。具有钻研精神的程序员们总能在代码中发现问题并用各种方式尝试解决它,同时引入新的问题。专业的软件工程师能够根据最终目标和环境的不同知道应该往哪个方向走,并且到站了也知道停下来。在一个仅仅需要开平方的地方引入符号求导机制同样有害。

本文中的例子和解决问题的过程纯粹为阐释上述意图而刻意设定,请勿作编程指导,如果你能从中发现自己坠入的认识陷阱就再好不过了。

参考书目

Jerome H.Saltzer, M. Frans Kaashoek. Priciples of Computer System Design (《计算机系统设计原理》)

Harold Abelson, Gerald Jay Sussman, Julie Sussman. Structure and Interpretation of Computer Programs 2nd Edition (《计算机程序的构造和解释》)

Tomas Petricek, Jon Skeet. Real-world Functional Programming – With Examples in F# and C# (《C#与F#编程实践》)

Adrian Banner. The Calculus Lifesaver – All the tools you need to excel at Calculus (普林斯顿微积分读本)

Gerald M.Weinberg. The Psychology of Computer Programming (《程序开发心理学》)

谷强强 版权所有