11.02.2017, 12:51 | #61 |
Участник
|
|
|
11.02.2017, 14:38 | #62 |
Участник
|
За 15 лет работы на Аксапте ни разу не попадались такие задачи. Может не повезло. Как правильно некоторые написали везде в консалтинге ценятся сроки и АДЕКВАТНОСТЬ. По мне так такие задачи в консалтинге не уместны. Да они конечно полезны для общего развития. Но оценивать разработчика ЕРП систем по ним это как оценивать бойца на войне по бегу на 100 м.
|
|
|
За это сообщение автора поблагодарили: Lemming (5). |
11.02.2017, 15:45 | #63 |
Участник
|
Написал джоб, который генерирует первые 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 |
Участник
|
Цитата:
поэтому и дают эти задачи только на собеседованиях незнакомым кандидатам. ДО того, как дать реальные задачи. да, посмотрев как кандидат бегает на 100м, ЕРП-задачи ему уже могут и не давать )))) |
|
11.02.2017, 17:59 | #65 |
Участник
|
Цитата:
Цитата:
еще не все из 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. |
|
|
За это сообщение автора поблагодарили: alex55 (1). |
11.02.2017, 18:21 | #66 |
Участник
|
|
|
11.02.2017, 18:25 | #67 |
Участник
|
"в реальности" что именно?
задачи другие? да, другие. люди по другому бегают? нет, также они бегают. в том же стиле, что и на реальных задачах... или вы ожидаете от кандидатов на собеседовании именно завершенного решения ваших задач? я лично ожидал увидеть как человек решает и чего от него ждать. |
|
11.02.2017, 18:46 | #68 |
Участник
|
ок, попробую вместо строк использовать массив int64. В ближайшее время, когда почувствую вдохновение
|
|
11.02.2017, 18:57 | #69 |
Участник
|
"Большие числа" - это как раз то, о чем говорил 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 |
Участник
|
|
|
11.02.2017, 23:39 | #71 |
Участник
|
Как и предвидел Маззи, вычисление первых 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 |
Moderator
|
Цитата:
Как и предвидел Маззи, вычисление первых 10 тысяч элементов ряда фибоначчи должно занимать в Аксапте меньше одной минуты. У меня получился результат 18 секунд без вывода в окно инфолога, и 57 секунд - с выводом результата в инфолог (еще секунд 15 сам инфолог перерисовывается - я это в расчет не беру).
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 |
Участник
|
Цитата:
попробуй убрать чисто аксаптовские фишки: 1. SysOperationProgress.inccount() очень сильно замедляет, когда обновляет окно прогресса 2. Контейнер - убери. удивись сколько времени там сидит )))) |
|
12.02.2017, 00:22 | #74 |
Участник
|
Андре, а эта функция вычисляет без переполнения? Там вроде задан тип BigInteger. А это же не больше 100 элементов Фибоначчи?
|
|
|
За это сообщение автора поблагодарили: mazzy (10). |
12.02.2017, 00:24 | #75 |
Участник
|
не, не в Аксапте дело.
ты сейчас используешь bigint. именно не более 100. а Ace of Database выводит до 10000 чисел. обновлено: там и так 10000 чисел. > fibonacci |> Seq.take 10000 bigint в F# - это синоним для .net библиотеки длинных чисел System.Numeric.Biginteger. прикольно. спасибо за новое знание. Последний раз редактировалось mazzy; 12.02.2017 в 02:02. |
|
12.02.2017, 00:27 | #76 |
Участник
|
справедливости ради:
вот здесь вывели 400 чисел на bigint... вопрос - с какого числа bigint начинает врать? ) |
|
12.02.2017, 00:40 | #77 |
Участник
|
Цитата:
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 |
Участник
|
гыыыы!!!!
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.
Таким образом, Ace of Database, стоит попробовать первоначальный алгоритм, но вместо int использовать System.Numerics.BigInteger Век живи - век учись! |
|
12.02.2017, 00:48 | #79 |
Участник
|
Цитата:
но если посмотреть на листинг здесь http://www.blogs.sigristsoftware.com...-Sequence.aspx то числа далеко за 100 похожи на правду, если проверять хотя бы на последние цифры... |
|
12.02.2017, 01:11 | #80 |
Участник
|
Попробовал через System.Numerics.BigInteger
Если без преобразования результата к аксаптовскому типу str, то летает как и у Андре - не успеешь моргнуть. Для 10000 элементов. Но! Если выводить в инфолог, то надо присваивать переменной типа str. И вот тут-то для 10000 элементов Аксапта работает несколько минут. |
|
|
За это сообщение автора поблагодарили: mazzy (2). |