8 июня 2012 г.

V8 и Javascript: оптимизация циклов в Chrome

Конечно, следует внимательнее посмотреть презентацию Егорова One day life in V8 (http://2012.jsconf.us/), но меня позабавило следующее при реализации функции, подсчитывающей количество делителей натурального числа.

Весь код на PasteBin


Вариант 1: работает за 1317 мс на 1E8
function divisors_count ( n ) {// 1E8 -> 1317ms
  if (n == 1) return 1;
  i = 1;
  count = 0;
  p = 0;
  n2 = n/2;
  while (i < n2 + 1 && p != i) {
    d = n / i;
    if (d % 1.0 == 0) {
      count+=2;
      p = d;
    }
    i++;
  }
  return count;
}

Вариант 2: работает быстрее, за 1246 мс
function divisors_count ( n ) {// 1E8 -> 1246ms
  if (n == 1) return 1;
  i = 1;
  count = 0;
  p = 0;
  while (i < n / 2 + 1 && p != i) {
    d = n / i;
    if (d % 1.0 == 0) {
      count+=2;
      p = d;
    }
    i++;
  }
  return count;
}

То есть получается что вариант, в котором вынесено за пределы цикла выражении n / 2 работает МЕДЛЕННЕЕ!
Между тем, более оптимальным алгоритмом подсчета количества делителей на Javascript является следующий:
function divisors_count (n) { // 1E8 -> 580ms
  if (n == 1) return 1;
  i = 1;
  count = 0;
  p = 0;
  while (i < n / 2 + 1 && p != i) {
    d = n % i;
    if (d == 0) {
      count+=2;
      p = n/i;
    }
    i++;
  }
  return count;
}

Что достаточно очевидно — в цикле мы выполняем деление только один раз. И один раз делаем когда добавляем в счет. т.к. делителей намного меньше чем число итераций, то следовательно второе деление менее трудозатратно.
Отправить комментарий