Тысячеликий формошлёп. Начало пути.

Предисловие

Рассмотрим задачу вычисления первых 100 чисел Фибоначчи, выпавшую на долю формошлёпа. По определению $n$-ное число Фибоначчи задаётся рекуррентным соотношением:

То есть каждое последующее число равно сумме двух предыдущих, где первое число равно нулю, а второе — единице.

Это определение естественным образом переводится на язык программирования, например, на TypeScript:

function fib(n: number) {
  if (n <= 1) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

На этом моменте задачу можно назвать решённой и пойти заняться формошлёпством, дабы поразить мир тем, чего он ещё не видовал:

При использовании данного калькулятора выясняется, что решение действительно поразительное, но, увы, в плохом смысле. Оно несёт в себе критический недостаток: время, которое занимает вычисление, возрастает с ростом $n$ и, начиная с $n\approx40$, калькулятор уже становится непригодным для использования — проще найти другой сервис.

Ситуация усугубляется тем, что средой выполнения кода является главный поток браузера, а длительное вычисление полностью его блокирует, что проявляется как "подвисание" страницы, в чём можно убедиться, попытавшись воспользоваться калькулятором, расположенным ниже, во время вычисления большого числа.

Чтобы избежать неприятных оказий с "повисшей" страницей, калькулятор имеет встроенный предохранитель, не дающий ввести число больше 42.

Для решения проблемы фронтендеру, знакомому с модными передовыми технологиями, могла бы прийти в голову идея перенести вычисления в WebWorker:

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

Осознав, что WebWorker никак не решает главную проблему (низкую скорость вычисления при больших $n$), фронтендер мог бы подумать, что корень зла кроется в этом медленном JavaScript'е с его слабой динамической типизацией и отдалённостью от реальных команд, выполняемых железом. И тогда появится реализация на Rust, которая при помощи WebAssembly будет выполняться в браузере:

fn fibonacci(n: u32) -> u32 {
    match n {
        0 => 1,
        1 => 1,
        _ => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

Скорость вычисления возросла в 1.5-2.5 раза! Но победой такой результат назвать сложно — такой прирост производительности позволяет вычислить лишь на пару-тройку чисел больше, чем JavaScript версия.

В этот момент раунд торгов заканчивается и наступает стадия депрессии — WebWorker, Rust, WebAssembly, настройка Next.js и Webpack — неужели вся эта не самая тривиальная работа по "склейке" всех этих технологий была впустую?

Формошлёп видит единственный постыдный выход — переложить ответственность и вычисления на мускулистые плечи бэкенда. Уж там-то сервер, арендованный у Amazon, быстро расколет этот орешек и вернёт заветное ядрышко в мгновение ока. Или нет? Пусть тогда купят сервера по-мощнее, ей-богу.

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

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