Почему JS решил задачу на рекурсию гораздо быстрее Python/Lua?

Question

[valis]

Есть задача 14 из проекта Эйлера.
Суть задачи есть следующая повторяющаяся последовательность определена для множества натуральных чисел:
n → n/2 (n - чётное)
n → 3n + 1 (n - нечётное)
Какой начальный элемент меньше миллиона генерирует самую длинную последовательность?

Решение задачи рекурсионное. В рамках канала https://www.youtube.com/watch?v=mHbgWHqeBp0 (да качество пока ужасное) я сделал сравнение производительности в решении данной задачи на Python/LUA (код не буду приводить он примерно такой же как и JS)

console.time('coll');
function getCollatz(number, iterations=1){
    if (number===1){
        return iterations
    } else if (number % 2 === 0){
        return getCollatz(Math.floor(number/2), iterations+1)
    } else {
        return getCollatz(3*number+1, iterations+1)
    }
}

let a = 0;
let x = 0;
let y = 0

for (let i = 1; i< 1000001; i++){
    let current_iter = getCollatz(i);
    if (current_iter>a){
        a = current_iter;
        x = i
    }
    y++
}
console.timeEnd('coll')
console.log(x)

Цифры получились такие:

1. Python: 59 сек
   
2. Lua: 17 сек
   

Для меня пока без сюрпризов, но JS на NodeJS справился за 2 секунды!!!!
Собственно вопрос - почему?

P.S. Все 3 теста на одной и той же машине

Comments

[Сергей Горностаев]

А вот зря вы код Python не приводите. На Тостере уже были случаи, когда люди писали формально корректный, но неправильный код, а потом удивлялись, что Python тормозит.

[Сергей Горностаев]

Dr. Bacon, пишет, что NodeJS. Ну, и у Lua тоже есть JIT-компиляция.

[Сергей Соколов]

number % 2 === 0 можно записать как number & 1 === 0 ещё пару копеек сэкономить )

[valis]

Dr. Bacon, Там NodeJS

[valis]

Юрий, Да, наверное так и есть

[valis]

Dr. Bacon, Пасиб. Померяю еще на PyPy

[valis]

Сергей Соколов, Вот за такие хаки и плюются на JS. Экономим пару копеек, въезжаем что вообще здесь происходит пару часов

[Сергей Соколов]

valis, да не, это обычный способ проверки на чётность, работает во всех языках – проверить младший бит.

[Дмитрий Беляев]

Сергей Соколов, в каком-нибудь ЯП с наличием типа int - это бы действительно сэкономило пару копеек, но в js будет приведение f64 -> i32 -> f64 что сведет всю экономию на нет и даже будет медленнее

[Andy_U]

Сергей Горностаев, Ага, возможно, одним декоратором @functools.lru_cache(). Там, конечно, памяти дофига потребуется...

[Wataru]

valis, немного оффтопик, но нормальное решение этой задачи будет таким быстрым, что вы разницы не заметите.

Надо просто завести массив на миллион элементов и запоминать в нем подсчитанные значения функции.

Вроде:

function getCollatz(number, iterations=1){
  if(res[number] > 0) return res[number];
  ...
  restult = GetCollatz(...);
  ...
  res[number] = result;
  return result;
}

[Andy_U]

wataru, @functools.lru_cache() быстрее. А numba еще быстрее. Не сильно, но быстрее. См. мой вариант в ответах. Ну и не массив, а словарь. Просто потому, что в процессе число может выскочить за миллион.

Answer 1

[Dimonchik]

вот тут поковыряй
https://benchmarksgame-team.pages.debian.net/bench...
и больше не майся фигней

есть тесты где асинхронный питон быстрее ноды и т.д и т.п.

все слишком многофакторно чтобы делать обобщения вида N быстрее / медленее M
достаточно знать порядок скорости

JS и Питон языки одного уровня и порядка

Comments

[Владимир Коротенко]

dimonchik2013 за тем исключением что гугл V8 вылизал до совершенства и этот движок сравним по скорости с компилируемыми языками. Кстати по коду могу предположить что питон чистит мусор на вызовах, а нода закомпилировала функцию и развернула цикл, сильно на это похоже.

[valis]

Я же просил пояснить для конкретного случая

[Dimonchik]

для конкретного не имеет практической пользы

хотя бы потому что нет кода

Answer 2

[shurshur]

Когда-то давно один товарищ обнаружил, что реализация вычисления чисел Фибоначчи через рекурсию на Java работает быстрее, чем её аналог на C. Он не только поудивлялся этому, но и поизучал вопрос. Оказалось, что gcc в каждом вызове функции делал push si; push di; и по окончании pop si; pop di; хотя регистры si и di в скомпилированном коде никак не использовались. Это давало какие-то микроскопические, но всё же расходы времени.

Любой конкретный тест специфичен, он показывает не то, как быстро работает тот или иной язык (точнее, его конкретная реализация), а какие в этой реализации получились расходы времени на конкретную задачу. В другой задаче, в другой реализации того же языка, просто даже на другом оборудовании может получиться другой результат.

Answer 3

[Дмитрий Беляев]

Синтетические бенчмарки врут практически всегда, потому что те кто их пишет редко знает досконально все сравниваемые технологии и вряд ли сможет свести задачу к схожим условиям. Как правило, схожие условия выходят только при отключении всех возможных оптимизаций, ибо оптимизации у разных технологий работают по разному.
Как уже написали выше, Вы зря не превели код на Python, возможно специалисты по этому ЯП предложили бы более оптимальное решение.
По js варианту могу сказать, что v8 очень хорошо умеет оптимизировать хвостовую рекурсию. И в данном примере вместо дорогой рекурсии у Вас будет работать более дешевый цикл. Я могу Вас удивить, перепишите свое решение на C вот прямо как есть и скомпилируйте без оптимизаций - js + v8 окажется быстрее

Answer 4

[Andy_U]

Уважаемый автор, попробуйте вот этот вариант (Python 3.8) на вашем компьютере. Результат вас удивит.

import time
import sys
from functools import lru_cache


@lru_cache(5000000)
def calc(number: int) -> int:

    if number == 1:
        return 0
    elif number % 2 == 0:
        iterations = calc(number//2)+1
    else:
        iterations = calc(3*number+1)+1

    return iterations


if __name__ == '__main__':

    sys.setrecursionlimit(2000)
    start = time.process_time()
    max_num, num = 0, 0

    for i in range(1, 1000000+1):
        if (cur_num := calc(i)) > max_num:
            max_num, num = cur_num, i

    print('n =', num, 'iterations =', max_num+1, 'time =', time.process_time()-start, 'sec')

Если поменять декоратор на

@numba.njit()

то будет еще чуть быстрее.