maytonZyK_BotaN, в отбрасывании 19990 есть какая-то хитрость?

Вообще весь код работает быстрее с отбрасыванием или нет?нет. не быстрее. меня просто интересуют последние числа.

первая половина - все равно не интересна. там числитель 1, а знаменатель уменьшается.

maytonZyK_BotaNмогу сделать такое же решение, только на си или джаве.
Нет. Не надо.а я уже было начал. ну ладно

ZyK_BotaNmaytonпропущено...

Нет. Не надо.а я уже было начал. ну ладно но не забываем про экономию памяти.

при отбрасывании, нам нужно не 20000 единиц под результат, а только 10.

Смоляное ЧучелкоZyK_BotaNпервая половина - все равно не интересна. там числитель 1, а знаменатель уменьшается
Положим, всё это симметрично относительно 1/2, так что если первые 1/n, то и хвост будет состоять из ровно стольки ж (n-1)/n. я не правильно сказал. не половина дробей, а первые к чисел, где к - половина от н.

ZyK_BotaNСмоляное ЧучелкоZyK_BotaNпервая половина - все равно не интересна. там числитель 1, а знаменатель уменьшается
Положим, всё это симметрично относительно 1/2, так что если первые 1/n, то и хвост будет состоять из ровно стольки ж (n-1)/n. я не правильно сказал. не половина дробей, а первые к чисел, где к - половина от н.
и заметь, для примера н = 5.



первые элементы действительно имеют числитель 1.
а вот последние два - уже разнятся знаменателями.

Смоляное ЧучелкоЭто называется рядами... эээ... имени Склероза. Не помню, в общем, кого.
И строить можно примерно так:
начинаем с . Потом промеж любой пары, у которой сумма знаменателей не больше нашего максимума, вставляем дробь сумма числителей/сумма знаменателей:


.
При этом не надо проверять на несократимость. Может получиться быстрее.

классный метод.

вроде рулит не хило.

считает элементы для н = 2024 - мгновенно.

вот код:



правда сам вывод занимает время, поэтому для бенчмарка, первую строку можно поменять на:

а вот мне интересно, как в ghc реализована операция конкатенации(есть ли какие-то оптимизации в зависимости от контекста вычислений).

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

ведь нам по сути нужна вставка элемента в список, а вместо этого, мне приходится их канкатенировать, так как списки иммутабельны.

вернее я могу одну канкатенацию выкинуть, но она и не является накладной, так как там список состоит из одного элемента, но все же:




а вот что делать с первой канкатенацией - не знаю.

но есть не нулевая вероятность, что оптимизатор компилятора ghc понимает что от него хотят, и делает список мутабельным, так как тот виден только локально.

ZyK_BotaNа вот мне интересно, как в ghc реализована операция конкатенации(есть ли какие-то оптимизации в зависимости от контекста вычислений).
вот что встретил на рсдн по данному вопросу:

автор
Ладно, тогда разберемся "аналитически". Ну, короче, как в принципе устроен ++? Ну, например, так. Я на Эрланге напишу, мне так проще, и в принципе один хрен.


%% Вот это - достаточно понятно.
concat( [], X ) -> X;

%% Как, собственно, и вот это
concat( [ H | T ], X ) ->
[ H | concat( T, X ) ].



Как у нас будет выполняться concat( A, B) в ленивом языке? Для простоты, пусть у нас ленивые только конструкторы списка, остальное неважно.

C = concat( A, B ) имеет сложность O(1)

Пробежка по результату приведет к дополнительному ленивому вызову concat, который будет возвращать копию элемента списка H для каждого элемента А, и будет стоить столько же для элементов B. То есть, пробежка по С будет чуть дороже, чем пробежка по А или Б. Однако, налицо неплохой потенциал для оптимизации в ghc — компилятор может избежать задействования хипа, если выведет last use для элементов C. Это уже кое-что, не так ли?

D = concat( concat( A, B ), B1 ) — само по себе тоже O(1), разумеется, это не интересно.

А пробежка по D... Два накладных вызова на len( A ), один — на len( A + B ) — len( A ), и ноль на len( B1 ). Та же картина по last use для ghc.

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

Смотрим второй вариант:
D = concat( B1, concat( A, B ) )

Имеем один накладной вызов при любой вложенности подобных операций конкатенации. То есть, квадратичности нет. Прикольно, не так ли?

Будем проверять теорию экспериментом?

взято отсюда. там на тему конкатенации идет дискусс

Смоляное ЧучелкоЕсли не лень, попробуй такой ещё вариант:

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

например сколько потребляется памяти, если нужно найти последних 10 из 20000. а сколько для всех 20000

ZyK_BotaNвзято отсюда. там на тему конкатенации идет дискусс сказать то сказал, а ссылку дать забыл:
http://www.rsdn.ru/forum/decl/3389338.flat.2