Комментарии 135
1. Быть проще, и люди к вам потянутся.
next = prev + next;
prev = next - prev;
У вас кончились талончики на переменные?
Кажется, для срабатывания memoize функцию fib надо записать иначе. Например, fib = memoize(n => {...})
Грубо говоря, вам надо, чтобы oldFib вызывала memoize(oldFib). Этого можно добиться несколькими методами, но вот просто скормить готовую рекурсивную функцию вашей реализации memoize — точно не выйдет (а вот если записать fib = memoize(n => {...}) — получится автоматически)
const oldFib = n => {
console.log(n);
if(n <= 1){
return 1;
}else{
return fib(n - 1) + fib(n - 2);
}
}
const memoize = f => {
const cache = {};
return arg => cache[arg] || (cache[arg] = f(arg));
}
const fib = memoize(oldFib);
fib(10);Консоль говорит: 10 9 8 7 6 5 4 3 2 1 0. Как и ожидалось.
Упс, пардон, я был невнимателен, прочитал в посте версию с ошибкой (как-то не ждёшь такого — особенно перечитывая пост, точнее, ища в нём «oldFib»), а что после неё шла нормальная — не сразу заметил.
P.S. Порой на хабре хочется видеть историю правок поста, как в wiki.
const answer = [2, 8, 34,… ]
print(answer)
Тестовые задания шлют когда хотят отшить
На чем основано это утверждение?
Да и потом смысл есть дальше разговаривать если я уже сейчас вижу абсолютную бескомпромиссность, можно изучить опыт крупных компаний как они проводят собесы, там нет тесовых заданий, есть или онлайн лайв кодинг, или совместное изучение кода твоих проектов, ну и потом чаще всего или тестовый раб день, или что то типа долгого собеседовочного дня где да нужно будет решать задачи.
Я готов к тестовому если оно оплачивается, но если ты пообщался в скайпе по телефону и тебе говорят давайте сделайте тестовое еще, то это значит что ты уже не нужен им, по разным причинам.
Если отказываются обобщатся, а с начало просят сделать тестовое значит им вообще не нужен сейчас никто, просто так базу набирают или повышают свою известность.
Можно дожать константу, если диагонализировать матрицу, то можно основные вычисления свести к вычислению степени от корня из пяти.
- У вас первая функция (остальные не проверял) не работает на отрицательном полупериоде
- Одна из функций неверно возвращала значение при нуле — об этом уже выше написали
- За использование стрелочных функций везде где только можно (а особенно в туторе) надо отрывать руки
- Компанию, где на собеседовании такое спрашивают на должность программиста, а не рокетсайенс или сайенс, надо обходить стороной
- Вы ещё скажите, что функцию надо аналитически продолжить на всю комплексную плоскость)
- Да, тут была путаница, я вроде исправил.
- А чем плохи стрелочные функции?
п3 — про стрелочные функции куча была уже статей когда их надо и когда их не надо использовать — пихать их везде — не лучшая идея, особенно в данном, конкретном случае
И чему же равно Pi**e-тое число Фиббоначчи?)
Пи в степени е — не рациональное число— судя по вики, одна из открытых математических проблем: про пи в степени e неизвестно, является ли оно рациональным или нет. Не знаю, специально Вам такое число сказали или нет, просто глаз зацепился.
число вида a^b где a — алгебраическое число, отличное от 0 и 1, а b — иррациональное алгебраическое число, всегда является трансцендентным
Со ссылкой на Гильберта
ух ты)
На самом деле я действительно ошибся, подумал что речь об комплексной плоскости почему-то...
Посчитал по обобщенной формуле Бине :) Fib(pi ^ e) = 22090.2876638248, -8.97932700936443E-06 * i.
3. Подскажите мне, пожалуйста, одну из этой кучи статей. Я прошу без всякой иронии, я допускаю, что вы правы, просто мне при беглом поиске не попадается статья, где написано, что именно неправильно именно в моём коде.
Плохо читаются.
На самом деле спасибо за подробный разбор задачи. Я далек от JS, с опытом программирования в пару скетчей на Ардуино по типу «while робот далеко от стены analogWrite скорость 255», но мне было понятно и интересно читать. Именно такие статьи и мотивируют изучать языки, с мыслью «я понял идеологию, осталось написать такой код и поиграться с ним самому».
Выражаясь грубым языком O-нотации, такое решение имеет временную сложность O(e^n).
Это правильно, но слишком грубо. Можно получить более точную оценку числа вызов функции ~(1+sqrt(5)) fib(n) и красивое замечание "Для вычисления числа Фибонначи наивным рекуррентным методом понадобится вызовов функции в 3.2 раза больше чем само число Фибонначи".
const fib = n => {
let result = id;
let m = matrix;
const bits = n.toString(2);
for(const bit of bits){
if(bit == "1")
result = mul(result, m);
m = mul(m, m);
}
return result[1][0];
Например, множитель возводится в квадрат и в зависимости от того, выставлен ли бит умножает результат, работает от младшего бита к старшему, например 2^10 r=1 (результат), m=2(множитель)
10 в двоичной это 1010, идя по битам от младшего к старшему 0101
0 m=2, r=1
1 m=4, r=r*m=4
0 m=16, r=4
1 m=256, r=r*m=1024
Т.е. 2^10 = 2^2*2^8
В двоичном виде степень меняется так:
0,10,010,1010
В приведённом алгоритме же порядок прохода битов от старшего к младшему, множитель не меняется, а сам результат возводится в квадрат, если бит 1 то ещё и домножается на множитель.
1 m=2, r=r*r*m=2
0 m=2, r=r*r=4
1 m=2, r=r*r*m=32
0 m=2, r=r*r=1024
Т.е. 2^10=(((2)^2)^2*2)^2
В двоичном виде степень меняется так:
1,10,101,1010
Всё верно, возведение в квадрат это дописать к степени в двоичном виде 0 справа, а если там должна быть единица то ещё домножить.
Однако я ожидал увидеть там немного другую реализацию — без нахождения старшего бита :).
Все нормальные способы вычисления чисел Фибоначчи (быстрое возведение матрицы в степень, разделяй и властвуй и особенно динамическое программирование) — вполне себе computer science.
Это конечно хорошо, но он сможет мне выдать 100000000 член ряда Фибоначчи?
Такой метод хорош для простых чисел...
в задаче возвращаемое значение было int на Java, так что 100000000 член ряда не требовался
Ответ кроется вот в этой моей статье.А написали ли вы уже игру «про деревянные домики и теорему Кёртиса-Хедланда-Линдона»?
Джва года уже прошли. (Или нет, так как «джва» может быть числом в совсем другой системе счисления.
К тому же это была только нижняя граница.)
Звучит дико интересно! Могли бы вы поделиться ссылкой на контекст?
Этот подход показался мне настолько забавным, что я написал небольшую игру, которая позволяет игроку ощутить всю его прелесть лично.упоминает домики и теорему.
Мне кажется в формуле небольшая ошибка.
Округлять надо не до ближайшего целого, а просто вверх.
Потому что проблема в √5
Поскольку число иррациональное, нам не хватает знаков после запятой.
В смысле √5 немного больше того рациональной записи в JS.
Тогда надо Math.ceil для округления вверх.
Вообще, извините, что я на вас побухтю, но такие вещи лучше сначала пробовать самому, а потом уже писать. Если подставите туда ceil, увидите, что расхождения начнутся сразу же, на каждом втором числе)
очень интересные решения встречались.
developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/let#Description
«Правильная» рекурсия с пункта 2 дает нам — 354224848179262000000 за 0.571044921875ms
Самый быстрый алгоритм на Диком Западе дает нам — 354224848179261900000 за 0.689208984375ms
Но самое интересное что 100 число Фибоначчи то — 354224848179261915075
RISENT, пожалуй, это ответ и вам тоже.
Меня вот больше всего удивило, что
Получение значения свойства объекта по ключу — это операция быстрая, но всё-таки не O(1), а O(log(size))
Где тут подвох? Подвох в том, что хэши могут повторяться, и в бакетах может быть заметно больше одного элемента. Но даже в этом случае получить ассимптотически что-то большее чем O(1) можно только специально подбирая данные.
На синтетических тестах теория подтверждается практикой — чтение из объектов размером 100 имеет такой же перфоманс как и чтение из объектов размером 10М. Гугл подкинул мне вот такую ссылку stackoverflow.com/questions/12241676/javascript-objects-as-hashes-is-the-complexity-greater-than-o1, но думаю можно и лучше поискать
Где тут подвох? Подвох в том, что хэши могут повторяться,Теоретически, если данные мы получаем «откуда-то», злые люди могут подобрать их так, что все хэши будут одинаковые.
Объекты в JS — это хэш таблицы, а хэш таблицы хранятся не так как вы говорите — там нет никакой сортировкиСвойства объектов в JS отсортированы в порядке добавления, по меньшей мере, они перечисляются в таком порядке, за исключением свойств с беззнаковыми 32-битными целочисленными ключами (в спеке начиная с ES2015).
Что касается реализации, могут быть варианты. Например, «быстрое» свойство в движке получается тремя ассемблерными инструкциями по заранее известному смещению.
Интересно, сколько раз на Хабре были числа Фибоначчи на матрицах? Раз пять я, наверно, видел…
Довели бы уж тогда до конца. Если умножение матриц этих расписать по определению, там видно, что некоторые действия лишние, и можно вывести более эффективную формулу без матриц.
Так-то много чего можно добавить. И корень-из-пяти-рациональные числа выписать ещё раз специально для этого поста. И бенчмаркинг провести. Ещё можно было упомянуть про прикольную приблуду для питона, которая почти произвольный цикл может ускорить, переведя его в матричную форму и использовав быстрое возведение в степень. Но поля этой рукописи слишком узки…
fibs = 1: 1: zipWith (+) fibs (tail fibs)
Красиво. Впрочем, тут же O(n) всё равно?
fib n = head (apply (Matrix [[0,1], [1,1]] ^ n) [0,1])Говорят, что это "Hello, world!" of Haskell programming; здесь есть и другие решения: https://wiki.haskell.org/The_Fibonacci_sequence
F2n = Fn * (2*Fn+1 – Fn)
F2n+1 = Fn2 + Fn+12
Реализация, кстати, получается довольно компактная.
Более того, этот подход обобщается на числа K-фибоначчи (т.е. каждое число — сумма K предыдущих). И он дает в K раз более хорошую асимптотика чем через матрицы (квадрат от K вместо куба).
Как-будто Milfgard, только про алгоритмы. Качественно, свежо, здорово!
Как вам такое в 2 ночи:
const fib = (n, i = 1, r1 = 0, r2 = 0) => (i >= n) ? r1 + r2 : fib(n, i + 1, (r2 || 1), r1 + r2);
const fib = n => {Какое же это уродство. Попробуйте это прочесть: константа fib равна сопоставлению между n и каким-то огромным блоком. Стрелочные функции придумывались не для таких ситуаций. Они придумывались для повышения наглядности коротких, простых функций, в примерах вроде такого:
var newUsers = users.filter(u => u.registered >= new Date('2014-01-01'));
var karma = sum(user.comments.map(c => c.score));В вашем же случае гораздо лучше смотрится слово function, смотрите:
function fib(n) {Прочтите: Функция fib с аргументом n и телом, которое идет ниже. Совсем другое дело. Уже по первому слову ясно, что перед нами. Если усложнять, то мне еще больше нравится что-то такое:
/** Комментарий на великом, могучем */
function fib(n: number): number {Какая прелесть!
Не надо бездумно использовать const и стрелки просто потому, что они недавно появлились. Неграмотным разработчикам кажется, что это делает их код более "современным", но по факту это лишь демонстрирует у них отстутствие понимания, что для каких ситуаций придумано.
Внимательный читатель может возразить, что да, синтаксис уродский, но зато функцию нельзя переопределить благодаря const. Мой ответ: ущерб от уродского синтаксиса слишком большой и перевешивает выгоды. А по-хорошему, надо бы просто в строгом режиме и в модулях ES6 сделать все function с признаком const автоматически.
Вот, кстати, пример такого неграмотного комментария в ответ на вполне логичный вопрос, а зачем здесь стрелочные функции:
А function вполне используется, у неё просто своя сфера применения. Стрелочные функции не имеют собственного this, поэтому обычные применяются там, где this нужен.
Ага, у нее есть "своя область применения", но я вам про нее не скажу, тем более что я в этом не разбираюсь.
Что касается потери точности при методе Бине, я подозреваю, аналогичная потеря точности будет и при "ручном" вычислении через плюсы и умножения. Так как в JS числа это float со всеми вытекающими.
Ага, у нее есть «своя область применения», но я вам про нее не скажу, тем более что я в этом не разбираюсь.Вот здесь вы переходите к оскорблениям.
Что касается потери точности при методе Бине, я подозреваю, аналогичная потеря точности будет и при «ручном» вычислении через плюсы и умножения. Так как в JS числа это float со всеми вытекающими.А вот здесь пишете откровенную глупость. Во-первых, не float, а double. Во-вторых, никакая потеря точности не может произойти, пока операнды и все результаты целые и не превосходят по модулю Number.MAX_SAFE_INTEGER.
В общем, мне кажется, вам стоило бы умерить апломб и сменить тон. Но, разумеется, это всего лишь дружеская рекомендация, как не упасть в кармическую яму (тут я заглянул к вам в профиль) ещё глубже.
У-у-у-у-у! Алгоритмы! Юра знает алгоритмы! Полтора года назад Юра обошел дерево в ширину алгоритмом, и вы представьте себе, это действительно было нужно сделать!
Полтора года назад Юра обошел дерево в ширину алгоритмом, и вы представьте себе, это действительно было нужно сделать!
Да, алгоритмы нужны не везде и не всегда. Но когда они действительно нужны, если разработчик их не занет, он даже не поймет, что они там нужны.
Заводить в команде отдельного "алгоритмиста" тоже не вариант по той же причине — остальные разработчики должны понять, что его нужно призвать. Или придется ему ревьювить все изменения в коде, что не скейлится.
Всегда нравилось формулирование и решение задач через матрицы, но не знал, что так можно с классическими числами Фибоначчи сделать.
Осталось прикрутить перемножение матриц через gpu.js — и можно рассказывать на собеседованиях, что умеешь вычислять числа Фибоначчи на GPU (главное не упоминать при этом, что на матрицах такого размера оно от это только медленнее станет). :)
"Запомните этот вариант. Так делать не стоит. Не следует. Нельзя. Никогда. Это хуже, чем пинать щеночков, и сравнимо с небольшим холокостом."
Это довольно холиварное утверждение) потом вы сами описываете что существуют способы для ускорения работы рекурсии. В целом есть ряд декларативных языков программирования где кроме рекурсии и алгебраических типов нет возможности реализовать циклы. Например Haskell, и прочие некоторые функциональные языки программирования. И говоря про рекурсию это она в джс так ужасно работает. Существет определенный набор оптимизаций для ускорения работы рекурсии, мемоизация, трамплины, ленивое исполнение и тд.
Использование рекурсии не нужно избегать, для определеного типа задач больше подойдет именно рекурсия. Просто нужно знать что ты делаешь.
А вообще декларативный код vs императивный это отдельная тема холивара))
Хочу предложить еще один способ, который работает с мемоизацией. Реализован при помощи Y-комбинатора.
// condition lazy
var condL = x => tF => fF => x ? tF() : fF();
// Y combinator
var Y = f => (x => x(x))(x => y => f(x(x))(y));
// Memoized Y combinator
var Ymem = memory => F => F(x => condL(memory.has(x))(y => memory.get(x))(y => memory.set(x, Ymem(memory)(F)(x)).get(x)));
// Fib function
var fibF = f => n => n === 0 || n === 1 ? 1 : f(n - 1) + f(n - 2);
// memoized fi function
var fib = Ymem(new Map)(fibF);
console.log(fib(160))
Сорри, что спустя 5 месяцев, но вставлю свои пять копеек.
Во-первых, про асимптотику наивной рекурсивной функции.
F(n) = F(n-1)+F(n-2) if n>2 else 1
Как думаете, во что она раскладывается? Правильно! В 1+1+...+1
Сколько же этих единичек и плюсиков? Тоже правильно… Итого, имеем O(F(n)).
А по формуле Бине мы видим, что F(n) — это какая-то приблизительно показательная функция, с основанием φ = (1+√5)/2, что приблизительно равно 1.6.
Не e и даже не 2, но тоже от души.
Это, кстати, касается и другой известной мозгоклюйки — функции Аккермана.
Она, мало того, что зверски растёт, так ещё и определена через суммирование единичек.
Во-вторых, про самый быстрый способ.
Самый быстрый способ — табличный. Если мы знаем разрядность чисел, то легко найдём, какое самое большое число Фибоначчи влезет в него. А оттуда — какой его порядковый номер. Опять же из формулы Бине, этот номер будет в районе N*log2/logφ, где N — разрядность.
Грубо говоря, для 64-битных целых нам надо записать порядка 90 чисел.
Один раз вычислили, захардкодили, и готово.
В-третьих, из таблицы же можно брать значения для матрицы, чтобы начинать сразу с 90-го числа, а не с первых. Это, если мы полезли в большие целые с неограниченной разрядностью.
Фибоначчи на собеседовании