AXForum  
Вернуться   AXForum > Прочие обсуждения > Курилка
All
Забыли пароль?
Зарегистрироваться Правила Справка Пользователи Сообщения за день Поиск Все разделы прочитаны

 
 
Опции темы Поиск в этой теме Опции просмотра
Старый 11.02.2017, 12:51   #61  
belugin is offline
belugin
Участник
Аватар для belugin
Сотрудники Microsoft Dynamics
Лучший по профессии 2017
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии 2011
Лучший по профессии 2009
 
4,010 / 2149 (80) +++++++++
Регистрация: 16.01.2004
Адрес: Москва
Цитата:
Сообщение от eugene egorov Посмотреть сообщение
А про глубину стека пусть постановщик ТЗ думает.....
Может быть там была хвостовая рекурсия с tail call optimization
Старый 11.02.2017, 14:38   #62  
DAX.Company is offline
DAX.Company
Участник
 
198 / 60 (3) ++++
Регистрация: 24.11.2016
За 15 лет работы на Аксапте ни разу не попадались такие задачи. Может не повезло. Как правильно некоторые написали везде в консалтинге ценятся сроки и АДЕКВАТНОСТЬ. По мне так такие задачи в консалтинге не уместны. Да они конечно полезны для общего развития. Но оценивать разработчика ЕРП систем по ним это как оценивать бойца на войне по бегу на 100 м.
За это сообщение автора поблагодарили: Lemming (5).
Старый 11.02.2017, 15:45   #63  
Ace of Database is offline
Ace of Database
Участник
Аватар для Ace of Database
 
700 / 525 (19) +++++++
Регистрация: 14.10.2004
Написал джоб, который генерирует первые 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];
    }
}

Последний раз редактировалось Ace of Database; 11.02.2017 в 15:59.
За это сообщение автора поблагодарили: mazzy (2).
Старый 11.02.2017, 17:42   #64  
online
mazzy
Administrator
Аватар для mazzy
Most Valuable Professional
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
28,759 / 3627 (178) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Цитата:
Сообщение от DAX.Company Посмотреть сообщение
Но оценивать разработчика ЕРП систем по ним это как оценивать бойца на войне по бегу на 100 м.
именно.
поэтому и дают эти задачи только на собеседованиях незнакомым кандидатам.
ДО того, как дать реальные задачи.

да, посмотрев как кандидат бегает на 100м, ЕРП-задачи ему уже могут и не давать ))))
Старый 11.02.2017, 17:59   #65  
online
mazzy
Administrator
Аватар для mazzy
Most Valuable Professional
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
28,759 / 3627 (178) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Цитата:
Сообщение от 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++

Последний раз редактировалось mazzy; 11.02.2017 в 18:36.
Старый 11.02.2017, 18:21   #66  
DAX.Company is offline
DAX.Company
Участник
 
198 / 60 (3) ++++
Регистрация: 24.11.2016
Цитата:
Сообщение от mazzy Посмотреть сообщение
да, посмотрев как кандидат бегает на 100м, ЕРП-задачи ему уже могут и не давать ))))
В реальности то не так)
Старый 11.02.2017, 18:25   #67  
online
mazzy
Administrator
Аватар для mazzy
Most Valuable Professional
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
28,759 / 3627 (178) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Цитата:
Сообщение от DAX.Company Посмотреть сообщение
В реальности то не так)
"в реальности" что именно?
задачи другие? да, другие.
люди по другому бегают? нет, также они бегают. в том же стиле, что и на реальных задачах...

или вы ожидаете от кандидатов на собеседовании именно завершенного решения ваших задач?
я лично ожидал увидеть как человек решает и чего от него ждать.
Старый 11.02.2017, 18:46   #68  
Ace of Database is offline
Ace of Database
Участник
Аватар для Ace of Database
 
700 / 525 (19) +++++++
Регистрация: 14.10.2004
Цитата:
Сообщение от mazzy Посмотреть сообщение
еще не все из x++ выжато.
и еще: будете играться с типами int32, int64 попробуйте разные режимы - на клиенте/на сервере. со включенным CIL и с выключенным. это тоже особенность X++
ок, попробую вместо строк использовать массив int64. В ближайшее время, когда почувствую вдохновение
Старый 11.02.2017, 18:57   #69  
online
mazzy
Administrator
Аватар для mazzy
Most Valuable Professional
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
28,759 / 3627 (178) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
"Большие числа" - это как раз то, о чем говорил Silence в самом начале
Цитата:
Сообщение от Silence Посмотреть сообщение
Кеширование конечно хорошо, но бесполезно. Ибо ряд бесконечен и программа все равно упадет из-за переполнения. Или Вы предлагаете после достижения результата в N-1 знаков, где N = кол-во не влезающее в память, разбивать результат на части и обсчитывать их отдельно, после чего выводить потоком на экран? (Точнее на бумажку, так как предлагалось писать код на листе А4) А потом так же поступать и с отдельными частями результата ибо и они переполнятся. А это рекурсия.
Нет, я бы не предлагал и не предполагал, что кандидат начнет решать задачу для любого огромного числа. Но если кандидат уж взялся.

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

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

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

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

Последний раз редактировалось mazzy; 11.02.2017 в 19:14.
Старый 11.02.2017, 19:05   #70  
online
mazzy
Administrator
Аватар для mazzy
Most Valuable Professional
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
28,759 / 3627 (178) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Цитата:
Сообщение от Ace of Database Посмотреть сообщение
ок, попробую вместо строк использовать массив int64. В ближайшее время, когда почувствую вдохновение
а не факт, что int64 на клиенте будет быстрее.
ведь клиент 32 разрядный. хоть и выполняется, скорее всего, на 64 разрядной машине.
Старый 11.02.2017, 23:39   #71  
Ace of Database is offline
Ace of Database
Участник
Аватар для Ace of Database
 
700 / 525 (19) +++++++
Регистрация: 14.10.2004
Как и предвидел Маззи, вычисление первых 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];
    }
}

Последний раз редактировалось Ace of Database; 12.02.2017 в 01:35.
За это сообщение автора поблагодарили: mazzy (10), Lemming (5).
Старый 11.02.2017, 23:59   #72  
Андре is offline
Андре
Moderator
Сотрудники компании GMCS
 
2,374 / 451 (20) +++++++
Регистрация: 03.12.2001
Цитата:
Как и предвидел Маззи, вычисление первых 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 (2), Ace of Database (5).
Старый 12.02.2017, 00:22   #73  
online
mazzy
Administrator
Аватар для mazzy
Most Valuable Professional
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
28,759 / 3627 (178) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Цитата:
Сообщение от Ace of Database Посмотреть сообщение
У меня получился результат 18 секунд без вывода в окно инфолога,
Круто!!!!!

попробуй убрать чисто аксаптовские фишки:
1. SysOperationProgress.inccount() очень сильно замедляет, когда обновляет окно прогресса
2. Контейнер - убери. удивись сколько времени там сидит ))))
Старый 12.02.2017, 00:22   #74  
Ace of Database is offline
Ace of Database
Участник
Аватар для Ace of Database
 
700 / 525 (19) +++++++
Регистрация: 14.10.2004
Андре, а эта функция вычисляет без переполнения? Там вроде задан тип BigInteger. А это же не больше 100 элементов Фибоначчи?
За это сообщение автора поблагодарили: mazzy (10).
Старый 12.02.2017, 00:24   #75  
online
mazzy
Administrator
Аватар для mazzy
Most Valuable Professional
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
28,759 / 3627 (178) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Цитата:
Сообщение от Андре Посмотреть сообщение
Я понимаю, что c Ax сравнивать не очень честно, но
не, не в Аксапте дело.
ты сейчас используешь bigint. именно не более 100.
а Ace of Database выводит до 10000 чисел.

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

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

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

Последний раз редактировалось mazzy; 12.02.2017 в 02:02.
Старый 12.02.2017, 00:27   #76  
online
mazzy
Administrator
Аватар для mazzy
Most Valuable Professional
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
28,759 / 3627 (178) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
справедливости ради:
вот здесь вывели 400 чисел на bigint...
вопрос - с какого числа bigint начинает врать? )
Старый 12.02.2017, 00:40   #77  
Ace of Database is offline
Ace of Database
Участник
Аватар для Ace of Database
 
700 / 525 (19) +++++++
Регистрация: 14.10.2004
Цитата:
Сообщение от 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 (2).
Старый 12.02.2017, 00:45   #78  
online
mazzy
Administrator
Аватар для mazzy
Most Valuable Professional
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
28,759 / 3627 (178) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
гыыыы!!!!

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

Век живи - век учись!
Старый 12.02.2017, 00:48   #79  
online
mazzy
Administrator
Аватар для mazzy
Most Valuable Professional
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
28,759 / 3627 (178) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Цитата:
Сообщение от Ace of Database Посмотреть сообщение
bigint начинает врать с 94-го числа.
92-е число 4660046610375530309
93-е число 7540113804746346429
94-е число 12200160415121876738 -уже не влезает в bigint
угу. у меня тоже эта мысль была первой.

но если посмотреть на листинг здесь
http://www.blogs.sigristsoftware.com...-Sequence.aspx
то числа далеко за 100 похожи на правду, если проверять хотя бы на последние цифры...
Старый 12.02.2017, 01:11   #80  
Ace of Database is offline
Ace of Database
Участник
Аватар для Ace of Database
 
700 / 525 (19) +++++++
Регистрация: 14.10.2004
Попробовал через System.Numerics.BigInteger
Если без преобразования результата к аксаптовскому типу str, то летает как и у Андре - не успеешь моргнуть. Для 10000 элементов.
Но!
Если выводить в инфолог, то надо присваивать переменной типа str. И вот тут-то для 10000 элементов Аксапта работает несколько минут.
За это сообщение автора поблагодарили: mazzy (2).
 

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход

Рейтинг@Mail.ru
Часовой пояс GMT +3, время: 16:36.
Powered by vBulletin® v3.8.5. Перевод: zCarot
Контактная информация, Реклама.