转换和优化

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

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

this.number = number;
}

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

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

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

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

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

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

this.number = number;
return this;
}

public static PrimeNumber getPrime(int number) {
}

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

public Set<Integer> getFactors() {
Set<Integer> factors = new HashSet<Integer>();
for (int i = 2; i < sqrt(number) + 1; i++)
if (isFactor(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;
}

}```

优化的函数式 Java

清单 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() {
}```

清单 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 java.lang.Math.round;

import static java.lang.Math.sqrt;

private int candidate;
private Map<Integer, Integer> cache;

this.candidate = value;
return this;
}

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 {
cache.put(candidate, sum);
return sum;
}
}

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

优化的 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})
}```

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

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
}
}```

优化的 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)(_ + _)```

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

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
}```

优化的 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)))```

清单 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 版本中一样，这就使得第二种优化非常易于实现。

结束语

相关主题

• 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