Циклы в ориентированном графе. #163520

История такая. Внедряем 1С:Бухгалтерия предприятия 8.0 ред 1.5. Документ "Закрытие месяца" проводится 1.5 (полтора)часа. Стали разбираться что к чему. Выяснилось разработчики решили оптимизировать расчет бухгалтерской средней. Просматривают все перемещения и если материал (товар) движется между складами по циклу (возвращается на исходный склад), то этот оборот исключается из расчета бухгалтерской средней. Вопрос спецам по алгоритмам (прежде всего NS)насколько это оптимально? В процедуре РасчитатьСписаниеПоСредней есть цикл, так тело этого цикла у нас выполняется 70 000 000 (Семьдесят миллионов)раз. PS а как это тему затолкнуть в секцию "Математика и алгоритмы"

да ладно полтора часа раз в месяц это немного

Мне кажется, что так средняя считается не более оптимально, а "более правильно" Кажется, есть смысл отключить это нафик

Сколько движений? Сколько документов? Сколько раз в среднем двигалась одна и та же позиция номенклатуры?

идет внедрение и документы надо перепроводить ежедневно. А как это посчитать?

Сколько в среднем перемещений товаров и сколько в среднем строк в документе?

Еще не известно кто ошибется - команда разработчиков или ты...

около 800 перемещений в месяц. Строчек от 5 до 20. складов около 15

У меня релиз 1.5.1.34. Такой процедуры не вижу. Имеются в виду NP задачи?

А ещё я бы предложил вообще не пользоваться "корректировкой фактической стоимости номенклатуры" и считать по скользящей средней

Кстати, когда я впервые увидел эту штуку - был совершенно потрясён. На сколько мощно, красиво, сложно, медленно и (скорее всего) никому особо не нужно

Я этого цикла не видел, но предполагаю, что оценить порядок количества итераций можно следующим образом: 800*800*10(среднее количество строк)*15 = 96 000 000, при использовании неоптимального алгоритма. Это только порядок значений, реально всё зависит еще и от структуры графа. На сколько я помню, написанный когда-то мною алгоритм делал это за 800^1,5*10*15 = 3 400 000 итераций. Но там был неориентированный граф. Думаю, что для ориентированного можно реализовать алгоритм имеющий примерно такую же зависимость от количества перемещений.

В любом случае можно уйти от квадратичной зависимости по количеству перемещений. Точнее смогу сказать, когда увижу сам цикл.

Общие модули корректировка стоимости РассчитатьСписаниеПоСредней + 3000 проводок Д10К10

+ 70 000 000 / 3 000 = 23 333 20 тыс. раз алгоритм мусолит кажду проводку !!!!