我该怎么做才能加快这段代码的速度？

Question

我正在尝试学习Java,Scala和Clojure.

我正在研究三种语言的Project Euler问题.下面列出了问题#5(http://projecteuler.net/problem=5)的代码以及前五个问题的运行时间(以秒为单位).令我惊讶的是Java和Clojure版本比问题#5的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  |

问题#5的Java版本

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

}

问题#5的Scala版本

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的Clojure Verson

(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,11 ^ 1,17 ^ 1,19 ^ 1)和将它们相乘.

更有趣的方面是使用基本相同的算法来理解三种语言之间的差异.有些情况下,像这样的强力算法可能会有所帮助.那么,为什么性能差异呢？

对于Java,一个建议是将ArrayList更改为一个原始的int数组.这确实减少了运行时间,减少了约0.5-1秒的时间(我今天早上跑了它,它将运行时间从4.386秒减少到3.577秒.这减少了一点,但没有人能够拿出一个将它带到半秒以下的方式(类似于Scala版本).考虑到所有三个都编译成java字节码,这是令人惊讶的.@ didierc建议使用不可变迭代器;我测试了这个建议,它将运行时间增加到超过5秒.

对于Clojure,@ mikera和@Webb提出了一些加快建议的建议.他们建议使用loop/recur进行快速迭代,使用两个循环变量,unchecked-math用于稍微更快的数学运算(因为我们知道这里没有溢出的危险),使用原始long而不是盒装数字,并避免更高阶函数,如每一个？

运行@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代码使用Sieve of 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;
  }
}

Answer 1

Scala更快,因为其他解决方案无缘无故地创建显式集合.在Scala中,1 to top创建一个对象来表示来自的数字1,top但不会在任何地方明确地列出它们.在Java中,您可以显式创建列表 - 并且ArrayList每次迭代创建一个对象比创建一个20的数组(实际上是21个对象,因为它也是一个对象)要快得多.

(请注意,没有一个版本实际上接近最佳状态.请参阅"最小公倍数",这是Eastsun在不提及它的情况下所做的事情.)

Answer 2

这是Clojure中更快的版本:

(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))))

(time (euler5))
=> "Elapsed time: 2438.761237 msecs"

即它与Java版本的速度大致相同.

关键技巧是:

• 使用loop/recur快速迭代有两个循环变量
• 使用unchecked-math的稍微快一点的数学运算(因为我们知道有没有溢出的危险在这里)
• 使用原始long而不是盒装数字
• 避免像高阶函数那样的高阶函数every?- 它们比低级操作具有更高的开销

显然,如果你真的关心速度,你会选择一个更好的算法:-)