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

belugin · 11.02.2017, 12:51

Цитата:

Сообщение от eugene egorov

А про глубину стека пусть постановщик ТЗ думает.....

Может быть там была хвостовая рекурсия с tail call optimization

DAX.Company · 11.02.2017, 14:38

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

Ace of Database · 11.02.2017, 15:45

Написал джоб, который генерирует первые 10 тысяч чисел фибоначчи. Длина 10-тысячного числа составляет около 2000 цифр. Вообще, приблизительная длина любого n-ного числа фибоначчи составляет примерно n/5 цифр. Так как надо сложить 1+2+3+5+8 = 5 чисел, чтобы к числу прибавился новый разряд.

Джоб у меня отработал примерно за 20 минут. На генерацию одного n-ного члена ряда, у которого n близко к 10000, уходит примерно 0,2 секунды. На генерацию первой тысячи элементов ряда уходит 5-10 секунд.
Поэтому для удобства тестируйте этот джоб для 1000 элементов.
Если переписать этот джоб на языке C++ и пользоваться указателями и массивами, то быстродействие увеличится в тысячи раз. И можно будет вычислять миллионные члены ряда Фибоначчи.

X++:

static void Job119(Args _args)
{
    int fibonacciSize = 10000; //сколько надо получить чисел Фибоначчи
    str x;
    str y;
    str total;
    int i;
    SysOperationProgress    p = new SysOperationProgress();

    str sumStrings(str _a, str _b)
    {
        str ret;
        int result;
        int digit;
        int j;
        int a;
        int b;
        int n;
        ;
        for (j = (strLen(_a) > strLen(_b) ? strLen(_a) : strLen(_b)); j >= 1; j--)
        {
            n ++;
            if (strLen(_a) >= n)
                a = str2int(subStr(_a, strLen(_a) - n + 1, 1));
            else
                a = 0;
            if (strLen(_b) >= n)
                b = str2int(subStr(_b, strLen(_b) - n + 1, 1));
            else
                b = 0;
            result = digit + a + b;
            digit = result / 10;
            result = result mod 10;
            ret = int2str(result) + ret;
        }
        if (digit)
            ret = int2str(digit) + ret;
        return ret;
    }
    ;
    p.settotal(fibonacciSize);
    p.update(true);
    x = "0";
    y = "1";
    info(x);
    info(y);
    while (fibonacciSize)
    {
        p.incCount();
        p.update(true);
        fibonacciSize --;
        total = sumStrings(x, y);
        info(total);
        [x, y] = [y, total];
    }
}

**mazzy** · 11.02.2017, 17:42

Цитата:

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

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

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

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

**mazzy** · 11.02.2017, 17:59

Цитата:

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

Написал джоб, который генерирует первые 10 тысяч чисел фибоначчи.

Цепануло, видать ))))

Цитата:

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

Если переписать этот джоб на языке C++ и пользоваться указателями и массивами, то быстродействие увеличится в тысячи раз. И можно будет вычислять миллионные члены ряда Фибоначчи.

рано.
еще не все из x++ выжато.

Предложения по улучшению:
1. вполне достижим результат "меньше 1 минуты". (для измерения скорости можно отказаться от SysOperationProgress)
2. "j = (strLen(_a) > strLen(_b) ? strLen(_a) : strLen(_b))" - фи, моветон. и strlen вычисляется дважды для каждой строки. лучше j = max(strlen(_a), strlen(_b))
3. операции со строками очень медленные. и сильно нагружают сборщик мусора. лучше использовать массив
4. сложение огромных чисел - это отдельная задача для собеседований ))))) там главная хитрость - оперировать не отдельными цифрами, а группами цифр. в одном int32 легко можно хранить до 9 полноценных разрядов (числа до +2147483647). Что в совокупности с массивом вместо строки, может дать увеличение производительности раз в 10. а ведь есть еще int64 и bigint )))
5. деление - очень дорогостоящая операция ))) когда исчерпаете варианты оптимизации, попробуйте заменить деление сравнением и сложением/вычитанием. Дополнительный цикл не понадобится )))
6. особенность x++ - вызов вложенной функции в X++ выполняется непропорционально долго по сравнению с вызовом обычного метода. попробуйте переделать, сами удивитесь.
7. особенность x++ - Конейнер - это сериализация-десериализация. Контейнер очень дорогостоящая операция для банального swap. Попробуйте избавиться от контейнера.

)))))

и еще: будете играться с типами int32, int64 попробуйте разные режимы - на клиенте/на сервере. со включенным CIL и с выключенным. это тоже особенность X++

DAX.Company · 11.02.2017, 18:21

Цитата:

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

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

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

**mazzy** · 11.02.2017, 18:25

Цитата:

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

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

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

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

Ace of Database · 11.02.2017, 18:46

Цитата:

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

еще не все из x++ выжато.
и еще: будете играться с типами int32, int64 попробуйте разные режимы - на клиенте/на сервере. со включенным CIL и с выключенным. это тоже особенность X++

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

**mazzy** · 11.02.2017, 18:57

"Большие числа" - это как раз то, о чем говорил Silence в самом начале

Цитата:

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

Кеширование конечно хорошо, но бесполезно. Ибо ряд бесконечен и программа все равно упадет из-за переполнения. Или Вы предлагаете после достижения результата в N-1 знаков, где N = кол-во не влезающее в память, разбивать результат на части и обсчитывать их отдельно, после чего выводить потоком на экран? (Точнее на бумажку, так как предлагалось писать код на листе А4) А потом так же поступать и с отдельными частями результата ибо и они переполнятся. А это рекурсия.

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

Но я бы очень внимательно смотрел на повторные вычисления и на переполнение.

чтобы понять, что кандидат понимает проблему.
"на листочке" вполне хватило бы комментария
// функция применима для 30-60 первых чисел

Наивный рекурсивный код {... result = fib(n-1) + fib(n-2)} делает слишком много повторных вычислений.
для "листочка" хватило бы простого кэширования уже полученных чисел.
или изящного решения, о котором я конечно же забыл, и которое показал Андре в этой ветке - передается больше параметров в стек, но полностью и ультимативно решается вопрос повторных вычислений в рекурсии.

или решения через итерацию и хранение в памяти только двух последних чисел, как показал Ace of Database.

**mazzy** · 11.02.2017, 19:05

Цитата:

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

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

а не факт, что int64 на клиенте будет быстрее.
ведь клиент 32 разрядный. хоть и выполняется, скорее всего, на 64 разрядной машине.

Ace of Database · 11.02.2017, 23:39

Как и предвидел Маззи, вычисление первых 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

X++:

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];
    }
}

**Андре** · 11.02.2017, 23:59

Цитата:

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

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

X++:

> 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

**mazzy** · 12.02.2017, 00:22

Цитата:

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

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

Круто!!!!!

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

Ace of Database · 12.02.2017, 00:22

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

**mazzy** · 12.02.2017, 00:24

Цитата:

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

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

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

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

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

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

**mazzy** · 12.02.2017, 00:27

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

Ace of Database · 12.02.2017, 00:40

Цитата:

Сообщение от 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** · 12.02.2017, 00:45

гыыыы!!!!

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

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

**mazzy** · 12.02.2017, 00:48

Цитата:

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

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

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

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

Ace of Database · 12.02.2017, 01:11

Попробовал через System.Numerics.BigInteger
Если без преобразования результата к аксаптовскому типу str, то летает как и у Андре - не успеешь моргнуть. Для 10000 элементов.
Но!
Если выводить в инфолог, то надо присваивать переменной типа str. И вот тут-то для 10000 элементов Аксапта работает несколько минут.