@valis

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

Есть задача 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 теста на одной и той же машине
  • Вопрос задан
  • 477 просмотров
Пригласить эксперта
Ответы на вопрос 4
dimonchik2013
@dimonchik2013
если всем давать - сломается кровать
вот тут поковыряй
https://benchmarksgame-team.pages.debian.net/bench...
и больше не майся фигней

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

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

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

Любой конкретный тест специфичен, он показывает не то, как быстро работает тот или иной язык (точнее, его конкретная реализация), а какие в этой реализации получились расходы времени на конкретную задачу. В другой задаче, в другой реализации того же языка, просто даже на другом оборудовании может получиться другой результат.
Ответ написан
bingo347
@bingo347 Куратор тега JavaScript
Бородатый программер
Синтетические бенчмарки врут практически всегда, потому что те кто их пишет редко знает досконально все сравниваемые технологии и вряд ли сможет свести задачу к схожим условиям. Как правило, схожие условия выходят только при отключении всех возможных оптимизаций, ибо оптимизации у разных технологий работают по разному.
Как уже написали выше, Вы зря не превели код на Python, возможно специалисты по этому ЯП предложили бы более оптимальное решение.
По js варианту могу сказать, что v8 очень хорошо умеет оптимизировать хвостовую рекурсию. И в данном примере вместо дорогой рекурсии у Вас будет работать более дешевый цикл. Я могу Вас удивить, перепишите свое решение на C вот прямо как есть и скомпилируйте без оптимизаций - js + v8 окажется быстрее
Ответ написан
@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()

то будет еще чуть быстрее.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы