Pull to refresh

Comments 121

Зато всегда можно ответить на вопрос «А чем ты, собственно, занимался всю неделю????»
Думаю, что за ответ «Писал абстрактную фабрику абстрактных фабрик для подсчёта факториала» дадут по балде :)
Зависит от стадии ООПухоли мозга системного архитектора.
Не дадут, они привыкли. Не зря же:
jezzarax: тебе на asp.net'е hello world настрогать за 10 минут научиться можно (8 минут на запуск студии, 2 на кодинг), на java такое не прокатит
jezzarax: пока скачаешь одну библиотеку, пока другую, пока их xml конфигом на полметра склеишь, пока маппинг для hibernate настроишь, пока базу нарисуешь, пока веб-сервисы поднимешь
jezzarax: вроде и hello world пишешь, а уже две недели прошло и всем кажется, что это учетная система для малого бизнеса

С баша
Искал способ, как захламить код.

Мне это напоминает реализацию include на PHP, которуюя однажды встретил.

$content=file(«filename.php»);
$evalCode='';
for ($x=0;$x<count($content);$x++){
$evalCode+=trim($content[$x]);
}
eval($evalcode);

Естественно я тут утрировал многое, было расписано намного больше…
Так не надо считать факториал:
for (int i = 1; i < = n; ++i) ret *= i;
Правильно:
for (int i = 2; i < = n; ++i) ret *= i;

До конца читал, ждал пока Вы замените эту строчку. Эээхх…
Вот чёрт, упустил самое главное!
Да такое есть почти для любого языка.
Например, хаскелл: www.willamette.edu/~fruehr/haskell/evolution.html
По моему мнению, вариант для хаскеля — один из самых мозгоразрывающих =)
только в обратную сторону, да?
Просто порвало когда прочитал кусок про Web Progammer, особенно часть где: i = 1; # Thanks Adam

убило про windows программера) отличная пародия на winapi
всегда существует боллее высокий уровень абстракции
А почему я не вижу реализации mp3 плеера?! неполностью тема раскрыта ;)!
Нужно не synchronized, в ConcurrentHashMap для кэша.
Проехали — все равно топик о том, как не надо делать.
Первое, о чём нам говорили в курсе численных методов: часто подход, исходящий из определения какой-либо функции, является неэффективным, неустойчивым в вычислительном смысле, медленно сходящимся и т. д…

Например, считать e^x по определению, как lim_{x->\infty}\left(1+frac{x}{n}\right)^n — пустая трата времени, уж лучше раскрыть скобки (бином Ньютона) и считать как предел суммы ряда.
Считать n-й член последовательности Фибоначчи тоже лучше не по определению, а по общей формуле для n-го члена. Сэкономим кучу памяти и ещё большую кучу времени.

А факториалы достаточно больших чисел (маленькие числа быстро заканчиваются при машинном счёте) нас учили считать по формуле Стирлинга. (Это конечно не относится к случаям вроде суммирования рядов, где факториал «сам набегает» при вычислении очередного члена ряда, и отдельно его никто не считает.)
Это всё, конечно, верно, но суть топика далеко не в этом.
Я хотел сказать, что пример с факториалом — плохой. Некоторые могут подумать, что «вот так его надо считать». А его не надо так считать.
В 99% случаев факториал надо считать так:
public class FactorialUtil {
    public static int factorial(int n) {
        return n == 0 ? 1 : n * factorial(n-1);
    }
}

И только в случае если профайлер показывает, что он занимает слишком много времени — искать более оптимальные способы.
А почему бы и нет? Или Java cannot into TCO?
Indeed, it cannot. Из соображений безопасности и чтобы всегда был стек трейс полноценный.
* не из соображений, а по модели безопасности, конечно же. Можете тут почитать.
Во-первых, в приведенном TheShock примере TCO невозможна. Видимо, вы недостаточно внимательно изучили что такое Tail Call Optimization (а это оптимизация ХВОСТОВОГО рекурсивного вызова, то есть он (вызов) должен быть последней операцией в функции.
Во-вторых, вот вам явный пример, почему TCO в Джаве таки пригодилось бы. Без нее невозможно написать функцию с кешированием в нерекурсивном виде. Только, возможно, через explicit проверку в кеше внутренних значений, а не аргументов.
А, да, хвостового вызова в этом коде нету
Рекурсия то зачем?

Потому что самый очевидный, короткий, красивый и логичный вариант. И все недостатки рекурсии тут не играют роли, потому что «только в случае если профайлер показывает, что он занимает слишком много времени — искать более оптимальные способы. „
Вы правы, но всё таки то, что JVM не поддерживает TCO, сказывается в конечном итоге.
Кому интересно, мне удалось обойти этот недостаток JVM с помощью ленивой бесконечной последовательности:

(def factorial (map second (iterate (fn[[n r]] [(inc n) (* n r)]) [1 1])))
(take factorial 20000)

Проблема в том, что при вызове факториала n оно закеширует все значения факториалов 1..n, что для n = 20000 занимает около 400 Мб памяти. Понятия не имею где может понадобится такая «оптимизация»:)
Вы действительно будете считать факториал при n = 20000? :)
Если я не ошибаюсь, max int в Java = 2,15e8, max long = 9e18, 20! = 2,43e18. То есть факториал 20 почти впритык влезает в long. Вы действительно думаете, что рекурсия даже глубиной в 20 вызовов как-нибудь существенно скажется на приложении? Если скажется, то используем кеш (псевдокод):
public class FactorialUtil {
    protected static factorialCache = new Array(20);

    protected static int countFactorial(int n) {
        return n == 0 ? 1 : n * factorial(n-1);
    }

    public static int factorial(int n) {
        if (!factorialCache[n]) {
            factorialCache[n] = countFactorial(n);
        }
        return factorialCache[n];
    }
}


Всё. Один раз посчитать 20! и всё в кеше. Если упрёмся в производительность функции вычисления факториала до реализации с кешем — не беда, 5 минут и добавили кеш.

А 20000! = 1,82e77337. Зачем вам такие значения? В каком формате вы их хранить будете?
В BigInteger, естественно.
Если нам нужен факториал от 1 до 20, то можно просто наперед просчитать все двадцать значений и сохранить в массив. Зачем еще придумывать какие-то кеширования?
Понятное дело, что факториал 20000 мне не нужен. Как и просто факториал мне не нужен в 90% приложений. Мы говорим о концептуальный возможности на простом знакомом примере, не более того.
Ну смотрите. Давайте посмотрим на спор в контексте темы.
цикл против рекурсии для вычисления факториала.

Я утверждаю, что можно использовать тот, которых по душе, потому что на малых значениях разницы при использовании рекурсии/цикла нету, а на больших значениях разницы не будет потому-что будет использоваться другой подход, например, кеширование или, даже, предподсчитанные значения, занесённые в базу данных/память.
Мне лично нравится (я провожу иногда собеседования) пример факториала именно тем, что тут хорошо видно когда вроде бы «тяжелый» подход (рекурсия типа захламляет стек) отлично подходит из-за того что мы не будет влазить в возвращаемый тип. А в случае с BigInteger скорость операций будет перевесит неудобство использование стека.

Конечно вопрос чисто теоретический и я его ставлю скорее в ряд логических задач, чем как демонстрация реального умения написания кода.
Никогда не понимал, почему рекурсивное вычисление факториала считается очевидным и логичным — цикл гораздо очевиднее.
PS
Вот для ханойских башен рекурсия — самый очевидный, короткий, красивый и логичный вариант
Никогда не понимал, почему рекурсивное вычисление факториала считается очевидным и логичным

Потому что в учебных заведениях про рекурсию рассказывают на примере факториала.
На самом деле странно, почему именно на примере факториала, а не чисел Фибоначчи, ведь как раз они определяются рекуррентно (тоже не рекурсивно, но хотя бы ближе к рекурсии :))
Если из учебного курса студент запомнил только только такое определение, а из курса разработки компиляторов не знает во что выливаев вызов метода, то думаю дальше джуниора ему нельзя и старшые колеги эту дурь вибъют лине
А после такого объяснения минимум половина студентов не понимает, зачем нужна эта дурацкая непонятная рекурсия, если можно посчитать влоб циклом.
Я вот рекурсию на примере ханойских башен изучал — гораздо нагляднее передаёт суть и смысл метода. Ещё обход дерева достаточно нагляден.
Потому что факториал по определению рекурсивный.
Вообще-то факториал по определению итеративный:
image
Ну вообще да, факториал можно определять и рекурсивно и итеративно. Видимо, кто как привык его понимать.
осмелюсь поправить


return  n < 2 ? 1 : n * factorial(n-1);

а не то при отрицательном n будет весело
Вы правы. Надо хотя-бы так.
Но правильнее, конечно, бросать исключение при неправильном аргументе.
Ага и имеем ненужныв вызов. Нафига нам лишний переход, засовывания в стек значений, вытягивание, восстановление адреса возврата, если цыклом можно посчитать? Это как пример как нельзя делать.
Преждевременная оптимизация — корень всех зол. Если вам критичны все эти замечания — кешируйте, я об этом писал выше.
А с кешем вообще без разницы, как считать. Хоть перебором.
Рекурсивный алгоритм обсчёта факториала даётся в ВУЗе не потому что он такой хороший, а потому что стоит задача на простом примере объяснить рекурсию.
Если вы стали программистом и единственное что запомнили это обсчёт факториала рекурсием то грошь цена вам как программисту.
Если вы победили в городской олимпиаде за самый быстрое решение какой-то задачи это не значит, что вы сейчас можете всем рассказывать, какие мы хреновые программисты. В большинстве случаев совершенно нету разницы, какой алгоритм использовать в плане производительности. На практике что цикл, что рекурсия будут показывать себя одинаково. Если их производительность будет не устраивать даже с кешем, то есть более быстрые алгоритмы, о чём писали ниже.

Я понимаю, что вы крутой теоретик-программист, знаете аж два способа подсчёта факториала, но в реальной жизни часто имеет смысл сделать как можно проще. И рекурсивный алгоритм кроме всех других преимуществ имеет ещё одно — он узнаваемый.
На мой взгляд это несколько извращенное понимание преждевременной оптимизации.
Подсчет факториала в цикле не сложнее и уж точно не менее понятнее чем рекурсивный, но при этом лишен проблем со стеком.
В общем, проще говоря — чтобы исправить положение, достаточно просто в конце статьи подключить алгоритм с формулой Стирлинга и не объяснять, откуда она взялась. Это не по теме статьи.

А вот что «в этом случае легко подключить любой алгоритм» — вы таким образом продемонстрируете наиболее очевидным способом.
Там есть ссылка на быстрые алгоритмы подсчёта факториала, думаю, её будет достаточно.
Хм. На правах не знающего языка: а в JAVA нет встроенного алгоритма подсчета факториала, нужен внешний?
Всегда казалось, что туда собрали всё и на все случаи жизни…
Видимо, нужно автору было писать не про Факториал, а про «Hello World» =)
Кстати насчет формулы Стирлинга. Там же вычисляется n/e в степени n. Разве перемножить числа от 1 до n будет быстрее чем n раз перемножить n?
по формуле стирлинга вы вычислите факториал любого числа n за конечное количество операций ( которое не зависит от n )
там вроде такая формула:
fac = sqrt( 2 * pi * n ) * exp( n * ln( n \ e ) );

тут мы имеем несколько операций умножения одно деление и три вызова встроенных функций
сложность алгоритма O(1)
ну а вычисление факториала через умножение:
for( i=1, fac=1; i<n; i++, fac *= i );
имеет сложность O(n)

первый вариант при n меньше сотни неточен, но зато он очень быстр по сравнению со вторым вариантом (вернее начиная с некоторого n равного k он станет быстрее второго варианта, где k зависит от платформы, языка, железа и пр)

п.с. насчет спора выше — вычислять факториал через рекурсию это бред. То что студентам объясняют что такое рекурсия на примере факториала — не значит что факториал надо вычислять через рекурсию. Оверхед на вызов функции, сохранение в стек и тд не стоит этого. Очень узкий класс задач решается рекурсией, там где не рекурсивный метод сложен и малопонятен.
А разве у этого exp( n * ln( n \ e ) ) сложность не O(n)?
exp вычисляется на уровне FPU. также как и ln
сложность у них константа
О том что в FPU забыл, это конечно быстрее. Но интересно, как оно считает такую вещь за константное время?
За константное — не знаю, могу рассказать, как найти a^b за log_2 b:
double pow(double base, int exponent) {
if (exponent == 0)
return 1;
double result = pow(base, exponent >> 1);
result *= result;
if ((exponent & 1) != 0)
result *= base;
return result;
}
Для больших n наверное имеет смысл умножение сделать одним из быстрых алгоритмов умножения.
А заключение статьи почему не переведено, где написано «It's all crap»? Просто читал статью пару дней назад и, на мой взгяд, самая важная часть как раз упущена.
Это написано в самом начале:
В этом посте высмеивается тенденция некоторых разработчиков применять существенно более сложные решения
Ок, видел начало. Хотелось еще большего высмеивания ;)
Да ладно, вдруг обидется кто. Там уже, вон, пришли ярые преверженцы ООП внизу.
Я тоже ярый приверженец ООП, но это не мешает мне смеяться над самим собой…
То, что вы над самим собой можете посмеяться, уже говорит о том, что вы приверженец не настолько ярый :)
Ничего смешного. Примерно так и пишут свежеиспеченные ООП-шники, начитавшиеся GoF-а.
UFO landed and left these words here
UFO landed and left these words here
осмелюсь предложить, что стоит вынести регистрацию класса в конфигурационный файл.

static {
FactorialAlgorithmFactory.registerAlgorithm(«recursiveAlgorithm», RecursiveFactorialImplementation.class);
}
Вообще смешно конечно, но в этой шутке только доля шутки. На самом деле неоходимо всего лишь создать интерфейс

public interface FactorialCalculator
{
    BigDecimal calculate(int n);
}


И, если свербит, наделать кучу реализаций. После этого используем любой DI-фреймворк по вкусу (Spring, Pico/Nano-container, Guice) или просто вручную в коде инжектим реализацию FactorialCalculator в другие бины.

За синглтоны подобные FactorialAlgorithmFactory и FactorialUtil давать по рукам и отправлять в ссылку — программировать на PHP
А эстеты могут предпочесть

public interface FactorialCalculator<T extends Number> {

  T calculate(int n);

}

тогда уж
public interface FactorialCalculator {

T calculate(T n);

}
а у вас объявление параметров хабрапарсер съел.
Вот зараза.
Но, думаю, идея понятна — а вдруг мы захотим посчитать факториал для чего-то большего, чем Integer.MAX_INT
главное чтоб молоко не убежало.
Нет особого смысла — сомнительно что вы сможете посчитать факториал от n большего чем (2^31 — 1)
Это почему ещё?
Может, мы тут пишем убер-фреймфорк для суперкомпьютера. С аппаратной реализацией JAVA.
У меня есть смутные ничем не подтвержденные сомнения, что во вселенной не хватит атомов для хранения такого факториала. По крайней мере не для long уж точно.
Самое большое, что я смог посчитать — это:
72306960! = 8,5e536870911
А никто не обещал возвращать точное значение.
log_2 n! < log_2 n^n = n * log_2 n. При n = 2^31 нам заведомо хватит 31*2^31 бит — меньше 8 гигабайт (а это очень грубая оценка)
Для n = 2^63 потребуется всего лишь 64 эксабайт — если всем договорится, то влезет :)
А кэширующая реализация просто обязаны быть proxy над какой-либо другой некэширующей.
Это вы вот всё серьёзно говорите, или издеваетесь?
то есть, вы считаете вполне нормальным считать факториалы, используя DI-фреймворки?
Ну, видимо, это глобально, надёжно и корпоративно до безобразия…
Я считаю ненормальным писать на Java кодеки и архиваторы. Но, если для вычислений требуется считать факториалы, и от способа реализации их расчета зависит очень многое — почему нет? Это не так трудозатратно и никаких побочных эффектов в данном конкретном случае нет.

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

К тому же факториалы тут не причем — шутка была про программистов.

Ладно, давайте не будем спорить. То, что вы говорите сейчас, вполне разумно. Однако то, как вы начали предлагать улучшения для очевидного стёба, насторожило.
Хоть и прошло уже 7 лет, все-таки вмешаюсь.

Считать факториалы используя DI-фреймворки — конечно же не стоит. А вот использовать DI-фреймворк для внедрения алгоритма подсчета факториала — уже не так глупо. При условии что DI-фреймворк в проекте используется для чего-то еще, а не только для внедрения алгоритма подсчета факториала.
UFO landed and left these words here
А еще при ленивой реализации синглтона надо использовать synchronized.
Подождите, а как же действительные и комплексные значения? Эйлер для кого старался?



и как следствие



Тут еще работы — непочатый край! :-)
UFO landed and left these words here
Спасибо за перевод и ссылку на блог автора. Пару месяцев назад искал хорошие блоги о Java, по сравнению с .NET нашел мало. А тут +1 в Гугл-ридер :)
create table factorials(
n int,
f bigtext,
primary key(n)
)

select f from factorials where n=?;

одни разок заполнить и…

но можно создать персистент обджектов и бин:)
Я в студенчестве вычислял факториал так:

...
    private static int cont(int n, int p) {
        int s=0;
        while (n!=0)
            s+=(n/=p);
        return s;
    }
      
    public static BigInteger factorial(int n) {
        BigInteger res = BigInteger.ONE;
        for (int i=2 ; i<=n; i=getNextPrime(i)) {
           int e=cont(n, i);
           res=res.multiply(BigInteger.valueOf(i).pow(e));
        }
        return res;
    }
...


Кто первый поймёт, как это работает, получит, ну скажем, плюс в карму :)

Написание реализации getNextPrime, я надеюсь, не вызовет у вас затруднений :)

Почему я тогда называл метод cont, я уже не помню, но сейчас бы я называл его по-другому.

Да, алгоритм основан на формуле, названной в честь одного французского математика.
cont вычисляет сколько раз число i (простое) входит в делители и умножает res на i возведённую в эту степень.
причем в делители не только n но и всех чисел меньше n
Хотелось бы более чёткого ответа… :)
Куда уж четче? Считаем сколько чисел делится на i, потом на i^2, итд, потом возводим i в соответствующую степень и перемножаем для всех i.

Я только немножко не уверен, что (n/p)/p будет равно n/(p*p), с учетом целочисленного деления. Надо подумать.
О, вам бы однозначно стоило перевести последние пару абзацев, в них вся суть.
Кому лень ходить по ссылкам:

So please, do us all a favor: if you have the urge to add complexity because “someday we’ll need it, I just know it!”, or because “it’s not sufficiently flexible enough” or “we need reusability in our code” or (God help us!) because it’s “cool”–just go home early. Watch some cartoons. Rent Inception on DVD.

Вольный перевод:
Пожалуйсте, сделайте нам одолжение: если вам приспичило усложнить код, с мыслями «ну, когда-нибудь это понадобится, уж я то знаю!», или потому что «эта реализация недостаточно гибкая» или «нам нужно, чтобы код был повторно используем» или же (Сохранились!) так как «это же крутотень неимоверная!» — лучше идите ка домой пораньше. Посмотрите мультиков. Скачайте DVDRip фильма «Начало».
Это был адаптированный перевод, да!)
$ perl -Mbigint -e "print do{$r=1;map{$r*=$_}(1..$ARGV[0]);$r}" 100
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Посчитать все факториалы про запас от 2 до 20000, записать в файл и читать из него, как из словаря. Делается это 1 (один) раз и на всю жизнь.
Любую проблему можно решить, внеся дополнительный уровень абстракции, кроме слишком большого числа уровней абстракции
Предвижу следующую статью: «подсчёт факториала на БрейнФаке»
Как же OSGi забыли? Мы ведь хотим расширять наше решение с помощью плагинов, содержащих новые алгоритмы вычисления факториала.
Велосипеды — зло
Синглтоны — зло
Для выбора реализации есть паттерн strategy

А так вообще позабавило (-:
Only those users with full accounts are able to leave comments. Log in, please.