Помню дали задачку, вывести ряд Фибоначи. Нарисовал рекурсию. Не понравилось. Видать не поняли.

[mazzy]

Цитата:

Сообщение от Ace of Database

Маззи, а как вам такой вариант?

вложенные то циклы зачем? раньше был один. и это было хорошо.

и снова без комментариев в коде нет комментариев по поводу используемого типа real )
и магическая константа в коде... константу-то можно было бы и прокомментировать.

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

заодно это и было бы обоснованием для магической константы ))))

[Ace of Database]

Цитата:

Сообщение от mazzy

вложенные то циклы зачем?
.....
заодно это и было бы обоснованием для магической константы ))))

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

Константа 50 - тоже для наглядности. Просто красивое число для примера вывода первых 50 членов последовательности.

[Андре]

Прошу прощения, но не удержался:

let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I)
fibonacci |> Seq.take 50

А вот получение первых 50-ти членов на F#. Ленивое, как ты, mazzy, и хотел

[mazzy]

Some? почему some?
вернее, а что значит Some в данном контексте?

и почему целые 0, 1?
а целые в F# скольки разрядные? как F# относится к переполнению целого?

Цитата:

Сообщение от Андре

Ленивое, как ты, mazzy, и хотел

я не то, чтобы хотел.
я опасался, что построенное супер-выражение в стек ляжет.

причем лобовое решение fib(n-1)+fib(n-2) скорее всего быстро переполнит стек и в функциональном языке за счет повторных подстановок в результирующее супер-выражение.

[mazzy]

int - 32 разряда
суффикс I означает bigInt
some(a,b) означает some(tuple(a,b)), что означает nullable tuple(a,b)
tuple(a,b) в контексте функции unfold означает: a - текущее состояние, b - следующее состояние.

так? ахренеть!

еще фибоначчи на F#
https://msdn.microsoft.com/en-us/vis...n-%5Bfsharp%5D
http://www.blogs.sigristsoftware.com...-Sequence.aspx

мдя...

=========================
а как это ленивое чудо потребляет память?

[Андре]

Цитата:

int - 32 разряда
суффикс I означает bigInt
some(a,b) означает some(tuple(a,b)), что означает nullable tuple(a,b)
tuple(a,b) в контексте функции unfold означает: a - текущее состояние, b - следующее состояние.

так? ахренеть!

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

0I,1I - как ты правильно заметил, что BigInteger, а точнее, обертка вот над этой .NET структурой: https://msdn.microsoft.com/ru-ru/lib...v=vs.110).aspx

Цитата:

The T:System.Numerics.BigInteger type is an immutable type that represents an arbitrarily large integer whose value in theory has no upper or lower bounds.

fun (x, y) -> Some(x, (y, x + y))

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

Эта функция (как видно по ее названию) противоположна более популярной функции fold (которая в python называется reduce, а в C# LINQ - aggregate):

Цитата:

Seq.fold (fun acc elem -> acc + elem) 0 seq

Здесь мы сворачивает последовательность в одно число путем указания функции - "как именно это делать - суммировать". Вот LINQ:

Цитата:

seq.Aggregate(0, (acc, elen) => acc + elem);

unfold - противоположна - из неких начальных значений обратно разворачивает последовательность.

Теперь про Some - я там выше написал, что эта функция "постарается" вернуть очередное значение. Но компилятор понимает, что это не всегда возможно. И хочет, чтобы ты это понимал и не забывал и предлагает использовать тебе "option type" - аналог монады MayBe из других языков программирования.

[mazzy]

Цитата:

Сообщение от Андре

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

угу.
http://coub.com/view/b8if4
)

[DAX.Company]

За 15 лет работы на Аксапте ни разу не попадались такие задачи. Может не повезло. Как правильно некоторые написали везде в консалтинге ценятся сроки и АДЕКВАТНОСТЬ. По мне так такие задачи в консалтинге не уместны. Да они конечно полезны для общего развития. Но оценивать разработчика ЕРП систем по ним это как оценивать бойца на войне по бегу на 100 м.

[mazzy]

Цитата:

Сообщение от DAX.Company

Но оценивать разработчика ЕРП систем по ним это как оценивать бойца на войне по бегу на 100 м.

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

да, посмотрев как кандидат бегает на 100м, ЕРП-задачи ему уже могут и не давать ))))

[DAX.Company]

Цитата:

Сообщение от mazzy

да, посмотрев как кандидат бегает на 100м, ЕРП-задачи ему уже могут и не давать ))))

В реальности то не так)

[mazzy]

Цитата:

Сообщение от DAX.Company

В реальности то не так)

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

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

[Ace of Database]

Как и предвидел Маззи, вычисление первых 10 тысяч элементов ряда фибоначчи должно занимать в Аксапте меньше одной минуты. У меня получился результат 18 секунд без вывода в окно инфолога, и 57 секунд - с выводом результата в инфолог (еще секунд 15 сам инфолог перерисовывается - я это в расчет не беру). Для 40 тысяч элементов джоб выполняется 2 с половиной минуты без вывода в инфолог.

Если закомментировать строку кода "info(total2str());", то получится результат без вывода в инфолог, который работает 18 секунд.

Данный джоб может без переполнения вычислить порядка 1000*18*5 = 90000 чисел Фибоначчи. Если надо вычислить большее количество, то надо переопределить макрос #define.maxSize(1000).

В качестве хранения одного числа используется массив из 1000 чисел int64. В одном элементе массива хранится число длиной до 18 знаков.В среднем, после каждого 5-го числа разряд увеличивается на 1. Поэтому и такая формула для лимита 1000*18*5 = 90000

static void Job120(Args _args)
{
    int fibonacciSize = 10000;
    #define.maxSize(1000)
    int64 x[#maxSize];
    int   xSize = 1;
    int64 y[#maxSize];
    int   ySize = 1;
    int64 total[#maxSize];
    int   totalSize = 1;
    int64 over;
    int64 maxInt64 = 1000000000000000000; //значение int64, удвоение которого не приведет к переполнению
    #define.int64x0(18) //столько нулей в значении int64, удвоение которого не приведет к переполнению
    SysOperationProgress    p = new SysOperationProgress();
    int   c;

    //суммирует массивы x и y, записывает результат в массив total
    void sumInt64Array()
    {
        int64 result;
        int64 digit;
        int j;
        int64 a;
        int64 b;
        int n;
        ;
        totalSize = 1;
        for (j = max(xSize, ySize); j >= 1; j--)
        {
            n ++;
            if (xSize >= n)
                a = x[n];
            else
                a = 0;
            if (ySize >= n)
                b = y[n];
            else
                b = 0;

            result = digit + a + b;
            over = result - maxInt64;
            digit = 0;
            if (over > 0)
            {
                result -= maxInt64;
                while(over > 0)
                {
                    digit ++;
                    over -= maxInt64;
                }
            }

            total[n] = result;
        }
        totalSize = n;
        if (digit)
        {
            totalSize ++;
            total[totalSize] = digit;
        }
    }

    str total2str()
    {
        int i;
        str ret;
        str s;
        int len;
        ;
        for (i = totalSize; i >= 1; i--)
        {
            s = strfmt("%1", total[i]);
            if (i < totalSize)
            {
                len = strLen(s);
                if (len < #int64x0)
                    s = strFmt("%1%2", strRep("0", #int64x0 - len), s);
            }
            ret += s;
            //ret = strFmt("%1%2", ret, s);
        }
        return ret;
    }
    ;
    p.settotal(fibonacciSize);
    p.update(true);
    x[1] = 0;
    y[1] = 1;
    info(strfmt("1: %1", x[1]));
    info(strfmt("2: %1", y[1]));
    c = 2;
    fibonacciSize -= 2;
    while (fibonacciSize > 0)
    {
        p.incCount();
        p.update(true);
        fibonacciSize --;
        sumInt64Array();
        c ++;
        info(strFmt("%1: %2", c, total2str()));
        [x, y] = [y, total];
        [xSize, ySize] = [ySize, totalSize];
    }
}

[mazzy]

Цитата:

Сообщение от Ace of Database

У меня получился результат 18 секунд без вывода в окно инфолога,

Круто!!!!!

попробуй убрать чисто аксаптовские фишки:
1. SysOperationProgress.inccount() очень сильно замедляет, когда обновляет окно прогресса
2. Контейнер - убери. удивись сколько времени там сидит ))))

[Андре]

Цитата:

Как и предвидел Маззи, вычисление первых 10 тысяч элементов ряда фибоначчи должно занимать в Аксапте меньше одной минуты. У меня получился результат 18 секунд без вывода в окно инфолога, и 57 секунд - с выводом результата в инфолог (еще секунд 15 сам инфолог перерисовывается - я это в расчет не беру).

Я понимаю, что c Ax сравнивать не очень честно, но:

> let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I);;
val fibonacci : seq<System.Numerics.BigInteger>

> #time;;
--> Timing now on

> fibonacci |> Seq.take 10000 |> Seq.iteri (printf "%3i - %A");;

// тут я не стал копировать набор чисел
Real: 00:00:03.454, CPU: 00:00:02.265, GC gen0: 27, gen1: 27, gen2: 0

[Ace of Database]

Андре, а эта функция вычисляет без переполнения? Там вроде задан тип BigInteger. А это же не больше 100 элементов Фибоначчи?

[mazzy]

Цитата:

Сообщение от Андре

Я понимаю, что c Ax сравнивать не очень честно, но

не, не в Аксапте дело.
ты сейчас используешь bigint. именно не более 100.
а Ace of Database выводит до 10000 чисел.

Андре, ты сравни с алгоритмом на 10тыс чисел

обновлено:
там и так 10000 чисел.
> fibonacci |> Seq.take 10000

bigint в F# - это синоним для .net библиотеки длинных чисел System.Numeric.Biginteger.
прикольно. спасибо за новое знание.

[mazzy]

справедливости ради:
вот здесь вывели 400 чисел на bigint...
вопрос - с какого числа bigint начинает врать? )

[Ace of Database]

Цитата:

Сообщение от mazzy

справедливости ради:
вот здесь вывели 400 чисел на bigint...
вопрос - с какого числа bigint начинает врать? )

На SQL максимальный bigint равен 9223372036854775807
http://stackoverflow.com/questions/7...nted-by-bigint

bigint начинает врать с 94-го числа.
92-е число 4660046610375530309
93-е число 7540113804746346429
94-е число 12200160415121876738 -уже не влезает в bigint

[mazzy]

Цитата:

Сообщение от Ace of Database

bigint начинает врать с 94-го числа.
92-е число 4660046610375530309
93-е число 7540113804746346429
94-е число 12200160415121876738 -уже не влезает в bigint

угу. у меня тоже эта мысль была первой.

но если посмотреть на листинг здесь
http://www.blogs.sigristsoftware.com...-Sequence.aspx
то числа далеко за 100 похожи на правду, если проверять хотя бы на последние цифры...

[mazzy]

гыыыы!!!!

bigint - это не 8 bytes, -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
bigint - это и есть реализация длинных чисел в .net

https://msdn.microsoft.com/ru-ru/lib...v=vs.110).aspx

Цитата:

The T:System.Numerics.BigInteger type is an immutable type that represents an arbitrarily large integer whose value in theory has no upper or lower bounds.

а также разбор внутреннего устройства https://habrahabr.ru/post/207754/

Таким образом, Ace of Database, стоит попробовать первоначальный алгоритм, но вместо int использовать System.Numerics.BigInteger

Век живи - век учись!