Как вычислить факториал в 1с
Фоновые задания как раз предназначаются для организации параллельных вычислений.
Задачу расчета факториала очень удобно распараллелить на несколько потоков вычислений. Причем это касается любого алгоритма для расчета факториала: классического, рекурсией или деревом. Главное разделить всю последовательность чисел на "отрезки", для каждого из которых запускать свой расчет отдельно.
В общем, сначала разделим входные данные: в алгоритме дерева используется разделение последовательности чисел пополам - еще раз пополам и т.д. Применим эту идею для своих целей.
Я решил разделить последовательность (2. ЧислоN) на 4 группы (см. Листинг 1) и расчет по каждой группе запускать в отдельном фоновом задании (см. Листинг 2).
Листинг 2. Запуск дочернего фонового задания для потока 1В файловой базе можно тестировать только одно фоновое задание. Или несколько, но они будут будут вставать в очередь и выполняться последовательно. А значит для распараллеливания файловая база не подходит.
Поэтому я развернул алгоритм на клиент-серверной базе. При этом я буду запускать сначала родительское фоновое задание (см. Листинг 3), оно в свою очередь будет запускать 4 дочерних фоновых задания (см. Листинг 4). Листинг 4 содержит все процедуры общего модуля ФоновыеПроцедуры - этого достаточно, чтобы не скачивать прилагаемый ЦФшник.
Листинг 4. Запуск 4-х дочерних фоновых заданий из процедуры-обработки родительского фонового заданияОбратите внимание на то, что я задействовал Константы для хранения промежуточных результатов. Тип Число для констант ограничен 32 разрядами, поэтому проверку на корректность расчета я проводил для небольших чисел: от 10 до 20, например.
Затем запускал расчет факториала для 50 000 и 150 000. Естественно, результат я видел такой "999 999 999 999 999 . ", но в этом случае интересно было только время работы алгоритма. Платформа 1С, насколько я осведомлен, умножает и хранит в памяти большие числа корректно, а вот с отображением больших чисел имеет проблемы.
Эпилог
Прилагаемую конфигурацию надо запускать в клиент-серверном режиме. Она содержит только общий модуль, обработку с формой для задания числа N и запуска расчета - для тестирования этого достаточно.
В файловом режиме параллельности расчетов не будет. Для завершения фоновых заданий в файловом режиме используйте таймаут (рекомендация синтакс-помощника). Решение задачи на файловой базе не проводил, поскольку цель была именно разделить потоки вычислений.
Если будете тестировать распараллеливание вычислений на базах с обычными формами, то можете использовать типовую КонсольЗаданий.epf для просмотра запущенных, завершенных заданий. Эта консоль заданий находится здесь ИТС. Консоль заданий для обычных форм
Если будете тестировать распараллеливание вычислений на базах с управляемыми формами, то используйте БСП (Библиотеку стандартных подсистем), которая содержит подсистему РегламентныеЗадания и свою консоль заданий Описание подсистем БСП. Регламентыне Задания
На платформе 8.3.15.1830 в синтакс-помощнике вы не найдете описание процедуры ФоновыеЗадания.ОжидатьЗавершения() - но в документации 1С найдете Метод ОжидатьЗавершения() считается устаревшим и не рекомендуется к использованию.
Но я его использовал, поскольку мне показалось это удобным.
Выводы:
1) ускорил расчет факториала числа
2) научился распараллеливать вычисления с помощью фоновых заданий
Собственно, это все.
Лирика, мотивация, кейсы внедрения:
Внешние обработки (не расширения!):
Специальные предложения
Я кода-то делал подобные вещи, пытаясь ускорить расчеты в серверном режиме. Отсюда у меня ряд вопросов и замечаний:
1. Мне кажется намного удобнее делать количество потоков расчета параметром для вызываемой процедуры. Ядер и потоков на каждом сервере по разному, да и соображения управления нагрузкой не надо забывать.
2. Я бы, как указал echo77 в (1), не стал в таком случае флудить 4 или сколько еще функций расчета факториала, ибо количество потоков динамическое и сколько нужно функций не понятно. Достаточно и одной.
3. Ожидать завершения фоновых заданий можно не собирая их отбором по ключу, а сразу при запуске добавлять в массив. В этом случае нам не нужно будет их потом искать и плодить лишние функции для запуска разных заданий с одним ключом.
4. Как Вы правильно заметили, константы не могут содержать результат больше 32 разрядов. Ну и количество констант не может быть динамическим, определяемым переменной числа нужных потоков. В общем как по мне константы здесь не годятся вообще. Я использовал старый добрый метод ЗначениеВФайл(), передавая имя файла для записи результата как параметр вызываемой функции фонового задания. В этом случае по завершении всех заданий я обходил файлы по списку, получал результаты и обрабатывал.
Прошу не воспринимать мои замечания, как стремление обидеть или уязвить. Пришлось когда-то заниматься этим вопросом, а раз Вы хотите разобраться, то пара-тройка советов, думаю, будет не лишней:)
Спасибо. Замечательный пример организации фоновых заданий и обработки данных в многопоточном режиме. Можно использовать и для обменов, и для перепроведений. В БСП удобно все реализовано.В Бух КОРП 3 дроблю проведение реализаций в разрезе подразделений (количество измеряется десятками) на 4 потока.
При этом 1 поток проводит 2,5 -3 часа, 4 потока - чуть больше часа. (
10000 документов в день)
Причем прибавлять ядра/потоки больше смысла нет, т.к. там уже в другом месте упирается.
(1) согласно синтакс-помощнику процедуры - обработчики фоновых заданий должны отличаться для фоновых заданий с одинаковым ключом. А ключ одинаковый мне нужен, чтобы фильтр наложить на ожидание одновременно завершающихся заданий.
В общем, я пробовал по разному - и текущий вариант оказался работоспособен.
Цитата из санткас-помощника:
Тип: Строка.
Ключ задания. Если ключ задан, то он должен быть уникальным среди ключей активных фоновых заданий, имеющих такое же имя метода, что и у данного фонового задания. (2) А что если сделать одну процедуру и разные ключи и ожидать завершения фоновых заданий с разными ключами?
(3) в теории наверное так тоже можно - программировать придется больше проверок - проверять каждый запущенный фоновый процесс по ключу
просто одно дело теория, другое дело практика - я пока тестировал ряд фраз синтакс-помощника по разному "прочитывал" и натыкался на бездействие программы.
В итоге, сейчас на практике понял некоторые нюансы. Поэтому за нюансы вашего предложенного способа ручаться не могу, комментировать тоже. Тут надо один раз попробовать.
Надеюсь на силу сообщества - каждый внесет свою лепту в раздел "параллельных вычислений".
Я кода-то делал подобные вещи, пытаясь ускорить расчеты в серверном режиме. Отсюда у меня ряд вопросов и замечаний:
1. Мне кажется намного удобнее делать количество потоков расчета параметром для вызываемой процедуры. Ядер и потоков на каждом сервере по разному, да и соображения управления нагрузкой не надо забывать.
2. Я бы, как указал echo77 в (1), не стал в таком случае флудить 4 или сколько еще функций расчета факториала, ибо количество потоков динамическое и сколько нужно функций не понятно. Достаточно и одной.
3. Ожидать завершения фоновых заданий можно не собирая их отбором по ключу, а сразу при запуске добавлять в массив. В этом случае нам не нужно будет их потом искать и плодить лишние функции для запуска разных заданий с одним ключом.
4. Как Вы правильно заметили, константы не могут содержать результат больше 32 разрядов. Ну и количество констант не может быть динамическим, определяемым переменной числа нужных потоков. В общем как по мне константы здесь не годятся вообще. Я использовал старый добрый метод ЗначениеВФайл(), передавая имя файла для записи результата как параметр вызываемой функции фонового задания. В этом случае по завершении всех заданий я обходил файлы по списку, получал результаты и обрабатывал.
Прошу не воспринимать мои замечания, как стремление обидеть или уязвить. Пришлось когда-то заниматься этим вопросом, а раз Вы хотите разобраться, то пара-тройка советов, думаю, будет не лишней:)
3. Ожидать завершения фоновых заданий можно не собирая их отбором по ключу, а сразу при запуске добавлять в массив. В этом случае нам не нужно будет их потом искать и плодить лишние функции для запуска разных заданий с одним ключом.а в остальном, все верно - и про константы и их замену на файл на жестком диске, и про параметр и одну функцию-обработчик - я уже позже домыслил реализацию, но не стал экспериментировать.
В БСП удобно все реализовано.В Бух КОРП 3 дроблю проведение реализаций в разрезе подразделений (количество измеряется десятками) на 4 потока.
При этом 1 поток проводит 2,5 -3 часа, 4 потока - чуть больше часа. (
10000 документов в день)
Причем прибавлять ядра/потоки больше смысла нет, т.к. там уже в другом месте упирается.
насколько я помню, дело не в кол-ве ядер.
и с одним ядром можно несколько рабочих процессов (потоков) запускать. за этим следит кластер серверов и платформа 1с. каждый фоновый процесс запускается в отдельном рабочем процессе.
Можно запускать, но вопрос в эффективности (я про производительность) (5) с проведением документов надо программировать непересекающиеся множества документов (записей в таблицах), чтобы не создавались блокировки записей в таблицах (документов).
все-таки принцип проведения документов - особенно расчет себестоимости - основывается на последовательном проведении документов (или фиксации факта хоз.деятельности) - поэтому параллелить именно процесс проведения документов имеет ряд ограничений и нюансов.
(5) все-таки научиться проводить документы в фоне (через фоновые задания) нельзя назвать задачей распараллеливания вычислений.
При проведении вы не ожидаете завершения фоновой задачи, чтобы произвести очередной расчет, и не используете полученные промежуточные результаты.
Для распараллеливания вычислений как раз и надо собрать все промежуточные результаты всех дочерних фоновых заданий и обработать их в родительском фоновом задании .
Для распараллеливания вам придется залезть в общий модуль конфигурации, дописать логику распараллеливания и сборки промежуточных результатов. А для типовой БП КОРП 3, я думаю это критично для последующих обновлений.
А вот запустить из внешней обработки длительную операцию перепроведения документов с отбором по подразделению - можно легко в БУХ КОРП 3.
Вы как реализовали свой метод?
Кто знает, заложена ли в БСП реализация разделения родительского фонового задания на дочерние и сборка промежуточных результатов ?
Войдите на сайт как ученик
Упражнение №4. Напишите программу, которая делает сортировку массива из предыдущего упражнения методом пузырька по возрастанию. Затем выводит отсортированный массив пользователю.
К примеру, был у нас массив: 1, 60, 20, 30, 0
После сортировки по возрастанию он будет выглядеть так: 0, 1, 20, 30, 60
В этом весь смысл. Сортировки бывают самые различные - быстрые и не очень. Но в данном задании я предлагаю вам в учебных целях воспользоваться широко известным среди программистов алгоритмом "Сортировка методом пузырька".
Суть этого алгоритма можно представить как выталкивание более лёгких пузырьков (меньших чисел) на поверхность (как можно ближе к первому элементу). В вышеприведённом примере 0 (ноль) в результате сортировки оказался вытолкнут на самый верх (крайне левая позиция, первый элемент в массиве).
Чтобы алгоритм заработал - просто перебирайте все числа массива, сравнивайте соседние и если левый сосед больше правого, меняйте их местами. Как только получится, что после очередного прохода массива вы не смогли сделать ни одной перестановки - готово. Массив отсортирован и его можно выводить пользователю.
Ещё более подробно о сортировке пузырьком можно прочитать здесь.
В эталонном решении я реализую "упрощённую" версию алгоритма (через бесконечный цикл), чтобы его суть стала понятна начинающим программистам.
Создать массив из 100 случайных чисел от 0 до 1000.Пробежаться по всем соседним числам этого массива и менять их местами,
если левый сосед больше правого, как бы выпихивая более легкие (меньшие) элементы
наверх (влево).
Снова пробежаться по всем соседним числам и менять их местами .
Снова пробежаться по всем соседним числам и менять их местами .
И так бегать пока в результате очередного "пробегания" не произойдёт ни одной перестановки. Как
только такой момент наступит, то это будет означать, что массив отсортирован и пора его
вывести пользователю.
Обработка вычисляет произвольный факториал и сумму цифр результата.
Написана просто в качестве развлечения.
Может пригодиться в качестве некоего учебного пособия.
Использовано разбиение строкового представления числа на части по N цифр (устанавливается в коде, по умолчанию выставлено в 8) и дальнейшее умножение данных частей "в столбик". Также внутри функции умножения используется сложение "в столбик" в промежуточных вычислениях.
Функции снабжены комментариями. Функция умножения подробными, сложения - общими (т.к. сложение много проще умножения).
Пользуйтесь на здоровье! =)
Т.к. теперь невозможно разместить абсолютно бесплатный файл, то прилагаю код обработки:
Специальные предложения
Функция ниже, вроде тоже вычисляет факториал. Или это немного не то?
(1) DrAku1a, а это тоже задача на переполнение - весь необходимый код уже имеется тут. Зачем же плодить лишние сущности? =)
Однозначно - ПЛЮС.
Еще бы возведение в произвольную степень, деление, просто умножение, вычисление числа Пи! и поиск простых чисел.
Кстати в поиске простых чисел есть некий подход, который позволяет пропускать те диапазоны, где простого числа не может быть.
Кстати есть интересная форма записи чисел (любых) система счисления, основанная на простых числах
Каждому разряду соответствует простое число и в разряде - 0 или 1. Таким образом любое число может быть представлено как сумма N количества РАЗНЫХ простых чисел. При этом длина записи для чисел больших порядков становится короче, чем например при использовании двоичной системы.
Почему именно 9 разрядов? - Думаю, потому, что 32-битное целое как раз укладывается в это представление и элементарные операции над частями по 9 десятичных цифр можно делать как операции над 32-битными целыми.
(6) ildarovich,
Несомненно, автор знал. Как следует из (4).
И несомненно, 1С прекрасно обрабатывает "вычисления неограниченной разрядности". Вот только при выводе результата, он, к сожалению, как это ни печально, обрезается.
Так что теории - это, конечно, хорошо, но попробовать на практике, наверное, все же стоило бы, прежде чем прозрачно намекать на бесполезность кода. ;)
И да - этот код написан и выложен сюда в образовательных целях. =) Несомненно, расчет факториала в бизнесе нафиг никому не нужен. И конечно, есть множество библиотек, которые считают его на порядки быстрее, если он, конечно, вдруг понадобился. Но вот только использование библиотек никак не поможет в, как Вы правильно выразились, "саморазвитии".
Решить данную задачу можно несколькими способами, мы рассмотрим рекурсивное вычисление факториала и циклическое.
Компилируем, запускаем и вводим любую N, которая меньше 0.
Получили ошибку, программа сообщила, что N < 0.
Запускаем и вводим любую N, которая больше или равно 0.
Нахождение факториала с помощью цикла
Для нахождения факториала напишем свою функцию, которая будет принимать значение N и возвращать результат.
Реализовать алгоритм нахождения факториала очень просто:
Что делает функция? Принимает значение N, после чего определяется переменная F, она будет хранить в себе ответ. Запускается цикл for от 1 до N, то есть переменная i будет иметь значения от 1 до N, эти значения мы используем для перемножения переменной F.
Для N=0 значение факториала равно 1. Цикл не будет вообще выполняться, т.к. i должна быть меньшей или равной N, в данном случае первое значение i=1, а N=0. Функция просто возвратит F, которая равно 1.
Для N=1 значение факториала равно 1. Цикл выполнится 1 раз, произойдет умножение F на i, а так как первое значение i = 1, то F так и останется равна 1.
Для остальных значений N цикл будет выполняться N раз, с каждой итерацией i будет увеличиваться на 1 и умножать на себя F.
Вставляем функцию в нашу программу:
Теперь проверим работу программы, для этого скомпилируем, запустим и попробуем ввести различные значения.
Пусть найдет факториал от 0
Получили значение 1. Мы знаем, что факториал от 0 равен единице, здесь программа работает верно.
Пусть найдет факториал от 1
Получили значение 1. Мы знаем, что факториал от 1 равен единице, здесь программа тоже работает верно.
Пусть найдет факториал от 5
Получили значение 120. Проверим: F = 1*2*3*4*5 = 120. Программа верно вычислила факториал.
Рекурсивное нахождение факториала
Наша функция factorial() будет принимать значение N и возвращать N*factorial(N-1). То есть будет возвращать значение N умноженное на саму себя, но только с N-1.
Код реализации рекурсивной функции нахождения факториала
Как это работает?
Допустим, N = 3. Мы передаем значение функции factorial(3), а она возвращает значение 3 * factorial(2), в свою очередь factorial(2) возвращает 2 * factorial(1), а factorial(1) возвращает 1. И теперь мы идем в обратном порядке:
factorial(2) = 2 * factorial(1) = 2 * 1 = 2;
factorial(3) = 3 * factorial(2) = 3 * 2 = 6;
Вызванная функция factorial(3) возвратит нам 6.
А factorial(0) и factorial(1) сразу вернут 1.
Вставим рекурсивную функцию в программу для нахождения факториала:
Компилируем, запускаем и проверяем.
Значение факториала для 0
Вывела 1, а мы знаем, что факториал от 0 равен 1. Значит работает верно.
Значение факториала для 1
Вывела 1, а мы знаем, что факториал от 1 равен 1. Значит работает верно.
Значение факториала для 5
Получили значение 120. Проверим:
Программа верно вычислила факториал.
Послесловие
Для вас это может быть интересно:
Программа для решения факториала на C++ : 5 комментариев
Очень полезная статья, сразу все стало понятно))Спасибо!
Я написал нечто подобное на обычном Си но столкнулся с проблемой программа корректно высчитывает факториал только до 12, можете помочь ее решить ?
может дело в том что лимит значений был превышен ?
int n_factorial(int n);
n_factorial(int n) int res=1;
for(int sucl=1; sucl<=n; sucl++) res=sucl*res;
>
return res;
>
Найти сумму 10 членов ряда, в котором an=(n!)/n2.
В качестве проекта необходимо написать программу для нахождения разности факториалов наименьшего и наибольшего чисел из N введенных с использованием структур языка JavaScript.
Вводится N(в данном случае 5) чисел: 1,2,3,4,5;
Находится наибольшее и наименьшее из них: 5 и 1 соответственно;
Вычисляется разность факториалов наименьшего и наибольшего чисел из N введенных: 1!-5!=-119
Требования к выполнению проекта: наличие написанной функции, циклов и условий.
Пожалуйста помогите решить задачу
В качестве проекта необходимо написать программу для нахождения разности факториалов наименьшего и наибольшего чисел из N введенных с использованием структур языка JavaScript.
Вводится N(в данном случае 5) чисел: 1,2,3,4,5;
Находится наибольшее и наименьшее из них: 5 и 1 соответственно;
Вычисляется разность факториалов наименьшего и наибольшего чисел из N введенных: 1!-5!=-119
Требования к выполнению проекта: наличие написанной функции, циклов и условий.
Помогите пожалуйста!!
Добавить комментарий Отменить ответ
Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.
Читайте также: