Java、Scala、Clojure を学ぼうとしています。
私は 3 つの言語で Project Euler の問題に取り組んでいます。以下に、問題 #5 ( http://projecteuler.net/problem=5 ) のコードと、最初の 5 つの問題のこれまでの実行時間 (秒単位) を示します。問題 5 で、Java と Clojure のバージョンが Scala のバージョンよりもはるかに遅いことは、私にとって驚くべきことです。それらは同じマシン、同じ jvm で実行されており、結果はいくつかの試行で一貫しています。2 つ (特に 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 バージョン
(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)))))
編集
さまざまな回答を自分の回答にまとめることが提案されました。ただし、クレジットが必要な場合はクレジットを提供したいと思います（実際には、この質問には自分で答えていません）。
最初の質問に関しては、より優れたアルゴリズムを使用することで、3 つのバージョンすべてを高速化できます。具体的には、1 ～ 20 の数字の最大公約数 (2^4、3^2、5^1、7^1、11^1、13^1、17^1、19^1) のリストを作成し、それらを乗算します。
はるかに興味深い側面は、基本的に同じアルゴリズムを使用して 3 つの言語の違いを理解することです。このようなブルート フォース アルゴリズムが役立つ場合があります。では、なぜパフォーマンスの違いが生じるのでしょうか?
Java の場合、ArrayList を int のプリミティブ配列に変更することをお勧めします。これにより実行時間が短縮され、約 0.5 ～ 1 秒短縮されます (今朝実行したところ、実行時間が 4.386 秒から 3.577 秒に短縮されました。少し短縮されましたが、誰も(Scala バージョンと同様) 0.5 秒未満にする方法. 3 つすべてが Java バイトコードにコンパイルされることを考えると、これは驚くべきことです. @didirc によって、不変イテレータを使用するという提案がありました. 私はこの提案をテストしました.実行時間が 5 秒強に増加しました。
Clojure については、@mikera と @Webb がスピードアップのためのいくつかの提案をしています。彼らは、2 つのループ変数を使用した高速反復には 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 の範囲は実際にはオブジェクトのリストではなく、1 つのオブジェクトであると述べています。とてもかっこいい。したがって、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 でどのように実装されるかを知ることは興味深いでしょう。
次のように、ImmutableRange クラスを作成してコードを改善するという @didierc の提案:
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 コードは、エラトステネスの篩と試行分割を使用して、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;
}
}