我能做些什么来加快此代码的速度？编辑
我正在尝试学习Java，Scala和Clojure。
我正在用这三种语言解决欧拉项目问题。下面列出的是问题 #5 （http://projecteuler.net/problem=5） 的代码，以及到目前为止前五个问题的运行时间（以秒为单位）。令我吃惊的是，Java和Clojure版本比Scala版本慢得多。它们在同一台机器上运行，相同的jvm，并且在多次试验中结果是一致的。我能做些什么来加快两者的速度（尤其是Clojure版本）？为什么Scala版本要快得多？
运行时间（以秒为单位）
|---------|--------|--------|----------|
| problem | Java | Scala | Clojure |
|=========|========|========|==========|
| 1 | .0010 | .1570 | .0116 |
| 2 | .0120 | .0030 | .0003 |
| 3 | .0530 | .0200 | .1511 |
| 4 | .2120 | .2600 | .8387 |
| 5 | 3.9680 | .3020 | 33.8574 |
Java 版本的问题 #5
public class Problem005 {
private static ArrayList<Integer> divisors;
private static void initializeDivisors(int ceiling) {
divisors = new ArrayList<Integer>();
for (Integer i = 1; i <= ceiling; i++)
divisors.add(i);
}
private static boolean isDivisibleByAll(int n) {
for (int divisor : divisors)
if (n % divisor != 0)
return false;
return true;
}
public static int findSmallestMultiple (int ceiling) {
initializeDivisors(ceiling);
int number = 1;
while (!isDivisibleByAll(number))
number++;
return number;
}
}
Scala 版本的问题 #5
object Problem005 {
private def isDivisibleByAll(n: Int, top: Int): Boolean =
(1 to top).forall(n % _ == 0)
def findSmallestMultiple(ceiling: Int): Int = {
def iter(n: Int): Int = if (isDivisibleByAll(n, ceiling)) n else iter(n+1)
iter(1)
}
}
问题#5的克洛尤尔·弗森
(defn smallest-multiple-of-1-to-n
[n]
(loop [divisors (range 2 (inc n))
i n]
(if (every? #(= 0 (mod i %)) divisors)
i
(recur divisors (inc i)))))
编辑
有人建议我将各种答案汇编成我自己的答案。但是，我想在应得的信用处给予信用（我自己真的没有回答这个问题）。
至于第一个问题，所有三个版本都可以通过使用更好的算法来加速。具体来说，创建数字 1-20（2^4、3^2、5^1、7^1、11^1、13^1、17^1、19^1）的最大公共因子的列表，并将它们相乘。
更有趣的方面是使用本质上相同的算法来理解三种语言之间的差异。在某些情况下，像这样的蛮力算法可能会有所帮助。那么，为什么会出现性能差异呢？
对于Java，一个建议是将ArrayList更改为int的原始数组。这确实减少了运行时间，减少了大约0.5-1秒（我今天早上刚刚运行它，它将运行时间从4.386秒减少到3.577秒。这减少了一点，但没有人能够想出一种方法将其降低到半秒以下（类似于Scala版本）。考虑到这三者都编译为java字节码，这是令人惊讶的。@didierc建议使用不可变迭代器;我测试了这个建议，它将运行时间增加到5秒以上。
对于Clojure，@mikera和@Webb给出一些建议来加快速度。他们建议使用循环/recur进行两个循环变量的快速迭代，使用未经检查的数学运算稍微快一些（因为我们知道这里没有溢出的危险），使用原始长整线而不是盒装数字，并避免像每个函数一样高阶函数？
运行@mikera的代码，我最终的运行时间为2.453秒，不如scala代码好，但比我的原始版本好得多，比Java版本更好：
(set! *unchecked-math* true)
(defn euler5
[]
(loop [n 1
d 2]
(if (== 0 (unchecked-remainder-int n d))
(if (>= d 20) n (recur n (inc d)))
(recur (inc n) 2))))
(defn is-divisible-by-all?
[number divisors]
(= 0 (reduce + (map #(mod 2 %) divisors))))
对于 Scala，@didierc指出范围对象 1 到 20 实际上不是对象列表，而是一个对象。非常酷。因此，Scala的性能差异在于我们迭代单个对象而不是整数1-20的列表/数组。
实际上，如果我将 scala 方法中的帮助器函数从范围对象更改为列表（见下文），则 scala 版本的运行时间将从 0.302 秒增加到 226.59 秒。
private def isDivisibleByAll2(n: Int, top: Int): Boolean = {
def divisors: List[Int] = List(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)
divisors.forall(n % _ == 0)
}
因此，看起来@didierc已经正确地确定了scala在这种情况下的优势。想知道这种类型的对象如何在java和clojure中实现会很有趣。
@didierc建议通过创建 ImmutableRange 类来改进代码，如下所示：
import java.util.Iterator;
import java.lang.Iterable;
public class ImmutableRange implements Iterable<Integer> {
class ImmutableRangeIterator implements Iterator<Integer> {
private int counter, end, step;
public ImmutableRangeIterator(int start_, int end_, int step_) {
end = end_;
step = step_;
counter = start_;
}
public boolean hasNext(){
if (step>0) return counter <= end;
else return counter >= end;
}
public Integer next(){
int r = counter;
counter+=step;
return r;
}
public void remove(){
throw new UnsupportedOperationException();
}
}
private int start, end, step;
public ImmutableRange(int start_, int end_, int step_){
// fix-me: properly check for parameters consistency
start = start_;
end = end_;
step = step_;
}
public Iterator<Integer> iterator(){
return new ImmutableRangeIterator(start,end,step);
}
}
没有改善运行时间。Java版本在我的机器上运行时间为5.097秒。因此，最后，对于为什么Scala版本性能更好，我们有一个令人满意的答案，我们了解如何提高Clojure版本的性能，但是缺少的是了解如何在Java中实现Scala的不可变范围对象。
最后的思考
正如一些人所评论的那样，改善此代码运行时间的最有效方法是使用更好的算法。例如，以下java代码使用Eratosthenes和Trial Division的筛子在不到1毫秒的时间内计算答案：
/**
* Smallest Multiple
*
* 2520 is the smallest number that can be divided by each of the numbers
* from 1 to 10 without any remainder. What is the smallest positive number
* that is evenly divisible by all of the numbers from 1 to 20?
*
* User: Alexandros Bantis
* Date: 1/29/13
* Time: 7:06 PM
*/
public class Problem005 {
final private static int CROSSED_OUT = 0;
final private static int NOT_CROSSED_OUT = 1;
private static int intPow(int base, int exponent) {
int value = 1;
for (int i = 0; i < exponent; i++)
value *= base;
return value;
}
/**
* primesTo computes all primes numbers up to n using trial by
* division algorithm
*
* @param n designates primes should be in the range 2 ... n
* @return int[] a sieve of all prime factors
* (0=CROSSED_OUT, 1=NOT_CROSSED_OUT)
*/
private static int[] primesTo(int n) {
int ceiling = (int) Math.sqrt(n * 1.0) + 1;
int[] sieve = new int[n+1];
// set default values
for (int i = 2; i <= n; i++)
sieve[i] = NOT_CROSSED_OUT;
// cross out sieve values
for (int i = 2; i <= ceiling; i++)
for (int j = 2; i*j <= n; j++)
sieve[i*j] = CROSSED_OUT;
return sieve;
}
/**
* getPrimeExp computes a prime factorization of n
*
* @param n the number subject to prime factorization
* @return int[] an array of exponents for prime factors of n
* thus 8 => (0^0, 1^0, 2^3, 3^0, 4^0, 5^0, 6^0, 7^0, 8^0)
*/
public static int[] getPrimeExp(int n) {
int[] factor = primesTo(n);
int[] primePowAll = new int[n+1];
// set prime_factor_exponent for all factor/exponent pairs
for (int i = 2; i <= n; i++) {
if (factor[i] != CROSSED_OUT) {
while (true) {
if (n % i == 0) {
n /= i;
primePowAll[i] += 1;
} else {
break;
}
}
}
}
return primePowAll;
}
/**
* findSmallestMultiple computes the smallest number evenly divisible
* by all numbers 1 to n
*
* @param n the top of the range
* @return int evenly divisible by all numbers 1 to n
*/
public static int findSmallestMultiple(int n) {
int[] gcfAll = new int[n+1];
// populate greatest common factor arrays
int[] gcfThis = null;
for (int i = 2; i <= n; i++) {
gcfThis = getPrimeExp(i);
for (int j = 2; j <= i; j++) {
if (gcfThis[j] > 0 && gcfThis[j] > gcfAll[j]) {
gcfAll[j] = gcfThis[j];
}
}
}
// multiply out gcf arrays
int value = 1;
for (int i = 2; i <= n; i++) {
if (gcfAll[i] > 0)
value *= intPow(i, gcfAll[i]);
}
return value;
}
}
