关于本系列
本系列旨在将您的观点重新定位为实用的心态，帮助您以新的方式看待常见问题并找到改善日常编码的方式。 它探讨了函数式编程的概念，允许在Java语言中进行函数式编程的框架，在JVM上运行的函数式编程语言以及语言设计的一些未来方向。 该系列面向那些了解Java及其抽象如何工作，但很少或没有使用功能语言经验的开发人员。
函数式编程起源于数学和计算机科学，两者都对术语有很强的见解。 语言和框架设计人员开发了自己喜欢的术语，只是发现基础范例已经有了名称。 由于术语的不一致，学习函数式编程范例非常困难。
在“ 大量转换 ”中，我解决了质数分类问题，并在JVM和两种功能性Java框架上的几种功能性语言中实现了解决方案。 继续该主题，本期文章以两种方式优化了先前的算法，显示了跨语言的后续更改。 与上一期一样，本期文章说明了工具和语言之间术语和功能可用性的差异。 特别是，我为这些示例练习map ， filter和memoize 。
在纯Java中优化了素数分类
陈述的问题是确定一个数是否是质数 ，一个仅因数为1的素数本身。 在解决该问题的几种算法中，我选择了在函数式编程领域中说明过滤和映射 。
在上一期中，我对算法采用了一种幼稚的方法来确定数字的因素，而是选择简单的代码而不是最佳地执行代码。 在本期中，我将使用几种不同的功能概念来优化该算法。 另外，我针对用例被多次调用以对相同编号进行分类的用例优化了每个版本。
清单1显示了我用于确定质数的原始Java代码：
清单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将在列表中生成重复的4s。 存在单元测试来找到这样的极端情况！
清单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);
}
所述getFactors()在方法清单3层的过滤器号码的范围从1到目标数加1（因为range使用在功能的Java s为noninclusive） isFilter()方法来确定的包括。 清单4中显示了Functional Java质数分类器的优化版本：
清单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()方法来收集因子直至平方根。 该方法的第二行使用Functional Java中的map()方法生成平方根上方的因子。 map()方法将函数应用于集合中的每个元素，并返回转换后的集合。 平方根上方的因子列表被追加到平方根下方的因子（ lowerFactors ） lowerFactors 。 对Functional Java的nub()方法的最后一个方法调用将列表转换为集合，从而减轻了完美平方重复的问题。
清单4中的sumFactors()优化使用了与清单2中的纯Java版本相同的高速缓存，这意味着对该类的有状态性要求与该版本相同。
优化的Groovy
清单5中显示了getFactors()和sumFactors()方法的原始Groovy版本：
清单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()方法，将代码块应用于每个元素，以将列表缩减为一个元素（即和，因为代码块将每一对相加，作为归约运算）。 清单6显示了质数分类器的优化Groovy版本：
清单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
}
}
就像在Functional Java版本中一样， 清单6中的factors()方法使用平方根对因子进行分区，并通过toSet()方法将结果列表转换为集合。 主要的区别是Functional Java和Groovy之间的术语差异。 在Functional Java中， filter()和foldLeft()方法分别是Groovy的findAll()和inject()同义词。
清单6中的优化解决方案与以前的Java版本完全不同。 我没有使用类的有状态性，而是使用Groovy的memoize()方法。 清单6中的factors方法是一个纯函数 ，意味着它除参数外不依赖任何状态。 一旦满足该要求，Groovy运行时就可以通过memoize()方法自动缓存值，该方法返回名为getFactors()的factors()方法的缓存版本。 这是函数式编程减少开发人员必须维护的机制（例如缓存）数量的能力的一个很好的例子。 我将在本系列的“ 功能设计模式，第1部分 ”中更全面地介绍备忘录。
优化的Scala
清单7中显示了getFactors()和sumFactors()方法的原始Scala版本：
清单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的内置可变映射及其方便的getOrElseUpdate()方法。
优化的Clojure
清单9中显示了factors和sum-factors方法的Clojure版本：
清单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函数将+函数应用于每个元素，从而得出总和。 清单10中显示了优化的Clojure质数分类器：
清单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)]
(concat 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)))) ： (filter #(factor? n %) (range 1 (inc (Math/sqrt n)))) 。 Clojure版本将其自己的符号（ % ）用于未命名的参数，例如清单8中的Scala版本。 #(/ n %)语法创建一个匿名函数，作为(fn [x] (/ nx))语法糖简写。
与Groovy版本一样，Clojure包括通过memoize功能来记住纯函数的功能，从而使第二个优化的实现变得微不足道。
结论
在上一期的上一部分中，我说明了相似的概念如何在各种语言和框架以及内置功能之间增长了不同的名称。 在函数命名方面，Groovy是一种奇怪的语言（例如，使用findAll()而不是更常见的filter()和collect()而不是map() ）。 备注的存在对于实现缓存的简便性和安全性有很大的不同。
在下一部分中，我将在各种语言和功能框架中更全面地探索惰性。
翻译自: https://www.ibm.com/developerworks/java/library/j-ft17/index.html
