Комментарии 24
для собеседований лучше так:
func gcd(_ a: Int, _ b: Int) -> Int { return b==0 ? a : gcd( b, a%b ); }
О, да, запись красивая, однозначно. А, учитывая, Swift 5.1 даже return можно не писать (точку с запятой, конечно, тоже, но это, наверное, опечатка). Но сразу после этого, думаю, нужно быть готовым пояснить, чем опасна рекурсия, и все же настрочить итеративную версию.
давайте так, весь код для бенчмарка в статье и комменте есть, соберите файлик, запустите с оптимизациями, и затем поделитесь с нами практическими выводами.
у меня на Винде нет последнего Swift-a.
никакого нет.
а в последних обычно лучше оптимизации.
чем же он плох то?
long c = 0;
while (b != 0)
{
c = b;
b = a % c;
a = c;
}
return a;Но на самом деле, если вас смущала рекурсия, то зря, т.к. она хвостовая и также переводится в цикл автоматически в большинстве языков
P.S. Простите, что пример не на swift, не пишу на этом языке
1) эх ты, я хотел, чтобы они(neurocore и автор) сами нарыли выход из своих ошибочных заблуждений, в которых слишком уверены.
2) свапать необязательно.
только если критически важно сэкономить 0.5 деления.
3) ненамного эффективнее.
в цикле divisionGCD выполняется 3 сравнения вместо 1ого в gcd, но, поскольку, деление — долгая операция, то выигрыш gcd будет несколько процентов. зато по количеству текстового кода — на 1000%, а машинного — на 200%.
improvedDivisionGCD может быть эффективнее.
готовы пояснить, почему именно эта рекурсия неопасна?
дизассемблерный код gcd
и можете ее замерить с @inlinable и без?
доп:
ваша рекурсивная реализация переворачивания односвязного списка опасна.
сможете настрочить безопасную рекурсию?
Не могли бы вы донести вашу мысль немного доступней?
Вы привели код хорошей такой, краткой, красивой, но рекурсивной функции, решающей обозначенную задачу. Я добавил, что об опасностях рекурсии стоит помнить всегда, когда она используется – думаю, понятно почему: не константное асимптотическое использование памяти и все такое.
Да, классные современные компиляторы классных современных ЯП умеют всякие оптимизации, в том числе разворачивать хвостовую рекурсию в цикл. Но об этом же сразу написал коллега в других комментариях: цель была высказать принципиальную мысль, а не привязываться к языкам и компиляторам.
Что если это будет, возвращаясь к теме собеседований, фукнция написанная на бумажке на "любом" ЯП и анализируемая глазами вместо компилирования?
Вы пишете, что худшими входными данными для алгоритма являются последовательные числа Фибоначчи. Добавьте их в тесты, чтобы показать, насколько худший случай хуже среднего.
Само слово “алгоритм” восходит к имени арабского математика Аль-Хорезми, жившего примерно в VII-IX вв. уже нашей эры.
Аль-Хорезми является персидским учёным, а не арабским.
… А место его рождения по нынешним меркам находится и вовсе в Узбекистане. Но, думаю, в данном случае погрешность простительна!
2. Извините, конечно, но я бы не хотел чтобы Ньютона назвали русским, а Менделеева французом.
В интернетах пишут, что он родился в Хиве: https://en.wikipedia.org/wiki/Khiva
Аль-Хорезми писал на арабском, а не на персидском. Персами же, как я понял, считаются иранцы, для которых родной язык – персидский.
В очередной раз о НОД, алгоритме Евклида и немного об истории алгоритмов вообще. Конечно, с примерами на Swift