Я пытаюсь изучить Java, Scala и Clojure.
Я работаю над проблемами Project Euler на трех языках. Ниже приведен код проблемы № 5 (http://projecteuler.net/problem=5), а также время выполнения (в секундах) до сих пор по первым пяти проблемам. Мне поразительно, что версии Java и Clojure намного медленнее, чем Scala для проблемы № 5. Они работают на одной машине, то же самое 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)
}
}
Clojure Версон проблемы № 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. и это увеличило время работы всего на 5 секунд.
Для Clojure, @mikera и @Webb дают несколько предложений, чтобы ускорить процесс. Они предлагают использовать loop/recur для быстрой итерации с двумя переменными цикла, 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, но недостающее будет заключаться в том, чтобы понять, как реализовать Scala неизменяемый объект диапазона в Java.
ЗАКЛЮЧИТЕЛЬНЫЕ МЫСЛИ
Как прокомментировали некоторые из них, самым эффективным способом улучшить время работы этого кода является использование лучшего алгоритма. Например, следующий код 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;
}
}
