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

02.11.15

Разработка - Математика и алгоритмы

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

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

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

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

Допустим, есть ряд именованных ячеек табличного документа [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.

граф порядок расчета

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4416    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7458    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8835    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7801    dusha0020    8    

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

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

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

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

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

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

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

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

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

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


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


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


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

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

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

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

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

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

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

Как твой алгоритм отреагирует на такую "ошибку"?
24. mickey.1cx 397 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 два раза, ничего не зависло, все ок.
Я к тому, что подобный подход не оптимален. Например, в конечной точке могут консолидироваться входные значения
с последующей записью в регистр.

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

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

Так же, как и рекурсия в подобной ситуации, зависнет. В контексте задачи наличие циклов в графе не учитывается,
поскольку корректность формул лежит на разработчике. При необходимости, проверка легко реализуется,
соответствующие алгоритмы (например, на основании поиска в глубину) уже разработаны.
27. minimajack 80 09.11.15 12:14 Сейчас в теме
(24) количество узлов 6, в вершину 5 зашли два раза итого рассчитали 7 узлов...а никак не минимум 2^6...вот максимум 2^M - да это возможно
30. ИНТЕГРА 25 10.11.15 17:10 Сейчас в теме
(24) ну что за ерунда! Мыслишь однобоко: "Если рекурсия, значит она так-то и так-то будет работать!" - это твое представление о ней. Нет! Она будет работать так как ты ее реализуешь. Моя рекурсия при двойном вхождении не зависает: т.к. при первом входе производится расчет и запоминается значение для этой ячейки, при повторном обращении - сразу возвращается значение (наверно и ты смог бы в графе эту ситуацию аналогично решить, но видимо не получается, либо просто не догадался)
14. minimajack 80 06.11.15 16:56 Сейчас в теме
утрировано, такое посчитает?
Формулы.Вставить("с", "5");
Формулы.Вставить("a", " если [k] тогда [с] иначе [b]-1 ");
Формулы.Вставить("b", " если [k] тогда [a] иначе [с] ");
16. mickey.1cx 397 06.11.15 17:07 Сейчас в теме
(14) minimajack,
допустим, Формулы.Вставить("a", "?([k], [с], [b]-1)");
21. minimajack 80 09.11.15 08:03 Сейчас в теме
(16) я привел псевдо цикличность...она вроде есть, но ее как бы нет.
то есть [а] зависит от [б],[с],[к]; но и [б] зависит от [а],[с],[к].
22. mickey.1cx 397 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 80 09.11.15 11:35 Сейчас в теме
(22) хорошо...почему вы указали формулу:
в то время как рекурсивный обход, как минимум O(2^N)

это же неправда.
28. mickey.1cx 397 09.11.15 13:46 Сейчас в теме
(23) minimajack,
пятница, наверное :)
на свежую голову, от О(N log N) до O(N^2)

при движении из вершины 1, поиск в ширину - 6 вершин, рекурсия - 9
(24) опередил ))
29. minimajack 80 10.11.15 12:11 Сейчас в теме
(28)
проверил на рекурсии - приблизительно такой порядок времени
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

31. ИНТЕГРА 25 10.11.15 17:22 Сейчас в теме
(29) minimajack, Теперь осталось с графом такой анализ провести и сравнить :) У ТС формул меньше изначально и за эти секунды пользователь ничего не потеряет я думаю.
33. mickey.1cx 397 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 80 15.11.15 13:48 Сейчас в теме
(33) рекурсия-рекурсии рознь. У меня после некоторых оптимизаций количество операций(расчетов) в рекурсии стало таким же как и в графе...
35. mickey.1cx 397 15.11.15 14:21 Сейчас в теме
(34) minimajack, я это прекрасно понимаю, все зависит от конкретной задачи.
Например, если предполагается обход структуры, подобной дереву значений, то рекурсия здесь предпочтительна.
Хотя бы потому, что: 1) не надо предварительно строить связи этих данных, а приступить сразу к обходу;
2) смысла определения порядка расчета тоже нет, входными параметрами текущего расчета будут являться
только значения предыдущей итерации.

В моем же случае мы имеем множество связей одной вершины с вершинами из соседних веток.
Соответственно, при увеличении количества вершин растет количество связей.
При 1356 вершинах моего графа количество связей составило 3625, отсюда и такая разница по времени выполнения.
Визуализацию графа прилагаю.
36. minimajack 80 16.11.15 10:25 Сейчас в теме
(35) еще раз повторюсь
важно: не количество формул, не количество вершин...а форма графа.
Вот пример генерации графа:
	Для 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 397 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 80 16.11.15 15:54 Сейчас в теме
(37)
после дополнительных модификаций сложность(временную) рекурсии удалось снизить еще на 12%...
[10x10] 85 мс
[20x10] 241 мс
[20x20] 608 мс
[50x50] 8800 мс
[100x100] 70000 мс

вы можете привести результаты ваших испытаний, вашим алгоритмом и таки доказать что он быстрее?
Меня интересуют накладные расходы...
Прикрепленные файлы:
18. ИНТЕГРА 25 06.11.15 17:30 Сейчас в теме
(14) minimajack, в рекурсии надо делать дополнительную проверку от циклических ссылок (причем только при сочетании условий). Интересно как графы на это отреагируют.
25. herfis 498 09.11.15 11:48 Сейчас в теме
Просто ИНТЕГРА овладел молотком, и теперь все задачи вокруг него ему кажутся гвоздями :)
Зачем нужна отвертка, если шуруп можно вбить молотком и не совершать кучу сложных вращательных движений?
К чему все эти сложности, другие инструменты и техники, если есть простое, элегантное и универсальное решение?
Не так крепко держаться будет? Подумаешь! Для современных стенок и полок вполне нормально, говорит ИНТЕГРА. И доля правды в его словах есть. Ведь вбить шуруп в самом деле намного легче и естественней, чем вкрутить гвоздь. И даже будет держать. Вполне себе универсально и просто.
ЗЫ. Извиняюсь за яд, просто в недавнем обсуждении он настаивал на рекурсивном решении для обхода дерева ссылок в БАЗЕ ДАННЫХ через точку, вместо порционного их доставания запросами сразу по нескольку уровней за раз, приводя похожие доводы. Мол раз дерево - значит тупой рекурсией и надо обходить, как завещано. И всё тут. Хоть кол на голове теши. Код мол получается простой и элегантный, а всё остальное - от лукавого. Оценкой сложности алгоритмов его не пронять. Отсутствующие знания он отметает как несущественные. Задача программистов, говорит он - писать простой и элегантный код. Оптимизация производительности, мол, должна происходить на более низких уровнях. И частично он опять-таки прав. Функциональные языки во многом такую оптимизацию и делают. А какие-нить мудрые фрейморки могли бы и на БД делать (или делают) нужную оптимизацию. Но, блин! Нельзя же закрывать глаза на реальную производительность реальных решений! И уж тем более - на разные порядки роста сложности!
32. ИНТЕГРА 25 10.11.15 17:31 Сейчас в теме
(25) herfis, (26) ну ты философ :)
К чему все эти сложности, другие инструменты и техники, если есть простое, элегантное и универсальное решение?

Ну нет в графе такой универсальности как в рекурсии. Язык 1С всяко универсальней, чем а-ля [ИмяОбласти] - в чем элегантность?
Тоже самое хотелось-бы сказать о разработчиках ЗУП. Произвольные алгоритмы в видах расчетов программируются безобразно - могли просто делать вызов "Вычислить()".
26. herfis 498 09.11.15 12:02 Сейчас в теме
Обход графа в ширину просто плохо ложится на рекурсию, т.к. используется очередь а не стек. Другими словами, рекурсия для этого - неподходящий инструмент.
А вот обход графа в глубину должен отлично лечь на рекурсию (безотносительно сабжевой задачи).
39. ИНТЕГРА 25 11.04.16 13:01 Сейчас в теме
Возникла и у меня необходимость в подобной задаче.
Пример моей реализации тут: http://infostart.ru/public/511773/
Оставьте свое сообщение