java - 我怎样做才能加快这段代码的速度？

Question

我正在尝试学习Java，Scala和Clojure。

我正在用三种语言解决欧拉计画的问题。下面列出的是问题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、13 ^ 1、17 ^ 1、19 ^ 1)和将它们相乘。

更加有趣的方面是使用本质上相同的算法来理解三种语言之间的差异。在某些情况下，像这样的蛮力算法可能会有所帮助。那么，为什么会有性能差异？

对于Java，一个建议是将ArrayList更改为int的原始数组。这确实减少了运行时间，减少了约0.5-1秒的时间(今天早上我才运行它，它将运行时间从4.386秒减少到3.577秒。虽然减少了一点，但是没有人能想到将其降到半秒以下的方式(类似于Scala版本)，考虑到这三个都编译为Java字节码，这令人惊讶，@ didierc的建议是使用不可变的迭代器；我对此建议进行了测试，并且将运行时间增加到超过5秒。

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

运行@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

这是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?这样的高阶函数-它们比低级操作

具有更高的开销

显然，如果您真的在乎速度，则可以选择更好的算法:-)