Что такое алгоритмы в 1с
Если посмотреть на все эти статьи, то можно заметить, что люди, которые их пишут, фактически обижены на университеты за то, что их заставили учить много сложного материала — в виде алгоритмического анализа, сложных алгоритмов и структур данных — который им вроде бы не пригодился. По сути, авторы статей обижены на университеты из-за того, что там не смогли предсказать будущую область работы авторов и дать им только минимально нужный набор навыков. Ведь действительно, чтобы писать простенькие сайты и скрипты, не нужно особого знания алгоритмов и структур данных. Или всё-таки нужно?
Давайте подумаем, что же нужно учить программисту в университете, для того чтобы приобрести необходимые навыки для успешной карьеры. Библиотеки? Фреймворки? Они устаревают, интерфейсы к ним меняются, все они написаны чаще всего под один язык, который студенты могут и не использовать никогда в индустрии. Всех учить писать сайты? Или всех учить писать ОС? Образование должно охватывать как можно большую аудиторию и давать максимально возможный набор навыков. Программист в первую очередь должен уметь анализировать и решать проблемы – это основной навык, которым должны обзавестись выпускники факультетов информатики. Написание кода – это просто необходимый инструмент, который используется для решения задач. Кто может знать какие навыки вам понадобятся в будущем? Таким образом учить теорию – это наиболее оптимально с точки зрения образования. Полученные навыки можно применить в любой области, а выучить библиотеку или фреймворк имея хорошую базу знаний не составит большого труда. Парадоксально то, что люди задающие вопросы про нужность алгоритмов, как правило имеют какие-то знания в этой области. Я не помню ни одного человека, который не имел знаний в области теории вычислений, и с гордостью кричал об этом, утверждая, что ему они не нужны.
Итак, вы абстрактный программист в вакууме, работаете десять с лишним лет клепая сайты и решая простые однотипные задачи клиентов/компании. Вам хорошо и уютно в вашей нише, и только мучительно больно за бесцельно потраченное время в классе по теории вычислений и алгоритмическому анализу, который вам ничего не дал. По утрам закуривая сигарету за чашкой кофе, в глубине философских размышлений о бренности бытия вы задумываетесь: зачем же программистам, не решающим сложных задач, знать алгоритмы и основы анализа. Короткий ответ: чтобы быть квалифицированным специалистом и эффективно использовать доступные инструменты, включая язык, на котором вы пишите. Теория алгоритмов и анализа учит не только экзотические алгоритмы и структуры данных в виде АВЛ и красно-чёрных деревьев. Она также даёт представления о том, как эффективно организовать данные, как писать код с максимальной производительностью, где в системе возможно бутылочное горлышко и как с ним бороться. Вас ознакамливают с готовыми решениями, чтобы вы не писали велосипедов, и не бежали в гугл каждый раз, когда нужно сделать что-то нетривиальное.
А как же библиотеки? Ведь они решают столько задач! Чтобы рационально использовать библиотеки, их тоже нужно понимать. Во-первых, функции в библиотеки могут иметь побочные эффекты или поведение, которые вы не будете знать без понимания алгоритмов. Получив баг в таком случае можно долго и упорно пытаться его поймать и решить, когда можно было избежать. Во-вторых, различные инструменты и библиотеки часто нужно «настраивать» — говорить им какие алгоритмы, структуры данных и технологии использовать внутри. Без элементарных знаний вам придётся либо идти читать маны, либо выбирать наугад. В-третьих – есть множество задач, которые нельзя решить простым вызовом API библиотеки или фреймворка. Что вы будете делать в таком случае? Тратить часы на поиски возможных решений и просить помощи у друга? В-четвёртых – множество задач решается очень просто несколькими строчками кода или встроенными средствами языка. Если для решения каждого чиха вы будете тянуть библиотеку, то ваши программы будут гигантскими монстрами, занимая по сотни мегабайт и больше на диске, отжирая всю память на сервере, и при том имея довольно скудный функционал. Кроме того, наличие кучи подключенных библиотек влечёт за собой проблемы совместимости, и программа может падать случайным образом из-за странного поведения нескольких библиотек в одном проекте. Бездумное использование библиотек может привести к довольно плачевным последствиям, и разработчики, которые умеют только использовать библиотеки, но не способны решить даже простую проблему самостоятельно, никогда не будут ценится, потому что их решения будут неконкурентоспособны.
Может ли программист обойтись без знаний алгоритмов и теории анализа? Может, и таких «программистов» очень много. Только назвать их программистами можно разве что с большой натяжкой. Ко мне на собеседование приходит очень много программистов, со стажем десять-пятнадцать лет, и толком не понимающих что же они делают и почему. У них своя ниша, они ходят от компании к компании, не задерживаясь в них больше года. Как правило, у них есть небольшой набор задач, которые они могут решать, и если сделать шаг в сторону, то человек теряется и ему нужно обучить себя новым навыкам. Таких людей приглашают на проект, и от них избавляются как можно быстрее, потому что они теряют кучу времени, изобретая велосипеды и читая маны чтобы узнать то, что уже должны были знать из университета. У них как правило нет особо никакой карьеры и нестабильный заработок.
В итоге, для чего нужно знать алгоритмы и теорию анализа, если можно выполнять работу и без этих знаний? Чтобы быть квалифицированным специалистом в своей профессии, иметь карьерный рост и уважение коллег. Чтобы эффективно решать поставленные задачи и не изобретать велосипедов. Чтобы не писать монстров с огромным количеством сторонних библиотек, которые занимают сотни мегабайт на диске от отжирают кучу памяти на сервере и регулярно падают по случайной причине в зависимости от фазы луны. Чтобы эффективно и с максимальными возможностями использовать язык, на которым вы пишете. Чтобы принимать информированные и осмысленные решения по выбору библиотеки и технологии для решения проблемы. Если же ваша работа заключается в написание SQL запроса и вбивание команды в консоль, то хочу вас огорчить: вы не программист, вы – пользователь, вам действительно не нужны алгоритмы и иже с ним, и вы зря потратили время в университете потому что для такой работы достаточно закончить курсы или прочитать пару вводных книжек самостоятельно.
Разбор популярных алгоритмов сортировки массивов, реализованных на 1с. + обработка с наглядной реализацией алгоритмов.
В статье рассмотрены одни из самых популярных алгоритмов сортировки для массивов, применяемых как практически, так и в учебных целях. Сразу хочу оговориться, что все рассмотренные алгоритмы медленнее, чем метод классической сортировки массива через список значений, но тем не менее, заслуживают внимания. Текста получается много, поэтому по каждому алгоритму описываю самое основное.
1.Алгоритм "Сортировка выбором".
Является одним из самых простых алгоритмов сортировки массива. Смысл в том, чтобы идти по массиву и каждый раз искать минимальный элемент массива, обменивая его с начальным элементом неотсортированной части массива. На небольших массивах может оказаться даже эффективнее, чем более сложные алгоритмы сортировки, но в любом случае проигрывает на больших массивах. Число обменов элементов по сравнению с "пузырьковым" алгоритмом N/2, где N - число элементов массива.
Алгоритм:
1. Находим минимальный элемент в массиве.
2. Меняем местами минимальный и первый элемент местами.
3. Опять ищем минимальный элемент в неотсортированной части массива
4. Меняем местами уже второй элемент массива и минимальный найденный, потому как первый элемент массива является отсортированной частью.
5. Ищем минимальные значения и меняем местами элементы,пока массив не будет отсортирован до конца.
2.Алгоритм "Сортировка пузырьком".
Пожалуй самый известный алгоритм, применяемый в учебных целях, для практического же применения является слишком медленным. Алгоритм лежит в основе более сложных алгоритмов: "Шейкерная сортировка", "Пирамидальная сортировка", "Быстрая сортировка". Примечательно то, что один из самых быстрых алгоритмов "Быстрый алгоритм" был разработан путем модернизации одного из самых худших алгоритмов "Сортировки пузырьком"."Быстрая" и "Шейкерная" сортировки будут рассмотрены далее. Смысл алгоритма заключается в том, что самые "легкие" элементы массива как бы "всплывают" , а самые "тяжелые" "тонут". Отсюда и название "Сортировка пузырьком"
Алгоритм:
1. Каждый элемент массива сравнивается с последующим и если элемент[i] > элемент[i+1] происходит замена. Таким образом самые "легкие" элементы "всплывают" - перемещаются к началу списка,а самые тяжелые "тонут" - перемещаются к концу.
2. Повторяем Шаг 1 n-1 раз, где n - Массив.Количество ().
3.Алгоритм "Шейкерная сортировка"(Сортировка перемешиванием,Двунаправленная пузырьковая сортировка).
Алгоритм представляет собой одну из версий предыдущей сортировки - "сортировки пузырьком". Главное отличие в том, что в классической сортировке пузырьком происходит однонаправленное движение элементов снизу - вверх, то в шейкерной сортировке сначало происходит движение снизу-вверху, а затем сверху-вниз.
Алгоритм такой же, что и у пузырьковой сортировки + добавляется цикл пробега сверху-вниз.
В приведенном ниже примере, есть усовершенствование в шейкерной сортировке. В отличие от классической, используется в 2 раза меньше итераций.
4. Алгоритм "Гномья сортировка".
Алгоритм так странно назван благодаря голландскому ученому Дику Груну.
Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.
Дик Грун
Вот собственно и все описание алгоритма "Гномья сортировка". Что интересно, алгоритм не содержит вложенных циклов, а сортирует весь массив за один проход.
5. Алгоритм "Сортировка вставками".
Представляет собой простой алгоритм сортировки. Смысл заключается в том, что на каждом шаге мы берем элемент, ищем для него позицию и вставляем в нужное место.
Элементарный пример: При игре в дурака, вы тянете из колоды карту и вставляете ее в соответствующее место по возрастанию в имеющихся у вас картах. Или
в магазине вам дали сдачу 550 рублей- одна купюра 500, другая 50. Заглядываете в кошелек, а там купюры достоинством 10,100,1000. Вы вставляете купюру
достоинсвом 50р. между купюрами достоинством 10р и 100р, а купюру в 500 рублей между купюрами 100р и 1000р. Получается 10,50,100,500,1000 - Вот вам
и алгоритм "Сортировка вставками".
Таким образом с каждым шагом алгоритма, вам необходимо отсортировать подмассив данных и вставить значение в нужное место.
6. Алгортим "Сортировка слиянием".
Интересный в плане реализации и идеи алгоритм. Смысл его в том, чтобы разбивать массив на подмассивы, пока длина каждого подмассива не будет равна 1. Тогда мы утверждаем, что такой подмассив отсортирован. Затем сливаем получившиеся подмассивы воедино, одновременно сравнивая и сортируя поэлементно значения подмассивов.
p/s не смог вставить сюда рисунок с более наглядной схемой, постоянно размазывается. Зато хорошо видна в блоке скриншотов внизу. Можно посмотреть как работает алгоритм.
7. Алгортим "Сортировка Шелла".
Алгоритм назван так в честь американского ученого Дональда Шелла. По своей сути этот алгоритм является усовершенствованным алгоритмом "Сортировка вставками". Смысл алгоритма заключается в том, чтобы сравнивать не только элементы, стоящие рядом друг с другом, но и на некотором удалении. Сначало выбирается Шаг - некий промежуток, через который будут сравниваться элементы массива на каждой итерации. Обычно его определяют так:
Для первой итерации Шаг = Цел(Массив.Количество()/2), для последующих Шаг = Цел(Шаг/2). Т.е. постепенно шаг сокращается и когда Шаг будет равен 1 произойдет последние сравнение и массив будет отсортирован.
Пример:
Дан массив (10,5,3,1,14,2,7,12).
1. Шаг = 4.
Сортируем простыми вставками каждые 4 группы по 2 элемента (10,14)(5,2)(3,7)(1,12)
10 , 2 , 3 ,1, 14 , 5 , 7 ,12
2. Шаг = 2
Сортируем простыми вставками каждые 2 группы по 4 элемента (10,3,14,7)(2,1,5,12)
3 , 1 , 7 , 2 , 10 , 5 , 14 , 12
3. Шаг = 1
Сортируем простыми вставками каждую 1 группу по 8 элементов.
8. Алгортим "Быстрая сортировка".
Наиболее популярный и применяемый алгоритм на практике. Является одним из самых эффективных алгоритмов сортировки данных.
Вся суть алгоритма сводится к тому, чтобы разбить сложную задачу на маленькие и решить их по отдельности. Выбирается некая опорная точка и все значения которые меньше перебрасываются влево, все остальные вправо. Далее для каждой полученной части выполняетя тоже самое, до тех пор пока дробить части уже нельзя. В конце мы получаем множество отсортированных частей, которые необходимо просто склеить в 1 целое.
9. Классическая сортировка массива в 1с.
Передаем массив в список значений. Сортируем стандартным методом "Сортировать".
Все сортировки можно ускорить расположив код в циклах в 1 строку. Но для читабельности, оставил так.
Написал обработку в которой реализованы все вышеперечисленные алгоритмы, также поддерживается динамическая анимация процесса сортировки (Кроме стандартной сортировки 1с).
-При запуске обработки автоматически происходит формирование массива случайных чисел от 0 до 100 размерностью 100 элементов.
-Для создания другого массива необходимо нажать на кнопку "Создание ГСЧ массива ", также можно выбирать необходимый диапазон.
-Для включения динамической анимации необходимо поставить галочку на "Отобразить сортировку в диаграмме". Советую на неэффективных алгоритмах устанавливать галочку при размерности массива до 100 элементов, иначе состаритесь ждать сортировки:)
- Динамическая отрисовка процесса сортировки очень сильно снижает производительность, зато наглядно видно как работает алгоритм.
Удивительное дело. Люди, стоявшие у истоков того, что мы сейчас называем computer science, считали "алгоритм" понятием в принципе неопределяемым. Таким же, как, например, "множество". Но, в отличие от "множества". Кстати, вы много видели определений множества? Кроме совсем смешного, типа: "множество - это совокупность чего-либо" (ага, ага, а совокупность - это множество чего-либо)? В отличие от "множества", в определениях "алгорима" недостатка нет. Вы без труда найдете штук пять или шесть.
Алгоритмом называется точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи.
Алгоритм — это последовательность действий для исполнителя, записанная на формальном языке и приводящая к заданной цели за конечное время.
Алгоритм - описание конечной последовательности шагов в решении задачи, приводящей от исходных данных к требуемому результату.
Алгоритм — конечная совокупность точно заданных правил решения произвольного класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи.
Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
Алгоритм — это последовательность действий, либо приводящяя к решению задачи, либо поясняющая, почему это решение получить нельзя.
И хотя все эти определения - всего лишь чуть менее смешные, чем приведенное мной ранее определение "множества", такое упорство в общем неглупых людей наводит на мысль, что математики-основатели все-таки ошибались и определение алгоритма существует. Попробуем его найти, но сначала определимся с самим определением (извините за каламбур). Определение - это выражение некоторого сложного понятия через более простые. В идеале, оно должно состоять из одного существительного и одного прилагательного. Конечно, нечто может обладать множеством свойств, но обычно только одно из них являеся основным и определяющим. Его-то и следует выносить в определение, про все второстепенные можно спокойно забыть.
Я считаю что такое идеальное определение алгоритма есть. Математикам было сложно его найти, потому что оно, действительно лежит скорее в области физики, но оно есть. Прежде чем я вас с ним познакомлю, давайте разберемя - что не так со всеми прочими определениями.
Навскидку, можно увидеть, что почти в каждом есть слово "задача". Не знаю, как кто, но я бы не стал говорить , что "задача" это более простое понятие.
Дональд Кнут давал такое определение алгоритму:
Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность.
Здесь мы опять видим "задачу", а также целых пять свойств. Наверняка здесь что-то лишнее.
Первое свойство - "конечность". Кнут определял его так:
Алгоритм всегда должен заканчиваться после конечного числа шагов.
Ха-ха-ха. "Всех впускать, никого не выпускать" через сколько ходов должно закончиться? А ведь это - алгоритм.
Видимо, количество тех, кому приходилось писать:
в наше время достигло некоторой критической точки, поэтому статья в википедии https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC, например, вводит разделение на вычислительные и управляющие алгоритмы и утверждает, что управляющие могут работать бесконечно. И на том спасибо, но есть еще один немаловажный момент. Один из "отцов-основателей" Алан Тьюринг не только прямо утверждал, что некоторые алгоритмы могут работать бесконечно. Он еще и доказал, что у нас в общем случае нет никакого способа заранее узнать - остановиться ли когда-нибудь вот этот конкретный алгоритм в этом конкретном случае или нет. Т.е. пишешь ты пишешь циклы там, условия. И может быть это и есть самый настоящий алгоритм, а может и нет. Никто ж не знает. Как вы понимаете, это свойство можно смело выкидывать.
Второе свойство - определенность.
Каждый шаг алгоритма должен быть точно определен. Действия, которые нужно выполнить, должны быть строго и недвусмысленно определены для каждого возможного случая.
Для кого, простите, должны быть определены шаги алгоритма? Для исполнителя? Да, некоторые перефразируют этот момент у Кнута во что-то типа: "Алгоритм должен быть понятен исполнителю". Вообще, слово "должен" меня всегда настораживает. Я слишком хорошо знаю, что в этом мире никто никому ничего не должен. Но, допустим, что алгоритм именно должен, именно исполнителю и именно быть понятным. Вам понятно вот это?
А это - алгоритм из почтенного семейства алгоритмов Hello World! Он написан на некоторой разновидности брейнфака, которую я только что придумал. Понятен ли он исполнителю? А какому? Нет никакого исполнителя. Возможно он появится, если я напишу примерно шестьдесят строчек кода на C, Java или 1С. Но, скорее всего, я не стану этим заниматься. Видите в чем дело? Нам стоит признать, что алгоритм существует независимо от исполнителя. А как иначе? Алгоритм существует, пока его исполняют? А когда перестают исполнять, он исчезает?
Да, можно сказать, что этот алгоритм понятен мне, его создателю. Но это пока. Завтра я забуду, что я тут напридумывал, и что? Алгоритм исчезнет? А послезавтра я вспомню. Он возродится? Алгоритм существует независимо не только от исполнителя, но и от создателя. Иначе, как вы объясните тот факт, что Евклид, светлая ему память, уже давно прекратил делить большее на меньшее, а алгоритм Евклида все еще существует?
Алгоритм существует независимо от исполнителя и независимо от создателя. И, в принципе, может быть не понятен никому и, при этом, продолжать свое существование. Свойство определенности(понятности) можно убрать.
Третье свойство - ввод.
Алгоритм имее некоторое (возможно, равное нулю) число входных данных.
То есть, входные данные могут быть, а могут и отсутствовать (и это действительно так). Но если входные данные могут быть, а могут и не быть, то такое свойство для определения не важно.
Самое интересное четвертое свойство - вывод.
У алгоритма есть одно или несколько выходных данных.
То есть, мы должны прийти к какому то результату, решить какую-то задачу. Решить или решать постоянно (это в случае с бесконечными алгоритмами). Почему я говорю, что это свойство самое интересное? Потому что, слова "задача" или "результат" вы обнаружите в любом определении алгоритма.
Можно было бы сказать, что алгоритм - это способ решения задачи. Но это будет плохое определение. А что такое "задача"? Вот есть известный армейский алгоритм - "копать от забора и до обеда". На решение какой задачи будут направлены действия исполнителя? Могут ли существовать действия без задачи? А почему нет!
Нас невозможно сбить с пути, нам все равно, куда идти.
Можно ли описать такие действия? Ну, а какие проблемы!
"Задача", "результат", "цель" - все это лишнее, не приближает нас ни на шаг к пониманию сущности алгоритма.
Да, осталось еще пятое свойство. Но его никто, кроме автора, не воспринимал всерьез (возможно, что и автор тоже).
Эффективность. Алгоритм обычно считается эффективным, если все его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени с помощью карандаша и бумаги.
Итак у нас нет никаких пяти свойств. А также нет ни "задач", ни "результатов". Может показаться, что теперь у нас вообще ничего нет. Но это не так. Представьте себе лестницу из трех ступенек и робота с двумя ногами. Все что он может - это поставить правую или левую ногу на ступеньку под номером 1,2 или 3. Можно сказать что у нас есть всего шесть возможных команд: П1,П2,П3,Л1,Л2,Л3. Попробуйте написать алгоритм подъема снизу на самый верх этой коротенькой лестницы. У вас должно получиться что-то типа:
Есть ли какая-нибудь разница в том, с какой ноги начинать: с правой или с левой? Как вы понимаете, разницы никакой нет. Значит, можно начинать с любой ноги? С любой нельзя. Начинать надо конкретно с правой или конкретно с левой. Вы должны сделать выбор. И пока вы его не сделаете, робот будет стоять внизу.
В этом мире все имеет последствия, но не все имеет причину. Что-то когда-то начинается. У всякой цепочки причин-следствий есть первое звено. Способность создавать такое первое звено, давать начало называется волей.
У этого слова есть узкий, психобиологический смысл. И широкий, философский. Воля в широком смысле - это способность давать начало. Это - фундаментальное свойство нашего мира. В нашем примере с шагающим роботом мы сделали выбор из двух возможных вариантов. На такое элементарное, можно сказать однобитовое, проявление воли способно вообще все, начиная с фотона. Размер данной статьи не оставляет место для подробных разъяснений. Если кто заинтересуется данным вопросом, смотрите спор Бора с Энштейном, неравенства Белла и их экспериментальную проверку. Результаты последнего эксперимента, кстати, были опубликованы совсем недавно, в мае 2018 года.
Безусловно, алгоритм - это проявление воли. Но не только. Для того, чтобы создать алгоритм, мы должны сделать еще кое-что. Мы дожны дать нашей воле свободу. Освободить ее от себя. Обеспечить ее независимое существование от нас, ее родителя. В сущности, алгоритм и есть такая освобожденая от родителя воля. Освобождение от родителя (или опекуна) называетя словом "эмансипация". Поэтому окончательное определение алгоритма выглядит так:
Алгоритм - это эмансипированная воля.
Как я и обещал, здесь у нас одно существительное и одно прилагательное. Кроме того, "эмансипация" и "воля" - понятия более простые, чем определяемое. Поэтому, я нахожу это определение идеальным. Алгоритм - эмансипированная воля. Создание алгоритма - эмансипация. А человек, который занимается созданием алгоритма - эмансипатор. Мне, кстати, никогда не нравилось слово "программист". Оно мне всегда казалось каким-то ругательным. В самом деле. Если есть "ПРОграммист", значит должен быть и "ЭПИграммист". И я бы предпочел, чтобы меня называли вторым словом. Потому что я сначала думаю и только ПОТОМ ("ЭПИ") пишу ("грамма"). А "ПРОграммист" сначала ("ПРО") пишет ("грамма") и только потом думает. Чтобы никому не было обидно, следует всех, кто занимается созданием алгоритмов называть эмансипаторами. Тем более, что это слово в точности отражает то, чем они занимаются.
Наверное, каждый из нас сталкивался с ситуацией, когда нужно выполнить большой объем вычислений или передать/получить большой объем информации за ограниченный промежуток времени. А сколько из нас остановилось на последовательном алгоритме и закрыли глаза на продолжительность выполнения? Ну и что, что 20 часов ведется расчет/отправка/получение (подчеркнуть нужное) каких-то данных? Ну, я «выжал» из системы все, что можно, быстрее не получится… При этом серверное железо загружено на минимум.
На самом деле, почти всегда доступна альтернатива в виде распараллеливания выполняемой задачи. Конечно, параллельные алгоритмы несколько сложнее — балансировка нагрузки, синхронизации между потоками, а так же, в случае разделяемых ресурсов, борьба с ожиданием на блокировках и избегание deadlock’ов. Но, как правило, оно того стоит.
Об этом мы сегодня и поговорим… в контексте 1С Предприятия.
Практически во всех современных языках есть необходимый инструментарий для реализации параллелизма. Но не везде этот инструментарий удобен для использования. Кто-то скажет: «Ну и что тут сложного и не удобного? Платформенный механизм фоновых заданий в руки и вперед!». На практике оказалось не так все просто. А что если задача бизнес-критичная? Тогда нужно обеспечить, во-первых, гарантированное выполнение заданий и, во-вторых, мониторинг работы подсистемы выполнения заданий.
- администратор для проведения регламентных работ завершил все сессии;
- внешний ресурс, требуемый на момент выполнения задания, был недоступен в течении какого-то времени;
- у части заданий после очередного обновления могут появится ошибки в коде, фоновое будет остановлено по эксепшену и, кроме записи в журнал регистрации, никому ничего не сообщит.
Хочется иметь возможность гибкого управления запускаемыми заданиями с обратной связью, с учетом ошибок, с гарантированным запуском, и все это примерно с той же легкостью, какая существует в других языках и фреймворках для параллельных заданий.
Для облегчения собственной жизни была разработана универсальная библиотека, позволяющая легко создавать параллельные алгоритмы с гарантированным выполнением в среде 1С Предприятия на базе фоновых заданий.
Область применения
- Использование параллельных вычислений в автоматизации бизнес процессов;
- Параллельное выполнение запросов в долгих отчетах/обработках;
- Процессы загрузки/выгрузки данных;
- Организация нагрузочного тестирования.
Основной принцип работы
Добавляется задание очень просто — нужно указать точку входа (путь к экспортному методу с серверным контекстом в общем модуле или модуле менеджера) и кортеж с параметрами в виде структуры:
При этом происходит запись в регистр сведений мзЗадания. Первоначально задание имеет состояние Ожидает. Метод возвращает КлючЗадания для возможного отслеживания прогресса в основном клиентском потоке. Кортеж с параметрами так же расширяется свойством КлючЗадания, чтобы при выполнении задания был контекст, он иногда может быть полезен.
Далее, раз в минуту просыпается Менеджер, который первым делом проверяет исполнителей и освобождает задания, исполнители которых «умерли». Проверка заключается в следующем. Если задание в состоянии Выполняется и прописанное в качестве исполнителя фоновое не активно (удалено администратором, возникла исключительная ситуация в коде и т.д.), то задание возвращается в очередь. Для этого у задания выставляется состояние Ожидает.
Следующим шагом запрашиваются из очереди задания в соответствии с настройками балансировки нагрузки (сейчас это только ограничение на количество одновременно работающих исполнителей).
После этого Менеджер под каждое задание запускает Исполнителя. В качестве исполнителей выступают те самые фоновые задания платформы 1С.
При запуске Исполнитель делает отметку, что взял задание в работу — прописывает свой уникальный идентификатор у задания в свойстве КлючИсполнителя и выставляет состояние задания в Выполняется.
Когда задание выполнено, Исполнитель так же делает соответствующую отметку в задании — состояние Выполнено.
Для использования подсистемы в оперативном режиме есть метод ДобавитьЗаданиеВнеОчереди. При этом сразу запускается Исполнитель, минуя Менеджера, и забирает новое задание. Сигнатура такая же, как у основного метода ДобавитьЗадание. На такие задания ограничение на количество исполнителей НЕ распространяется, НО квота используется.
- У фоновых заданий вроде как есть метод отмены, но он работает для меня не прозрачно. Очень часто наблюдал картину, когда длительное фоновое задание дорабатывало до конца несмотря на отправленную команду отмены;
- Не хочется оставлять систему в неконсистентном состоянии. Кто знает, как именно написан код задания и что он делает в базе данных?
- ДождатьсяВыполнения(КлючиЗаданий, Таймаут = 5) — усыпляет текущий поток до выполнения указанного списка заданий, либо до истечения указанного времени;
- ОжидатьСостояниеЗадания(КлючЗадания, ОжидаемоеСостояние, Таймаут = 5) — усыпляет текущий поток до установления указанного состояния у задания, либо до истечения указанного времени;
- ОжидатьИзмененияСостояния(КлючЗадания, ТекущееСостояние, Таймаут = 5) — усыпляет текущий поток до изменения состояния у задания с указанного на любое другое, либо до истечения указанного времени.
Настройка
Для настройки есть специальная обработка «Управление менеджером заданий»:
- Ограничение на количество исполнителей — для балансировки нагрузки на сервере 1С. Принимает значение от 0 до 9999. При значении 0 задания в работу браться не будут.
- Глубина хранения истории (дни) — если указано значение отличное от 0, тогда подсистема сама будет чистить информацию по старым выполненным заданиям оставляя последние N дней указанных в настройке.
- Количество активных исполнителей;
- Количество заданий в очереди (в состоянии Ожидает);
- Всего активных заданий (п.1 + п.2).
Расширенный мониторинг сильно зависит от области применения и оставлен на откуп потребителям подсистемы.
Примеры использования
Использование параллельных вычислений в автоматизации бизнес процессов
Например, расчет заработной платы можно распараллелить по сотрудникам, потому что расчет зарплаты одного сотрудника, как правило, не зависит от расчета зарплаты другого сотрудника. (Приведенный код всего лишь иллюстрирует возможности подсистемы, и никак не связан с типовыми конфигурациями 1С.)
Параллельное выполнение запросов в долгих отчетах/обработках
Процессы загрузки/выгрузки данных
Организация нагрузочного тестирования
Исходники и прочее
Подсистема доступна на github/TaskManagerFor1C. CF файл открыт, так что можно ознакомиться с исходными кодами.
Подсистема разрабатывалась через тестирование (TDD), тесты доступны во внешней обработке /Тесты/Тесты_МенеджерЗаданий.epf. Для запуска тестов нужен инструментарий xUnitFor1C.
Обратная связь приветствуется. С удовольствием отвечу на все возникшие по инструменту вопросы.
Публикуем статью Павла Дубова, студента ФИВТ МФТИ, преподавателя курса Алгоритмы. Олимпиадное программирование в 1С: Клубе программистов и тренера нашей олимпиадной сборной.
Рано или поздно перед любым школьником, планирующим поступать в приличный вуз на IT-специальность, встаёт вопрос: как и к чему готовиться? Безусловно, самый банальный ответ — готовиться к ЕГЭ, доводя самоконтроль до исступлённого автоматизма, чтобы избегать ошибок в ответственные моменты. Но есть и другой путь, позволяющий не только дать себе дополнительные шансы, но и приобрести навыки, необходимые для устройства на работу в хорошие компании.
Это путь изучения алгоритмического программирования. Помимо всего вышеперечисленного, это очень увлекательно и забавно.
На данный момент существует несколько уровней олимпиад по информатике. На самом «высоком» уровне находится Всероссийская олимпиада школьников. Получение диплома на этой олимпиаде гарантирует участнику поступление в любой вуз по соответствующему профилю без экзаменов. Олимпиады других уровней в зависимости от вуза могут давать либо поступление без экзаменов, либо 100 баллов на ЕГЭ по информатике. Для таких льгот требуется набрать минимальный балл на самом ЕГЭ — обычно 65 баллов, что, в общем, при условии получения диплома труда не составляет. Распределение олимпиад по уровням каждый год публикует Минобрнауки в интернете. Так как олимпиад несколько, можно попытать успеха несколько раз и таким образом упростить себе задачу.
Так что же нужно для того, чтобы начать подготовку?
В самом плохом случае — море терпения, ибо многие вещи в подобных дисциплинах передаются «из уст в уста», и храбрец, отважно решивший штурмовать гранитную крепость в одиночку, рискует очень сильно буксовать на пути изучения. Некоторые приёмы, идеи и техники, сокращающие количество кода и потенциальных ошибок, просто-напросто не задокументированы. Важен и порядок изучения: гораздо проще разобраться, например, в алгоритмах обхода графов, понимая, что такое рекурсия.
Изучение алгоритмов у нас начинается со Стартового модуля Алгоритмов (каждый модуль длится полгода, занятия раз в неделю по два часа с перерывом), который рассчитан на тех, кто до этого вообще не имел дела с программированием. В нём подробно изучаются основы: арифметические операции, условные операторы, операторы цикла и функции, как сдавать решения задач в тестирующую систему.
Затем следуют Первый и Второй модули, в которых происходит закрепление приобретённых навыков, разбираются простые структуры данных и алгоритмы: НОД/НОК, массивы и сортировки, строки, стек и очередь, графы и обходы, метод динамического программирования.
в 3-4 модулях идёт нацеленная подготовка инструментов, часто используемых на серьёзных олимпиадах: комбинаторная генерация, наибольшая возрастающая/общая подпоследовательность, алгоритмы на графах, суммы игр, бинарный поиск, вычислительная геометрия, выпуклая оболочка, двоичная куча, деревья отрезков, хеширование.
Разумеется, не обязательно приходить именно на Стартовый модуль: если владеешь основным конструкциями языка — можно начинать сразу с Первого. Если Первый или Второй кажутся скучными и понятными — можно пропустить и их.
Для тех, кому основных занятий мало, существуют специальные сборы по 4 часа: на них идёт подготовка к конкретным соревнованиям, оттачивание техники и умения распознавать методы решения задач, нестандартное применение идей и алгоритмов.
Я занимаюсь с группами 3-4 модуля и веду сборы.
Обычно, занятия 3-4 модуля проходят так: сначала мы разбираем необходимую теорию, а затем ребята решают задачи и сдают их в тестирующую систему. Задач чаще всего около 10 — от самых простых (для развития нужного навыка) до уровня олимпиад. При этом я смотрю код как во время написания, чтобы убедиться, что процесс идёт в нужном направлении, так и после сдачи, чтобы дать советы, ускоряющие или упрощающие разработку решений в дальнейшем.
На сборах мы моделируем ситуацию на реальных олимпиадах: дано время, в течение которого нужно почти беспрерывно решать задачи. Естественно, по ходу я даю какие-то подсказки, но они в основном имеют идейный характер, или помогают правильнее вести себя на туре. По истечению времени мы подводим итоги, и каждую задачу кто-нибудь из решивших рассказывает, а затем я рассказываю нерешённые. Иногда мы посвящаем занятия важным, но не освещённым в модулях темах, например, стресс-тестированию или использованию стандартных библиотек.
У ребят на сборах нет единой задачи: скажем, в этом году двое готовились к заключительному этапу Всероссийской олимпиады, а основная масса готовилась к Московской олимпиаде, которая проводится в версиях для 7-9 и 10-11 классов. В итоге, на каждом соревновании нам удалось добиться призёрств.
Во внеучебное время Клуб тоже живёт своей жизнью: устраиваются походы в кино и на экскурсии. А я обычно гуляю с ребятами из последней у меня в этот день группы.
Бывает, что и меня учат чему-нибудь: например, как избавиться от ±1 при написании дерева отрезков, где вкуснее всего хот-доги или в каком году родилась Мария-Антуанетта. Так что скучно не бывает.
Не знаю уж, в чём тут секрет, но Клуб очень домашний. Можно найти друзей, команду по Counter-Strike, компанию для настольных игр, или устроить парочку хакатонов и с одногруппниками сделать своего Mario.
Да и голодным никто не остаётся. Наверное, это одна из причин такой атмосферы: одно дело — скоротать время, листая ленту социальной сети, а другое — отложив смартфон, кушать бутерброд и пить чай с печеньками. Тут уж обязательно с кем-нибудь познакомишься!
Читайте также: