内容

函数式思维

转换和优化

各种语言的更多功能比较

Neal Ford
Neal Ford
2012 年 12 月 11 日发布

系列内容：

此内容是该系列 # 部分中的第 # 部分： 函数式思维

https://www.ibm.com/developerworks/cn/views/global/libraryview.jsp?series_title_by=函数式思维
敬请期待该系列的后续内容。

此内容是该系列的一部分：函数式思维

敬请期待该系列的后续内容。

关于本系列

本系列的目标是重新调整您对函数式思维的认识，帮助您以全新的方式思考常见问题，并寻找提升您的日常编码能力的方法。本系列文章将探讨函数编程概念、允许在 Java 语言中进行函数编程的框架、在 JVM 上运行的函数编程语言，以及语言设计的未来方向。本系列面向那些了解 Java 及其抽象工作原理，但对函数式语言不甚了解的开发人员。

函数式编程起源于数学和计算机科学，这两种科学对术语都各执一词。语言和框架设计师们开发了他们最喜欢的命名法，结果发现基础范式已经有名称了。由于术语存在不一致性而使得了解函数式编程范式变得不容易。

在 “大量转换” 中，我提出了对质数进行分类的问题，并且跨各种函数式语言就 JVM 和两种函数式 Java 框架实现了一种解决方案。本期文章继续探讨上一期的主题，通过两种方式优化了上一期的算法，展示了各种语言中的后续更改。本期文章和上一期文章同样阐述了各种工具和语言中术语与特性可用性之间的区别。具体来讲，我练习了这些示例中的 map、filter 和 memoize。

使用纯 Java 语言优化的质数分类法

所陈述的问题是确定一个数是否是质数，一个质数的因子只包括 1 和它本身。在解决该问题的多种算法中，我选择了阐述函数式编程领域的过滤 和映射。

在上一期中，我对确定一个数的因子的算法采取了一种朴素法，选择了简单代码而不是最佳执行代码。在本期中，我使用几种不同的函数式概念优化了这种算法，此外，我还优化了用例的每个版本，类在该用例中调用了多次以便对同一个数进行分类。

我的用于确定质数的原始 Java 代码如清单 1 所示：

清单 1. 质数分类器的原始 Java 版本
public class PrimeNumberClassifier {
    private Integer number;

    public PrimeNumberClassifier(int number) {
        this.number = number;
    }

    public boolean isFactor(int potential) {
        return number % potential == 0;
    }

    public Set<Integer> getFactors() {
        Set<Integer> factors = new HashSet<Integer>();
        factors.add(1);
        factors.add(number);
        for (Integer i = 2; i < number; i++)
            if (isFactor(i))
                factors.add(i);
        return factors;
    }

    public int sumFactors() {
        int sum = 0;
        for (int i : getFactors())
            sum += i;
        return sum;
    }

    public boolean isPrime() {
        return sumFactors() == number + 1;
    }
}

在 清单 1 中，getFactors() 方法迭代了从 2 到正在分类数字的潜在因子，但效率很低。考虑到因子总是成对存在的，这就意味着当我发现一个因子时，只需进行简单的除法即可发现该因子的配对因子。因此，我并不需要一直对该数字进行迭代；相反，我可以迭代到该数字的平方根，即可获得成对的因子。优化的 getFactors() 方法出现在如清单 2 所示的整体优化版本中：

清单 2. 优化的纯 Java 版本
public class PrimeNumber {
    private Integer number;
    private Map<Integer, Integer> cache;

    public PrimeNumber() {
        cache = new HashMap<Integer, Integer>();
    }

    public PrimeNumber setCandidate(Integer number) {
        this.number = number;
        return this;
    }

    public static PrimeNumber getPrime(int number) {
        return new PrimeNumber().setCandidate(number);
    }

    public boolean isFactor(int potential) {
        return number % potential == 0;
    }

    public Set<Integer> getFactors() {
        Set<Integer> factors = new HashSet<Integer>();
        factors.add(1);
        factors.add(number);
        for (int i = 2; i < sqrt(number) + 1; i++)
            if (isFactor(i)) {
                factors.add(i);
                factors.add(number / i);
            }
        return factors;
    }

    public int sumFactors() {
        int sum = 0;
        if (cache.containsValue(number))
            sum = cache.get(number);
        else
            for (int i : getFactors())
                sum += i;
        return sum;
    }

    public boolean isPrime() {
        return number == 2 || sumFactors() == number + 1;
    }

}

在 清单 2 所示的 getFactors() 方法中，我对从 2 到该数的平方根（加上 1，以便处理舍入错误）进行了迭代，并获得了成对的因子。在该代码中返回一个 Set 很重要，因为边界情况涉及到完全平方数。比方说数字 16，它的平方根是 4。在 getFactors() 方法中，使用 List 代替 Set 将会造成在列表中复制 4 次。执行单元测试是为了查找像这样的边界情况！

清单 2 中的另一项优化涉及到多个调用。如果该代码的主要用途是对同一数字做多次判断，以确定它是否是质数，那么 清单 1 中的 sumFactors() 方法执行的计算就是无效的。相反，在 清单 2 中的 sumFactors() 方法中，我创建了一个类范围的缓存来保存之前计算的值。

要实现第二种优化，需要进行有点不太确定的类设计，以便使其呈现出状态，从而使实例可以充当缓存的所有者。这样做可能会有所改进，但改进部分在后续的示例中微不足道，所以我不会在此花费太多精力。

优化的函数式 Java

函数式 Java（参见 参考资料）是一种向 Java 添加函数式特性的框架。优化影响到的两种方法是 getFactors() 和 sumFactors() 方法，这两种方法的原始（未优化）版本如清单 3 所示：

清单 3. 原始函数式 Java getFactors() 和 sumFactors() 方法
public List<Integer> getFactors() {
    return range(1, number + 1)
            .filter(new F<Integer, Boolean>() {
                public Boolean f(final Integer i) {
                    return isFactor(i);
                }
            });
}

public int sumFactors() {
    return getFactors().foldLeft(fj.function.Integers.add, 0);
}

清单 3 中的 getFactors() 方法使用 isFilter() 方法过滤掉了从 1 到目标数字加上 1 的数字范围（因为没有包括函数式 Java 中的 ranges），进而确定内含项。函数式 Java 质数分类器的优化版本如清单 4 所示：

清单 4. 函数式 Java 的优化版本
import fj.F;
import fj.data.List;
import java.util.HashMap;
import java.util.Map;
import static fj.data.List.range;
import static fj.function.Integers.add;
import static java.lang.Math.round;

import static java.lang.Math.sqrt;

public class FjPrimeNumber {
    private int candidate;
    private Map<Integer, Integer> cache;

    public FjPrimeNumber setCandidate(int value) {
        this.candidate = value;
        return this;
    }

    public FjPrimeNumber(int candidate) {
        this.candidate = candidate;
        cache = new HashMap<Integer, Integer>();
    }

    public boolean isFactor(int potential) {
        return candidate % potential == 0;
    }

    public List<Integer> getFactors() {
        final List<Integer> lowerFactors = range(1, (int) round(sqrt(candidate) + 1))
                .filter(new F<Integer, Boolean>() {
                    public Boolean f(final Integer i) {
                        return isFactor(i);
                    }
                });
        return lowerFactors.append(lowerFactors.map(new F<Integer, Integer>() {
            public Integer f(final Integer i) {
                return candidate / i;
            }
        }))
        .nub();
    }

    public int sumFactors() {

        if (cache.containsKey(candidate))
            return cache.get(candidate);
        else {
            int sum = getFactors().foldLeft(add, 0);
            cache.put(candidate, sum);
            return sum;
        }
    }

    public boolean isPrime() {
        return candidate == 2 || sumFactors() == candidate + 1;
    }
}

在 清单 4 中的 getFactors() 方法中，我比较有选择性地使用了相同的 range() 和 filter() 方法。第一个范围获得了高达平方根的因子，使用的是如 清单 3 所示的 filter() 方法。该方法的第二行使用函数式 Java 中的 map() 方法生成了高于平方根的因子。map() 方法将函数应用到集合中的每个元素中，并返回了一个已转换的集合。将这个高于平方根的因子列表附加到低于平方根 (lowerFactors) 的因子中。对函数式 Java 的 nub() 方法的上一个方法调用将列表转换为一个集，从而缓解了完全平方的复制问题。

清单 4 中的 sumFactors() 优化使用了一种与 清单 2 中纯 Java 版本同样的缓存，意味着与该版本中一样对类具有相同的需求。

优化的 Groovy

getFactors() 和 sumFactors() 方法中原始的 Groovy 版本如清单 5 所示：

清单 5. 原始的 Groovy getFactors() 和 sumFactors() 方法
public def getFactors() {
  (1..number).findAll { isFactor(it) }.toSet()
}

public def sumFactors() {
  getFactors().inject(0, {i, j -> i + j})
}

在 Groovy 中，findAll() 方法过滤了数字范围，而 sumFactors() 方法使用了 Groovy 的 inject() 方法，将代码块应用到每个元素中，以便将列表减少为一个元素（这个元素将会是总数，因为代码块将每一对总结为归约运算）。质数分类器的 Groovy 优化版本如清单 6 所示：

清单 6. 优化的 Groovy 版本
import static java.lang.Math.sqrt

class PrimeNumber {
  static def isFactor(potential, number) {
    number % potential == 0;
  }

  static def factors = { number ->
    def factors = (1..sqrt(number)).findAll { isFactor(it, number) }
    factors.addAll factors.collect { (int) number / it}
    factors.toSet()
  }

  static def getFactors = factors.memoize();

  static def sumFactors(number) {
    getFactors(number).inject(0, {i, j -> i + j})
  }

  static def isPrime(number) {
    number == 2 || sumFactors(number) == number + 1
  }
}

正如在函数式 Java 版本中一样，清单 6 中的 factors() 方法使用平方根对因子进行了分区，并通过 toSet() 方法将结果列表转换成一个集。函数式 Java 和 Groovy 之间的主要差别是术语差别；在函数式 Java 中，filter() 和 foldLeft() 方法分别是 Groovy 的 findAll() 和 inject() 的同义词。

清单 6 中的优化解决方案与之前的 Java 版本完全不同。我并没有向类中添加状态性，而是使用 Groovy 的 memoize() 方法。清单 6 中的 factors 方法是一种纯函数，这就意味着它除了自身的参数外，不依赖任何状态。一旦需求得到满足，Groovy 运行时就可以通过 memoize() 方法自动缓存值，memoize() 方法返回一个名为 getFactors() 的缓存版本的 factors() 方法。这就是函数式编程降低开发人员必须维持的机制（比如缓存）数量的一个极好的示例。在本系列的 “函数式设计模式，第 1 部分” 这一期中，我详细介绍了内存化 (memoization)。

优化的 Scala

getFactors() 和 sumFactors() 方法的原始 Scala 版本如清单 7 所示：

清单 7. 原始的 Scala factors() 和 sum() 方法
def factors(number: Int) =
  (1 to number) filter (isFactor(number, _))

def sum(factors: Seq[Int]) =
 factors.foldLeft(0)(_ + _)

清单 7 中的代码对那些名称不太重要的参数使用了便捷的 _ 占位符。质数分类器的优化版本如清单 8 所示：

清单 8. 优化的 Scala 版本
import scala.math.sqrt;

object PrimeNumber {
  def isFactor(number: Int, potentialFactor: Int) =
    number % potentialFactor == 0

  def factors(number: Int) = {
    val lowerFactors = (1 to sqrt(number).toInt) filter (isFactor(number, _))
    val upperFactors = lowerFactors.map(number / _)
    lowerFactors.union(upperFactors)
  }

  def memoize[A, B](f: A => B) = new (A => B) {
    val cache = scala.collection.mutable.Map[A, B]()
    def apply(x: A): B = cache.getOrElseUpdate(x, f(x))
  }

  def getFactors = memoize(factors)

  def sum(factors: Seq[Int]) =
    factors.foldLeft(0)(_ + _)

  def isPrime(number: Int) =
    number == 2 || sum(getFactors(number)) == number + 1
}

优化的 factors() 方法使用了与前面示例相同的技术（比如在 清单 3 中），该方法适用于 Scala 的语法，并生成一种直观的实现。

尽管未来可能会添加 Scala，但它不具有标准内存化设置。Scala 可通过多种方式实现；简单的实现依赖于 Scala 内置的可变映射和其便利的 getOrElseUpdate() 方法。

优化的 Clojure

factors 和 sum-factors 方法的 Clojure 版本如清单 9 所示：

清单 9. 原始的 factors 和 sum-factors 方法
(defn factors [n]
  (filter #(factor? n %) (range 1 (+ n 1))))

(defn sum-factors [n]
  (reduce + (factors n)))

就像在其他预先优化的版本中一样，原始的 Clojure 代码过滤了从 1 到数字加上 1 的数字范围，并使用了 Clojure 的 reduce 函数来将 + 函数应用到每一个元素中，最后生成总数。优化的 Clojure 质数过滤器如清单 10 所示：

清单 10. 优化的 Clojure 版本
(ns primes)

(defn factor? [n, potential]
  (zero? (rem n potential)))

(defn factors [n]
  (let [factors-below-sqrt (filter #(factor? n %) (range 1 (inc (Math/sqrt n))))
        factors-above-sqrt (map #(/ n %) factors-below-sqrt)]
    (flatten (conj factors-below-sqrt factors-above-sqrt))))

(def get-factors (memoize factors))

(defn sum-factors [n]
  (reduce + (get-factors n)))

(defn prime? [n]
  (or (= n 2) (= (inc n) (sum-factors n))))

factors 方法使用了与前面的示例（如 清单 3）中相同的优化算法，通过过滤从 1 到平方根加 1 的范围，得出了低于平方根的因子：(filter #(factor? n %) (range 1 (inc (Math/sqrt n))))。Clojure 版本对未命名的参数使用了自己的符号 (%)，就像 清单 8 中的 Scala 版本一样。#(/ n %) 语法创建了一个匿名函数，就像用于 (fn [x] (/ n x)) 的语法速记法一样。

Clojure 包含通过 memoize 函数内存化纯函数的能力，就像在 Groovy 版本中一样，这就使得第二种优化非常易于实现。

结束语

与上一期一样，在本期中我阐述了类似的概念为何可以在各种语言、框架以及内置功能中变成不同的名称。一说到函数命名，Groovy 就是一种奇怪的语言（例如，使用 findAll() 而不是更普遍的 filter()，使用 collect() 而不是 map()）。内存化的出现能够极大地有助于轻松安全地实现缓存。

在下一期中，我将详细探讨各种语言和函数式框架中的 “惰性”。

相关主题

  • The Productive Programmer（Neal Ford，O'Reilly Media，2008 年）：Neal Ford 撰写的一本书籍，讨论了能够帮助您提高编码效率的工具和实践。
  • Scala：Scala 是运行在 JVM 上的一种现代函数式语言。
  • Clojure：Clojure 是运行在 JVM 上的一种现代函数式 Lisp。
  • Functional Java：Functional Java 是一种给 Java 添加了大量函数式语言构造的框架。
  • Practically Groovy：在 developerWorks 的系列文章中探讨 Groovy 的函数式（和其他）特性。
  • “Execution in the Kingdom of Nouns”（Steve Yegge，2006 年 3 月）：有关 Java 语言设计某些方面的一次有趣的演讲。
  • developerWorks Java 技术专区：查找有关 Java 编程的方方面面的数百篇文章。
  • 下载 IBM 产品评估版 或 在线试用 IBM SOA Sandbox，并开始使用来自 DB2®、Lotus®、Rational®、Tivoli® 和 WebSphere® 的应用程序开发工具和中间件产品。
static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Java technology
ArticleID=851094
ArticleTitle=函数式思维: 转换和优化
publish-date=12112012