gifts2017

Определение порядка расчета связанных формул

Опубликовал Михаил Андрияшкин (mickey.1cx) в раздел Программирование - Практика программирования

Пару лет назад возникла идея реализовать некий аналог таблицы Excel на основе табличного документа 1С. Главной задачей подобной разработки было создание алгоритма, позволяющего по формулам определить связи ячеек документа и их порядок расчета. Позже приоритеты сместились, и разработку пришлось забросить. Но необходимость реализации Excel-подобного интерфейса ввода все таки возникла, и теоретические наработки наконец-то превратились в работающий код.
На реальном проекте с помощью такой методики удалось реализовать обработку расчета плана производства, суммарное количество формул составило около тысячи (от 70 строк, 12 месяцев + итоги), порядок расчета связанных областей при изменении ячейки достигал 260 элементов.

Общая концепция заключается в том, что связи областей, используемых в формулах, представляются в виде ориентированного графа. Для определения порядка расчета формул используется способ обхода графа "поиск в ширину". Теперь перейдем к практической реализации.

Допустим, есть ряд именованных ячеек табличного документа [a..g] и определены формулы расчета:
b = a + 1
c = a + f
d = a * c + e
g = b + d

Тогда связь ячеек можно представить в виде графа:

Для демонстрации метода я сделал небольшую обработку:

&НаСервере
Процедура ТестНаСервере()
 
 Результат.Очистить();
 
 Вершины = Новый Соответствие;
 Формулы = Новый Соответствие;
 //формирование списка формул
 Формулы.Вставить("b", "[a]+1");
 Формулы.Вставить("c", "[a]+[f]");
 Формулы.Вставить("d", "[a]*[c]+[e]");
 Формулы.Вставить("g", "[b]+[d]");
 
 ЧтениеДОМ = Новый ПостроительDOM; 
 ЧтениеФормулы = Новый ЧтениеXML;
 
 Для Каждого Формула Из Формулы Цикл
  
  ТекущаяВершина = Формула.Ключ;
  ТекущаяФормула = Формула.Значение;
  
  ЗначениеВершины = Вершины[ТекущаяВершина];
  Если ЗначениеВершины = Неопределено Тогда
   СписокСвязей = Новый СписокЗначений;
   ЗначенияФормулы = Новый СписокЗначений;
   Вершины.Вставить(ТекущаяВершина, Новый Структура("Формула, СписокСвязей, ЗначенияФормулы", ТекущаяФормула, СписокСвязей, ЗначенияФормулы));
  Иначе
   ЗначениеВершины.Формула = ТекущаяФормула;
   ЗначенияФормулы = ЗначениеВершины.ЗначенияФормулы;
  КонецЕсли;
  
  //первый вариант обнаружения имени области был через поиск по строке символов "[", "]"
  ЧтениеФормулы.УстановитьСтроку(ПолучитьПредставлениеФормулыXML(ТекущаяФормула));
  ПредставлениеФормулы = ЧтениеДОМ.Прочитать(ЧтениеФормулы);
  Разыменователь = Новый РазыменовательПространствИменDOM(ПредставлениеФормулы);
  РезультатПоиска = ПредставлениеФормулы.ВычислитьВыражениеXPath("//param", ПредставлениеФормулы, Разыменователь);
  
  ПолучитьСледующий = Истина;
  Пока ПолучитьСледующий Цикл
   ЭлементРезультата = РезультатПоиска.ПолучитьСледующий();
   Если ЭлементРезультата = Неопределено Тогда
    ПолучитьСледующий = Ложь;
   Иначе
    ВершинаФормулы = ЭлементРезультата.ТекстовоеСодержимое;
    ДобавитьСвязьВершины(Вершины, ВершинаФормулы, ТекущаяВершина);
    ЗначенияФормулы.Добавить(ВершинаФормулы);
   КонецЕсли;
  КонецЦикла;
  
 КонецЦикла;
 
 ПоместитьВоВременноеХранилище(Вершины, АдресКэш); 
 ТипЧисло = Новый ОписаниеТипов("Число", Новый КвалификаторыЧисла(15, 2));
 
 Для СтрокаДокумента = 1 По 2 Цикл
  Сч = 1;
  Для Каждого ЭлементСтруктуры Из Вершины Цикл
   ОбластьДокумента = Результат.Область(СтрокаДокумента, Сч);
   Если СтрокаДокумента = 1 Тогда
    ОбластьДокумента.Текст = ЭлементСтруктуры.Ключ;
   Иначе
    ИмяОбласти = ЭлементСтруктуры.Ключ;
    //пришлось добавить подчеркивание к имени области, 
    //при установке ОбластьДокумента.Имя = "d" имя не присваивается
    ОбластьДокумента.Имя = "_" + ИмяОбласти;
    ОбластьДокумента.СодержитЗначение = Истина;
    ОбластьДокумента.УстановитьЭлементУправления(Тип("ПолеВводаФормы"));
    ОбластьДокумента.ТипЗначения = ТипЧисло;
    Если НЕ ЭлементСтруктуры.Значение.ЗначенияФормулы.Количество() Тогда
     ОбластьДокумента.Защита = Ложь;
     ОбластьДокумента.ЦветФона = WebЦвета.Желтый;
    КонецЕсли;
    
   КонецЕсли;
   Сч = Сч + 1;
  КонецЦикла;
 КонецЦикла;
 
КонецПроцедуры

&НаСервере
Функция ПолучитьПредставлениеФормулыXML(ТекстФормулы)
 
 ПредставлениеФормулы = СтрЗаменить(ТекстФормулы, "(", "<group>");
 ПредставлениеФормулы = СтрЗаменить(ПредставлениеФормулы, ")", "</group>");
 ПредставлениеФормулы = СтрЗаменить(ПредставлениеФормулы, "[", "<param>");
 ПредставлениеФормулы = СтрЗаменить(ПредставлениеФормулы, "]", "</param>");
 
 Возврат "<formula>" + ПредставлениеФормулы +  "</formula>";
 
КонецФункции // ПолучитьПредставлениеФормулыXML()

&НаСервере
Процедура ДобавитьСвязьВершины(Вершины, Знач Вершина1, Знач Вершина2)
 
 ЗначениеВершины = Вершины[Вершина1];
 Если ЗначениеВершины = Неопределено Тогда
  СписокСвязей = Новый СписокЗначений;
  СписокСвязей.Добавить(Вершина2);
  Вершины.Вставить(Вершина1, Новый Структура("Формула, СписокСвязей, ЗначенияФормулы",, СписокСвязей, Новый СписокЗначений));
 Иначе
  ЗначениеВершины.СписокСвязей.Добавить(Вершина2);
 КонецЕсли;
 
КонецПроцедуры // ДобавитьСвязьВершины()

&НаКлиенте
Процедура Тест(Команда)
 ТестНаСервере();
КонецПроцедуры

&НаСервере
Процедура ПриСозданииНаСервере(Отказ, СтандартнаяОбработка)
 
 АдресКэш = ПоместитьВоВременноеХранилище(Неопределено, УникальныйИдентификатор);
 
КонецПроцедуры

&НаКлиенте
Процедура РезультатПриИзмененииСодержимогоОбласти(Элемент, Область)
 
 Области = Результат.Области;
 ИмяОбласти = СтрЗаменить(Область.Имя, "_", "");
 
 Вершины = ПолучитьИзВременногоХранилища(АдресКэш);
 
 РасчетОбласти = Вершины[ИмяОбласти];
 Если РасчетОбласти = Неопределено Тогда
  Возврат;
 КонецЕсли;
 
 СписокСвязей = РасчетОбласти.СписокСвязей;
 Очередь = Новый СписокЗначений;
 Очередь.ЗагрузитьЗначения(СписокСвязей.ВыгрузитьЗначения());
 ПорядокРасчета = Новый СписокЗначений;
 
 Пока Очередь.Количество() Цикл
  
  ЭлементОчереди = Очередь[0];
  Вершина = ЭлементОчереди.Значение;
  ПорядокРасчета.Добавить(Вершина);
  Очередь.Удалить(ЭлементОчереди);
  
  СписокОчереди = Вершины[Вершина].СписокСвязей.ВыгрузитьЗначения();
  Для Каждого ВершинаОчереди Из СписокОчереди Цикл
   
   ЭлементСписка = Очередь.НайтиПоЗначению(ВершинаОчереди);
   Если НЕ ЭлементСписка = Неопределено Тогда
    Очередь.Удалить(ЭлементСписка);
   КонецЕсли;
   ЭлементСписка = ПорядокРасчета.НайтиПоЗначению(ВершинаОчереди);
   Если НЕ ЭлементСписка = Неопределено Тогда
    ПорядокРасчета.Удалить(ЭлементСписка);
   КонецЕсли;
   Очередь.Добавить(ВершинаОчереди);
  КонецЦикла;
  
 КонецЦикла;
 
 Для Каждого ВершинаПорядка Из ПорядокРасчета Цикл
  
  Вершина = Вершины[ВершинаПорядка.Значение];
  Если Вершина = Неопределено Тогда
   Продолжить;
  КонецЕсли;
  
  Формула = Вершина.Формула; 
  Если Формула = Неопределено Тогда
   Продолжить;
  КонецЕсли;
  
  Формула = СтрЗаменить(Формула, "[", "Области[""_");
  Формула = СтрЗаменить(Формула, "]", """].Значение");
  Области["_" + ВершинаПорядка.Значение].Значение = ВычислитьРезультат(Формула, Области);
  
 КонецЦикла;
 
КонецПроцедуры

&НаКлиенте
Функция ВычислитьРезультат(Формула, Области)

 Перем Результат;
 
 Выполнить("Результат = " + Формула);
 
 Возврат Результат;

КонецФункции // ВычислитьРезультат()

Запускаем на выполнение и введем в область "а" единицу. 


В отладчике можно посмотреть список связей области и порядок расчета.


Корректность порядка расчета можно проверить по вышеприведенной схеме графа.


По результатам обработки получаем следующие значения в связанных ячейках.


Порядок расчета для области "e":


Соответственно, для области "f":


Результаты расчета можно проверить по изначальным формулам, либо в Excel.



 

Скачать файлы

Наименование Файл Версия Размер Кол. Скачив.
Демонстрация порядка расчета
.epf 7,81Kb
05.11.15
0
.epf 7,81Kb 0 Скачать

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Андрей Кайгородов (mszsuz) 02.11.15 03:39
Стало интересно :) Можно и проигнорировать порядок:
Т = Новый Структура;
Т.Вставить("Б", "Вычислить(Т.А) + 1");
Т.Вставить("Ц", "Вычислить(Т.А) + Вычислить(Т.Ф)");
Т.Вставить("Д", "Вычислить(Т.А) * Вычислить(Т.Ц) + Вычислить(Т.Е)");
Т.Вставить("Г", "Вычислить(Т.Б) + Вычислить(Т.Д)");
Т.Вставить("А", 1);
Т.Вставить("Е", 2);
Т.Вставить("Ф", 3);
Сообщить(Вычислить(Т.Г));
...Показать Скрыть
2. Михаил Андрияшкин (mickey.1cx) 02.11.15 09:29
(1) mszsuz, идея интересная, спасибо.
Только в вашем примере происходит расчет для одной конечной точки.
В контексте моей задачи, при изменении одной ячейки количество конечных точек заранее неизвестно.
Соответственно, необходимо определить правильный порядок расчета промежуточных значений ячеек табличного документа.
3. Александр Отр (ИНТЕГРА) 03.11.15 21:33
Ндаааа.... ты долго писал это чудо? Про рекурсию не слышал? (сейчас полезут оппоненты из другой ветки, там меня шапками чуть не закидали - рекурсию обсуждали)
4. Михаил Андрияшкин (mickey.1cx) 04.11.15 02:33
(3) ИНТЕГРА,
Шапок мешок несу.
Зайду к соседу, скажу
Про рекурсию.

Может более предметно попробуешь, а то вроде бы и сказал, а как-то объемно очень получилось, в пространство.
5. Александр Отр (ИНТЕГРА) 04.11.15 07:21
(4) mickey.1cx, во-первых не стоило изобретать свой синтаксис. В данной задаче это не оправдано и слишком накладно. Зачем?
Во-вторых (следуя из п.1) вычислять каждую ячейку тебе надо командой: "Вычислить(<ТекстЯчейки>)".
Ну и в-третьих - у тебя должна в контексте выражения п.2 быть определена функция а-ля "ВычислитьЯчейку(<АдресОбласти>)". Она должна рекурсивно вызвать саму-себя (тебе для этого даже делать по-моему ничего не надо).

В результате тебе надо просто удалить 95% твоего кода, а вместо него продумать заглушку - чтоб рекурсия не зацикливалась - это очень просто.
6. Михаил Андрияшкин (mickey.1cx) 04.11.15 11:58
(5) ИНТЕГРА, ок, спасибо.
Возможно, стоило сделать пример более приближенный к рабочему варианту.
Свой синтаксис необходим. Реальные формулы расчета изначально зашиты в шаблон и имеют вид:
СуммаРаздела([ПланПродаж]), ИтогСтроки([ПланПродаж]), {КоэффициентРоста} * [ПланПродаж], ([ФактПродажиНал] + [ФактПродажиБезнал]) / [ПланПродаж] и другие интересные варианты.
Соответственно, мне нужно как то выделять независимые параметры, параметры значений 1С.
После получения данных заполнения происходит привязка параметров 1С к идентификаторам (например ПланПродаж_c4e33f6c-26ba-4979-aa32-36dd798db4d2) , формирование окончательного набора формул на основе шаблона, выполняется процедура именования необходимых ячеек табличного документа.

По поводу рекурсии. Сейчас расчет ячеек происходит в цикле
Для Каждого ВершинаПорядка Из ПорядокРасчета Цикл

Можно конечно код цикла обернуть в рекурсию, брать первый элемент списка с последующим его удалением и проверкой на количество элементов списка при каждой итерации. Но зачем?
7. Александр Отр (ИНТЕГРА) 05.11.15 07:57
(6)
Можно конечно код цикла обернуть в рекурсию

Конечно-же не об этом речь. Во-первых тебе на надо будет делать парсинг твоих выражений, а этот цикл вообще не понадобится.

Выражения станут более функциональными, т.к. в них можно будет использовать все возможности языка, в том числе и вызовы доступных функций конфигурации. Я думаю в твоем варианте это недоступно.
8. Михаил Андрияшкин (mickey.1cx) 05.11.15 23:51
(7) ИНТЕГРА,
Любые функции доступны, если правильно подготовить формулу. Смотри функцию ВычислитьРезультат
Выполнить("Результат = " + Формула)

Такие конструкции без проблем отработают:
Формулы.Вставить("c", "Мин([a],[f])");

Либо
Формулы.Вставить("c", "МояСуперФункция([a],[f])");

Проверено.
9. Михаил Андрияшкин (mickey.1cx) 06.11.15 08:37
(7) ИНТЕГРА, по поводу рекурсивного вычисления,
оно имеет смысл для обхода деревьев


в случае рекурсивного обхода графа вершина 5 будет рассчитана два раза


При изменении вершины 2 нет смысла рекурсивного обхода вершины 4 к вершине 6, пока не будет рассчитана вершина 5


Может быть и такое
10. Александр Отр (ИНТЕГРА) 06.11.15 10:53
(9) очень плохо, что ты сам увидел как это реализовать через рекурсию. Достаточно добавить проверку: если ячейка уже расчитывалась ранее - брать ее значение сразу. Графом я как раз не представляю как решить такую задачу. От может ты в ответ меня просветишь.

Кстати лет 10 наверно назад писал обработку для 1С77, которая выгружает в текстовый документ данные из базы. Затем этой-же обработкой можно было загрузить в идентичную конфигурацию эти данные. Работала она с любыми метаданными, код был около 500 строк. Структура базы 1С сам понимаешь - гораздо сложнее твоих примеров. Я ее продавал даже по интернету, тогда инфостарта вроде небыло, через проклаб.ру торговля шла, по 300р за шт :)
11. Михаил Андрияшкин (mickey.1cx) 06.11.15 15:16
(10) ИНТЕГРА, фишка как раз в том, что при рекурсивном расчете ячейку необходимо пересчитывать каждый раз,
поскольку только при последнем обходе все вышестоящие ячейки будут рассчитаны корректно.
Попробуй рекурсивно обойти второй рисунок. При левом проходе 1-2-5 вершина 5 получит еще не рассчитанное значение вершины 3, поскольку
эта вершина будет обрабатываться, после окончания обхода левой ветки.
Есть простой алгоритм расчета порядка обхода графа, основанный на списках смежности вершин.
Для этого как раз в формуле через [ ] выделяются вершины графа, по которым строятся списки смежности ячеек.
При обработке изменения ячеек на основе этих списков происходит построение порядка расчета.
В начале статьи я писал, что порядок расчета на реальной разработке достигал 260 элементов, общее количество формул около 1000, в зависимости от настроек.
На таком графе рекурсивный обход будет явно не самой быстрой операцией.
Теорию для обхода графа брал здесь, поиск в ширину.
12. Евгений Ванжула (minimajack) 06.11.15 16:27
(11) mickey.1cx, давайте начнем исходить из задачи...
возьмем два варианта решения
1. Автора
2. Рекурсивный
И проверим где быстрее будет решение.
13. Александр Отр (ИНТЕГРА) 06.11.15 16:46
(11) mickey.1cx, я-же тебе писал - у меня база выгружалась. Там логика гораздо запутанней, чем у тебя. и "Формулы" с вложенностью более 100 уровней достигали. Мне кажется рекурсия для таких задач проще в реализации, ни в коем случае не утверждаю что твой способ плох (для этого надо изучать тему, а мне лень :) ). Просто предлагаю альтернативный вариант реализации. Если тебе интересна эта тема - попробуй на нем реализовать, увидишь, что кода станет в разы меньше. За пару часов можно набросать рабочий алгоритм. Вопрос универсальности: а сможет твой алгоритм обхода графа выгрузить БД в текстовый файл?
(12) Скорость на задачах автора вряд ли будет отличаться, а вот кода, значительно больше у него.
14. Евгений Ванжула (minimajack) 06.11.15 16:56
утрировано, такое посчитает?
Формулы.Вставить("с", "5");
Формулы.Вставить("a", " если [k] тогда [с] иначе [b]-1 ");
Формулы.Вставить("b", " если [k] тогда [a] иначе [с] ");
...Показать Скрыть
15. Михаил Андрияшкин (mickey.1cx) 06.11.15 17:03
(12) minimajack, можно конечно проверить и на практике.
А можно использовать такую штуку, как О-нотация оценки сложности алгоритмов.
Исходя из этой теории, алгоритм формирования порядка очереди расчета с последующим обходом
будет иметь сложность О(N log N) + О(N), в то время как рекурсивный обход, как минимум O(2^N)
На графике явно видно. как будет расти количество операций при увеличении количества элементов.
16. Михаил Андрияшкин (mickey.1cx) 06.11.15 17:07
(14) minimajack,
допустим, Формулы.Вставить("a", "?([k], [с], [b]-1)");
18. Александр Отр (ИНТЕГРА) 06.11.15 17:30
(14) minimajack, в рекурсии надо делать дополнительную проверку от циклических ссылок (причем только при сочетании условий). Интересно как графы на это отреагируют.
19. Михаил Андрияшкин (mickey.1cx) 06.11.15 20:29
(13) ИНТЕГРА, ок, постараюсь подвести итоги :) Каждый алгоритм хорош, там где хорош.

В моей задаче оптимален как раз обход графа в ширину.
Можно даже вручную пройтись по вышеприведенным картинкам, смоделировать обход классической
рекурсии и посмотреть сколько вершин будут обсчитаны повторно и сколько раз. Поэтому рекурсия
в контексте данной задачи даже не рассматривается. Соответственно, "избыточность" кода
приемлема, поскольку в моем случае это будет работать быстрее. Это не мое заявление,
существуют математические методы оценки скорости и сложности алгоритмов.

По поводу выгрузки, теоретически можно и реализовать. Только вот здесь как раз использовать граф смысла нет,
поскольку после получения выборки необходимо затратить ресурсы на его построение. Поэтому проще эту выборку
рекурсивно обойти, пропуская обработанные ссылки.

(18) графы бывают различных видов, в моем случае используется ориентированный, без циклических ссылок.
Если таковая появляется, то это означает ошибку в логической структуре формул. Попробуй провернуть
такое в Excel - ругнется.
20. Александр Отр (ИНТЕГРА) 08.11.15 18:37
(19) mickey.1cx,
смоделировать обход классической
рекурсии и посмотреть сколько вершин будут обсчитаны повторно и сколько раз. Поэтому рекурсия
в контексте данной задачи даже не рассматривается

Логику не наблюдаю в этом умозаключении. Ты не понимаешь что я предлагаю и понять, видимо не хочешь. Еще раз повторюсь: Повторно при рекурсии нельзя обсчитывать, иначе зависнет! Яж говорю - не настаиваю, просто предложил более компактный вариант решения, ради которого не требуется месяцы разработки. Но с другой стороны ты освоил теорию графов, это похвально, хотя все-же не практично в контексте данной задачи.

Если таковая появляется, то это означает ошибку в логической структуре формул

Как твой алгоритм отреагирует на такую "ошибку"?
21. Евгений Ванжула (minimajack) 09.11.15 08:03
(16) mickey.1cx, я привел псевдо цикличность...она вроде есть, но ее как бы нет.
то есть [а] зависит от [б],[с],[к]; но и [б] зависит от [а],[с],[к].
22. Михаил Андрияшкин (mickey.1cx) 09.11.15 10:48
(21) minimajack, пардон, просмотрел.
На реальной задаче я сделал просто, добавил символ "#" для значений ячеек, которые участвуют в расчете, но пропускаются при повторном появлении в очереди расчета.

	Формулы.Вставить("с", "5");
	Формулы.Вставить("a", "?([k], [с], [#b]-1)");
	Формулы.Вставить("b", "?([k], [#a], [с])");	
...Показать Скрыть






Процедура ДобавитьСвязьВершины(Вершины, Знач Вершина1, Знач Вершина2)
	
	ПропускРекурсии = Найти(Вершина1, "#");
	ЗначениеВершины = Вершины[Вершина1];
	Если ЗначениеВершины = Неопределено Тогда
		СписокСвязей = Новый СписокЗначений;
		СписокСвязей.Добавить(Вершина2,, ПропускРекурсии);
		Вершины.Вставить(СтрЗаменить(Вершина1, "#", ""), Новый Структура("Формула, СписокСвязей, ПараметрыФормулы, ЗначенияФормулы",, СписокСвязей, Новый СписокЗначений, Новый СписокЗначений));
	Иначе
		ЗначениеВершины.СписокСвязей.Добавить(Вершина2,, ПропускРекурсии);
	КонецЕсли;
	
КонецПроцедуры // ДобавитьСвязьВершины()
...Показать Скрыть


	ПропускРекурсии = Новый Массив;
	Пока Очередь.Количество() Цикл
		ЭлементОчереди = Очередь[0];
		Вершина = ЭлементОчереди.Значение;
		ПорядокРасчета.Добавить(Вершина);
		Очередь.Удалить(ЭлементОчереди);
		СписокОчереди = Вершины[Вершина].СписокСвязей;//.ВыгрузитьЗначения();
		Для Каждого ВершинаОчереди Из СписокОчереди Цикл
			ВершинаЗначение = ВершинаОчереди.Значение;
			ЭлементСписка = Очередь.НайтиПоЗначению(ВершинаЗначение);
			Если НЕ ЭлементСписка = Неопределено Тогда
				Очередь.Удалить(ЭлементСписка);
			КонецЕсли;
			Если ВершинаОчереди.Пометка Тогда
				Если ПропускРекурсии.Найти(ВершинаЗначение) = Неопределено Тогда
					ПропускРекурсии.Добавить(ВершинаЗначение);
				Иначе
					Продолжить;
				КонецЕсли;
			КонецЕсли;
			ЭлементСписка = ПорядокРасчета.НайтиПоЗначению(ВершинаОчереди);
			Если НЕ ЭлементСписка = Неопределено Тогда
				ПорядокРасчета.Удалить(ЭлементСписка);
			КонецЕсли;
			Очередь.Добавить(ВершинаЗначение);
		КонецЦикла;
	КонецЦикла;
...Показать Скрыть


		Формула = СтрЗаменить(Формула, "[", "Области[""_");
		Формула = СтрЗаменить(Формула, "]", """].Значение");
		Формула = СтрЗаменить(Формула, "#", "");
		Области["_" + ВершинаПорядка.Значение].Значение = ВычислитьРезультат(Формула, Области);
...Показать Скрыть

23. Евгений Ванжула (minimajack) 09.11.15 11:35
(22) хорошо...почему вы указали формулу:
в то время как рекурсивный обход, как минимум O(2^N)

это же неправда.
24. Михаил Андрияшкин (mickey.1cx) 09.11.15 11:42
(20) ИНТЕГРА,
Допустим, есть функция f(), использующая рекурсивный вызов самой себя по спискам смежности вершин.
Рассмотрим работу этой функции на простом примере.

При вызове f(1) вызываются последовательно f(2) и f(3).
Для f(2), соответственно, f(4) и f(5), для f(3) - f(5) и f(6).
Пожалуйста, рекурсивно мы зашли в вершину 5 два раза, ничего не зависло, все ок.
Я к тому, что подобный подход не оптимален. Например, в конечной точке могут консолидироваться входные значения
с последующей записью в регистр.

Понять, видимо, хочу. Поэтому и потрудился рассмотреть вариант с рекурсией. Более того,
привел аргументы в пользу ее неоптимальности в текущем контексте.
На чем же основаны твои выводы, мне непонятно. Извини, не телепат.

Как твой алгоритм отреагирует на такую "ошибку"?

Так же, как и рекурсия в подобной ситуации, зависнет. В контексте задачи наличие циклов в графе не учитывается,
поскольку корректность формул лежит на разработчике. При необходимости, проверка легко реализуется,
соответствующие алгоритмы (например, на основании поиска в глубину) уже разработаны.
25. Сан Саныч (herfis) 09.11.15 11:48
Просто ИНТЕГРА овладел молотком, и теперь все задачи вокруг него ему кажутся гвоздями :)
Зачем нужна отвертка, если шуруп можно вбить молотком и не совершать кучу сложных вращательных движений?
К чему все эти сложности, другие инструменты и техники, если есть простое, элегантное и универсальное решение?
Не так крепко держаться будет? Подумаешь! Для современных стенок и полок вполне нормально, говорит ИНТЕГРА. И доля правды в его словах есть. Ведь вбить шуруп в самом деле намного легче и естественней, чем вкрутить гвоздь. И даже будет держать. Вполне себе универсально и просто.
ЗЫ. Извиняюсь за яд, просто в недавнем обсуждении он настаивал на рекурсивном решении для обхода дерева ссылок в БАЗЕ ДАННЫХ через точку, вместо порционного их доставания запросами сразу по нескольку уровней за раз, приводя похожие доводы. Мол раз дерево - значит тупой рекурсией и надо обходить, как завещано. И всё тут. Хоть кол на голове теши. Код мол получается простой и элегантный, а всё остальное - от лукавого. Оценкой сложности алгоритмов его не пронять. Отсутствующие знания он отметает как несущественные. Задача программистов, говорит он - писать простой и элегантный код. Оптимизация производительности, мол, должна происходить на более низких уровнях. И частично он опять-таки прав. Функциональные языки во многом такую оптимизацию и делают. А какие-нить мудрые фрейморки могли бы и на БД делать (или делают) нужную оптимизацию. Но, блин! Нельзя же закрывать глаза на реальную производительность реальных решений! И уж тем более - на разные порядки роста сложности!
26. Сан Саныч (herfis) 09.11.15 12:02
Обход графа в ширину просто плохо ложится на рекурсию, т.к. используется очередь а не стек. Другими словами, рекурсия для этого - неподходящий инструмент.
А вот обход графа в глубину должен отлично лечь на рекурсию (безотносительно сабжевой задачи).
27. Евгений Ванжула (minimajack) 09.11.15 12:14
(24) mickey.1cx, количество узлов 6, в вершину 5 зашли два раза итого рассчитали 7 узлов...а никак не минимум 2^6...вот максимум 2^M - да это возможно
28. Михаил Андрияшкин (mickey.1cx) 09.11.15 13:46
(23) minimajack,
пятница, наверное :)
на свежую голову, от О(N log N) до O(N^2)

при движении из вершины 1, поиск в ширину - 6 вершин, рекурсия - 9
(24) опередил ))
29. Евгений Ванжула (minimajack) 10.11.15 12:11
(28) mickey.1cx,
проверил на рекурсии - приблизительно такой порядок времени
1600 переменных
матрица 40х40 - формул 1600
связь вида по строкам = значение левой ячейки + номер строки + значение ячейки слева вверху
изменение первой ячейки приводит к перерасчету 800 связанных формул - и занимает это все 3 секунды...уровень глубины ~600

связь вида по строкам = значение левой ячейки + номер строки + значение ячейки вверху - это намного тяжелее

матрица 40х40 - изменение первой ячейки приводит к перерасчету 1 560 переменных - и занимает это все 8 секунд...уровень глубины ~1560
матрица 70х18 - изменение первой ячейки приводит к перерасчету 1 190 переменных - и занимает это все 6,3 секунд...уровень глубины ~1190
матрица 14х20 - изменение первой ячейки приводит к перерасчету 260 переменных - и занимает это все 0,63 секунд...уровень глубины ~260

30. Александр Отр (ИНТЕГРА) 10.11.15 17:10
(24) mickey.1cx, ну что за ерунда! Мыслишь однобоко: "Если рекурсия, значит она так-то и так-то будет работать!" - это твое представление о ней. Нет! Она будет работать так как ты ее реализуешь. Моя рекурсия при двойном вхождении не зависает: т.к. при первом входе производится расчет и запоминается значение для этой ячейки, при повторном обращении - сразу возвращается значение (наверно и ты смог бы в графе эту ситуацию аналогично решить, но видимо не получается, либо просто не догадался)
31. Александр Отр (ИНТЕГРА) 10.11.15 17:22
(29) minimajack, Теперь осталось с графом такой анализ провести и сравнить :) У ТС формул меньше изначально и за эти секунды пользователь ничего не потеряет я думаю.
32. Александр Отр (ИНТЕГРА) 10.11.15 17:31
(25) herfis, (26) ну ты философ :)
К чему все эти сложности, другие инструменты и техники, если есть простое, элегантное и универсальное решение?

Ну нет в графе такой универсальности как в рекурсии. Язык 1С всяко универсальней, чем а-ля [ИмяОбласти] - в чем элегантность?
Тоже самое хотелось-бы сказать о разработчиках ЗУП. Произвольные алгоритмы в видах расчетов программируются безобразно - могли просто делать вызов "Вычислить()".
33. Михаил Андрияшкин (mickey.1cx) 14.11.15 21:46
(29) minimajack, наконец то дошли руки проверить на действующей разработке, количество вершин 1356, формул 1092.
Тест по три замера на самом длинном участке.
Граф:
Итераций, очередь 413
Итераций, порядок 205
Время, мс 132
Итераций, очередь 413
Итераций, порядок 205
Время, мс 128
Итераций, очередь 413
Итераций, порядок 205
Время, мс 234

Рекурсия:
Итераций, порядок 2 912
Время, мс 2 471
Итераций, порядок 2 912
Время, мс 2 500
Итераций, порядок 2 912
Время, мс 2 042
34. Евгений Ванжула (minimajack) 15.11.15 13:48
(33) mickey.1cx, рекурсия-рекурсии рознь. У меня после некоторых оптимизаций количество операций(расчетов) в рекурсии стало таким же как и в графе...
35. Михаил Андрияшкин (mickey.1cx) 15.11.15 14:21
(34) minimajack, я это прекрасно понимаю, все зависит от конкретной задачи.
Например, если предполагается обход структуры, подобной дереву значений, то рекурсия здесь предпочтительна.
Хотя бы потому, что: 1) не надо предварительно строить связи этих данных, а приступить сразу к обходу;
2) смысла определения порядка расчета тоже нет, входными параметрами текущего расчета будут являться
только значения предыдущей итерации.

В моем же случае мы имеем множество связей одной вершины с вершинами из соседних веток.
Соответственно, при увеличении количества вершин растет количество связей.
При 1356 вершинах моего графа количество связей составило 3625, отсюда и такая разница по времени выполнения.
Визуализацию графа прилагаю.
36. Евгений Ванжула (minimajack) 16.11.15 10:25
(35) mickey.1cx, еще раз повторюсь
важно: не количество формул, не количество вершин...а форма графа.
Вот пример генерации графа:
	Для k=1 По 20 Цикл
		Для n=1 По 20 Цикл
			Если k=1 Тогда
				ЗначениеФормулы = "=" + n;
			Иначе
				ЗначениеФормулы = "=" + n + " + [""R" + Строка(n) + "C" + Строка(k-1) + """]";
				Если n > 1 Тогда
					ЗначениеФормулы = ЗначениеФормулы + " + [""R" + Строка(n-1) + "C" + Строка(k) + """]";
				КонецЕсли;
			КонецЕсли;
		КонецЦикла;
	КонецЦикла;
...Показать Скрыть

элементарная сетка - по факту ужасный вариант для рекурсии...
[10x10] 100 мс - в среднем затрачивается на перерасчет при изменении ячейки C1R1
[20x10] 260 мс - в среднем затрачивается на перерасчет при изменении ячейки C1R1
[20x20] 700 мс - в среднем затрачивается на перерасчет при изменении ячейки C1R1
[50x50] 9800 мс - в среднем затрачивается на перерасчет при изменении ячейки C1R1
[100x100] 80000 мс - в среднем затрачивается на перерасчет при изменении ячейки C1R1
Визуализация [20x20]:

Аппроксимация:
Прикрепленные файлы:
37. Михаил Андрияшкин (mickey.1cx) 16.11.15 15:33
(36) minimajack, спасибо за проделанную работу.
Могу лишь добавить, что формулы, в моем случае, определяют количество связей вершины результата с вершинами входных параметров.
Зная количество вершин и связей можно сделать предварительную оценку сложности формы графа без его визуализации.
Для обычного дерева количество связей всегда будет равно n-1, сложность (n-1)/n -> 1
Сетка 10х10 - 180, 20х20 - 760, 30х30 - 1740, для n^2 = 2*(n^2 - n), сложность 2*(n^2 - n) / n^2 = 2(1 - 1/n) -> 2
Сложность формы моего получается 3625 / 1356 = 2,67.
38. Евгений Ванжула (minimajack) 16.11.15 15:54
(37) mickey.1cx,
после дополнительных модификаций сложность(временную) рекурсии удалось снизить еще на 12%...
[10x10] 85 мс
[20x10] 241 мс
[20x20] 608 мс
[50x50] 8800 мс
[100x100] 70000 мс

вы можете привести результаты ваших испытаний, вашим алгоритмом и таки доказать что он быстрее?
Меня интересуют накладные расходы...
Прикрепленные файлы:
39. Александр Отр (ИНТЕГРА) 11.04.16 13:01
Возникла и у меня необходимость в подобной задаче.
Пример моей реализации тут: http://infostart.ru/public/511773/
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа