Friday, October 22, 2010

Не всё то быстро, что в библиотеке

Так получается иногда, что и алгоритм написан правильно и всё вроде коротко и ясно, а решение все равно не укладывается в требуемые временные ограничения... Эта история началась с задачки.
На первый взгляд оптимальное и простое решение пусть и давало правильные ответы, но на максимальном объеме данных работало неприлично долго. Что делать, полез смотреть решения более умных коллег. Каково же было мое удивления, когда другие решения оказались по-сути такими же, но только почти в 10 раз быстрее.
Потанцевав с бубном, проверив еще раз свое решение и убедившись что оно идентично правильному, обратил внимание на такое маленькое различие.

В моем решении, я возводил некоторое число в степень, всё это происходило в цикле:
  
t1 += Math.pow(t0%10, K);


Аналогичная строчка в правильном решении:
  
int k = t0%10;
for (int ki=1; ki<K; ki++) k*=t0%10;
t1 += k;


-В чем секрет? Подумал я. Ведь вызов стандартной функции возведения в степень должен быть достаточно быстрым. Секрет, как оказалось, был именно в этом.
В чем позволяет легко убедиться маленький эксперимент:
  
public static void main(String[] args) {
long t0 = System.currentTimeMillis();
for(int x=0; x<100000; x++){
for(int a=0; a<10; a++){
Math.pow(x, a);
}
}
long t1 = System.currentTimeMillis();
for(int x=0; x<100000; x++){
for(int a=0; a<10; a++){
pow(x, a);
}
}
long t2 = System.currentTimeMillis();
System.out.println("Math.pow() time " + (t1-t0));
System.out.println("Simple pow time " + (t2-t1));

}

private static double pow(double x, long a){
double res = 1;
for(int i=0; i<a; i++) res*=x;
return res;
}

Результат работы:
Math.pow() time 375
Simple pow time 31

Разница более чем в 10 раз!
Таким образом, для возведения в целочисленную степень с небольшой величиной показателя лучше использовать простой цикл, вместо стандартных библиотечных функций.

Что мне не понятно, так это почему в стандартной библиотеке нет способа решения проблемы. Ведь это задача встречается достаточно часто, настолько часто, что некоторые языки программирования даже имеют соответствующий оператор возведения в степень. В Java можно было бы просто перегрузить метод Math.pow(double a, int pow), добавить проверку на величину pow и по результату проверки использовать либо простой цикл либо стандартное возведение в степень.

No comments:

Post a Comment