Как не «попасть на миллион», решая задачу разузлования

28.11.10

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

Часто, столкнувшись с долгим временем выполнения какого-либо фрагмента кода, мы начинаем искать технологические программные решения: переносить вычисления в СУБД, либо в оперативную память, устранять неявные запросы в циклах, применять другие известные приемы оптимизации или просто ругать платформу. Хотя на самом деле проблема  может быть всего лишь в неверно выбранном алгоритме. В статье рассказывается об одном таком случае, возникшем при решении задачи «разузлования».  Надеюсь, прочитав эту статью и ознакомившись с текстом варианта программы, построенной по давно известному алгоритму, Вы избежите подобных ошибок. Тем более программа получилась совсем небольшой.

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

Наименование Файл Версия Размер
Разузлование.dt
.dt 40,08Kb
102
.dt 40,08Kb 102 Скачать
Внешний отчет суперскоростное разузлование (быстрее нельзя!) для БП с исправлениями 28.11.10
.erf 8,09Kb
53
.erf 8,09Kb 53 Скачать
Что бы проверить работу разузлования в пустой БП строятся графы, деревья заданных параметров
.epf 8,31Kb
23
.epf 8,31Kb 23 Скачать

 

Задача, рассматриваемая в статье, приводится здесь с разрешения ее автора Ish_2. Собственно задача была сформулирована в ходе обсуждения вопроса "Реально написать хитрый запрос" в посте (79) примерно так:

 

Дана таблица, содержащая три колонки: номенклатура-набор (X), номенклатура-элемент (Y), количество элементов в наборе (Z). В строчках этой таблицы записаны тройки (X, Y, Z):

Всего таблица содержит 61 элемент ("0", А0, ..., А9, Б0, ... , Б9, ... , Е0, ... , Е9) и 510 строк:

(0, А0, 2) (0, А1, 2) (0, А2, 2) (0, А3, 2) (0, А4, 2) (0, А5, 2) (0, А6, 2) (0, А7, 2) (0, А8, 2) (0, А9, 2)

(А0, Б0, 2) (А0, Б1, 2) (А0, Б2, 2) (А0, Б3, 2) (А0, Б4, 2) (А0, Б5, 2) (А0, Б6, 2) (А0, Б7, 2) (А0, Б8, 2) (А0, Б9, 2)

(А1, Б0, 2) (А1, Б1, 2) (А1, Б2, 2) (А1, Б3, 2) (А1, Б4, 2) (А1, Б5, 2) (А1, Б6, 2) (А1, Б7, 2) (А1, Б8, 2) (А1, Б9, 2)

...

(Д9, Е0, 2) (Д9, Е1, 2) (Д9, Е2, 2) (Д9, Е3, 2) (Д9, Е4, 2) (Д9, Е5, 2) (Д9, Е6, 2) (Д9, Е7, 2) (Д9, Е8, 2) (Д9, Е9, 2).

Каждая строка таблицы (X, Y, Z)  интерпретируется следующим образом: объект X содержит элемент Y в количестве Z.  Наглядно эта таблица представляется следующим графом (фиг1). Все дуги на фиг1 направлены слева направо и имеют вес, равный двум.

Требуется построить программу, способную посчитать:  сколько  элементов  Е0, Е1, Е2, Е3, Е4, Е5, Е6, Е7, Е8, Е9 содержится в объекте «0». Конечно, программа  должна решать подобные задачи в общем случае для всех подобных таблиц. Тогда данный пример будет тестом скорости работы программы,  а  также правильности алгоритма путем сравнения с очевидным ответом  (6 400 000, 6 400 000, … , 6 400 000). В этом общем случае программа также  должна исключать ошибочные связи типа Е9 – 0, Д0 – Б9 и другие «обратные» связи, приводящие к «зацикливанию».

Сравнение строк 11 (А0-Б0-2) и 21 (А1-Б0-2) позволяет сделать принципиально важный вывод: структура, описываемая таблицей, не является деревом! Элемент Б0 имеет более одного владельца! Необходимость такой структуры при составлении сборочных спецификаций  легко объяснить: если четыре колеса входят в спецификацию автомобиля, а два таких же колеса в спецификацию прицепа, то заводится не две разных, а одна единая спецификация колеса.  В результате шина как элемент колеса входит в состав автомобиля с прицепом двумя различными способами: в составе колеса в составе автомобиля и в составе колеса в составе прицепа.

В тестовом примере элемент Е9 входит в состав элемента «0»  сто тысячью (100 000) различных способов!  Вот тут-то некоторые программисты и делают принципиальную ошибку: они считают, что для подсчета числа вхождений Е9 нужно перечислить все 100 000 способов. (На самом деле это тоже самое, что вычислять  10 х 10 х 10 х 10 х 10 х 10 миллионом сложений единиц!) Источником этой ошибки, видимо, является известный отчет о разузловании, строчки которого соответствуют путям вхождения атомарных деталей в готовое изделие. Отчет для наглядности представляется в виде дерева. В данном случае это дерево отчета будет иметь  миллион конечных вершин. Видимо, тут и возникает желание получить результат поставленной задачи группировкой этих путей по виду их конечных элементов. Как же по-другому? – А вот как:

1.       Исходная задача разузлования заданного узла разбивается на более простые задачи разузлования отдельных узлов, причем в этих простых задачах считается, что результат разузлования подчиненных узлов уже известен. Тогда результат разузлования узла получается как сумма результатов разузлования подчиненных узлов, взятых с коэффициентом количества для каждого подчиненного узла. Если обозначить результат разузлования узла j как Q(j) = (q1j, q2j, … , qNj), где qij обозначает, что узел j транзитивно содержит узел i qij раз, и если как gkl обозначить количество узлов i в спецификации узла k, то получаем простую формулу подсчета результата разузлования узла k

Q(k) = i=1,N G’(i) * Q(i) = i=1,N gki * qij. (1)

2.       Результат разузлования каждого узла запоминается, чтобы не вычисляться заново. Поэтому в решении тестовой задачи будет всего 51 операция вида (1).

3.       Порядок обхода вершин графа, начиная с заданного, определяется рекурсией. Дважды в один и тот же узел для расчетов алгоритм не входит!

Вот конфигурация справочника, в котором хранится таблица (фиг2)

А вот код самой программы (фиг3)

Приведен весь исходный код. Никакого другого кода в решении нет и он не требуется.

Для работы с относительно небольшими структурами достаточно использовать массивы.

В данном случае используется массив массивов Матрица. Измерениями  будет номер вершины графа. Для простоты считаем, что коды вершин начинаются с единицы и не содержат пропусков. Это позволяет рассчитать индекс при обращении к массиву как ё = Ссылка.Код – 1. В результате Матрица[ё] будет содержать разузлование узла Ссылка. Если  Матрица[ё][0] = Неопределено, значит, этой вершиной еще не занимались.  Сначала разузлование обнуляется //процедура Обнулить()//, затем к нему в цикле прибавляются разузлования подчиненных узлов //определяемые рекурсивно процедурой Распаковать()// с соответствующим весом //процедура Добавить()//.  После разузлования подчиненных узлов отмечаем единицей текущий узел //Матрица[ё][ё] = 1//.  Этой единицей данный узел будет с точки зрения  вышележащих уровней. 

Если разузлование находится в процессе расчета //Матрица[ё][0] <> Неопределено//, но не закончено, то Матрица[ё][ё] = 0. Это дает возможность проверить зацикливание. Правда диагностический вывод «слабоват» - мы отмечаем только вершину, в которую попали в результате «зацикливания».

Запрос в начале работы программы нужен только для построения таблицы, куда потом будут помещены результаты работы метода,  для определения терминальных узлов, а также для определения количества узлов, которое также определяет  размерность массива.

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

Сейчас тестовая задача выполняется примерно 0,122 секунды (использовалась платформа 8.1 и ноутбук). При этом «неправильные» методы дают на два-три порядка большие значения!

Сформировав структуру степени 10 из 33 уровней (331 вершина), получим время разузлования всего 3,666 секунды!

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

Если никто не вспомнит, где уже встречалось такое решение, мне будет нетрудно перевести его на  77. Там всего лишь несколько более длинный код. Также возможно будет интересным показать, как решается эта задача с использованием техники «одного запроса». 

 

См. также

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

Математика и алгоритмы Платформа 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    4419    user1959478    50    

34

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

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

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

1 стартмани

09.06.2023    7462    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    4446    fishca    13    

36

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

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

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

12.10.2021    8839    John_d    73    

46

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

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

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

31.08.2021    7805    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. hogik 443 21.11.10 18:41 Сейчас в теме
(0)
Сергей.
За статью - "плюс" однозначно.
Однако в сообщении #79 темы "Реально написать хитрый запрос"(с) - поставлена другая задача. И Ваше утверждение "Хотя на самом деле проблема может быть всего лишь в неверно выбранном алгоритме"(с) - верно, но не для поставленной Игорем задачи.
Думаю, что любой алгоритм "базируется" на структуре хранения (представлении) данных. А в постановке от Игоря - структура хранения должна быть "только такой", а данные должны храниться и обрабатываться в "реляционной модели", а язык манипулирования данными должен быть "запросного" типа.
Игорь, думаю, специально поставил задачу так, чтобы "Мы писали запросы"... ;-)
Выше по его теме и "исходной" темы, было многократно сказано, что изменение структуры хранения данных и ЯМД позволяет решать задачу "разузлования" - быстро и простым алгоритмом.
Исходная тема: http://infostart.ru/public/75878/ с сообщения #151.
2. Ish_2 1104 21.11.10 20:33 Сейчас в теме
Будем плясать от печки. От постановки задачи.
Что мы решаем ? Почему это четко не обозначено в начале темы ?
Придется строить догадки , что же решает автор ?

1. Задачу разузлования в общем виде ?
Тогда нам дана структура таблицы Ссылка, Номенклатура,Количество , в которой содержатся не один граф, а все графы, описывающие все спецификации на предприятии.
Действительно , смешно заводить Справочник для каждого нового сложного изделия.
Поэтому в Справочнике есть спецификации и "паровоза", и "тепловоза", и много чего еще. Из этого вытекает, что перед началом разузлования мы ничего не знаем о графе , который в нем содержится , не знаем какие записи в Справочнике нашего искомого изделия, а какие принадлежат другому изделию , не входящему в исследуемый нами граф.. Повторяю мы Н И Ч Е Г О не знаем о графе. Ни количество связей(510 у автора) , ни количество элементов(61- у автора) , неизвестно повторяются ли элементы в этом графе, есть ли зацикливание ? Неизвестен и уровень графа. Ответ на эти вопросы можно получить только одним способом : обойти все узлы графа. На форуме я безуспешно пытался втолковать это автору. Но может быть я что-то не понял ? и тогда :

2. Решается задача разузлования для искусственного, придуманного мной примера ?
Но пример этот был придуман всего лишь как удобный легкий тест для оценки быстродействия универсального алгоритма обработки произвольного графа. И я не понимаю для чего его здесь решать ? Что это нам даст ?
Задача разузлования для графа с известной повторяющейся структурой - есть задача ТРИВИАЛЬНАЯ . Её не нужно решать.

Но даже решая тривиальную ,никому не нужную задачу получаем у автора :
Если разузлование находится в процессе расчета //Матрица[ё][0] <> Неопределено//, но не закончено, то Матрица[ё][ё] = 0. Это дает возможность проверить зацикливание. Правда диагностический вывод «слабоват» - мы отмечаем только вершину, в которую попали в результате «зацикливания».


Какой прок пользователю ведущему работу по спецификациям узнать о какой-то вершине.
Для того чтобы исправить ошибку пользователь должен знать и видеть всю ветку содержащую ошибку начиная от корневого элемента . Еще раз внимательно посмотрите на прикрепленном скриншоте , как нужно показывать ошибки зацикливания пользователю .
Прикрепленные файлы:
17. ildarovich 7850 22.11.10 14:20 Сейчас в теме
(2) Соглашусь, что не переименовав справочник "Справочник" в справочник "Номенклатура", я усложнил понимание статьи. Вскоре исправлю.
Хотя алгоритм универсальный, из-за применения массива для хранения промежуточных разузлований, он работает для конфигураций, справочник "Номенклатура" в которых содержит до 5-10-ти(?) тысяч номенклатур, а эффективней работает только до нескольких сотен. Это преодолимо - переделаю на таблицы значений.
Также совсем нетрудно распечатывать ошибочный цикл (добавлю один параметр в процедуру Распаковать()).
3. Ish_2 1104 21.11.10 20:53 Сейчас в теме
Разговор же о том , как сделать алгоритм более устойчивым к повторениям элементов и не попасть на миллиард в произвольном графе:( например,1-1000-1000-1000 ) - достаточно сложен , в реальной практике даже не знаю где встречается и я ,честно говоря, не решаюсь его даже начинать .
Прикрепленные файлы:
4. Ish_2 1104 21.11.10 20:59 Сейчас в теме
Вопрос :
Имеем граф целиком :

  А0 - Б0
       - Б1- С0
             - Б0


Посмотрите на элемент Б0 на третьем уровне. Мы уже раньше побывали в Б0 - это будет считаться зацикливанием ? Такой граф будет решен Вашей обработкой ?
6. WKBAPKA 214 21.11.10 23:52 Сейчас в теме
2(4): Б0 - кто у этого элемента родитель?
10. Ish_2 1104 22.11.10 05:38 Сейчас в теме
(6) В этом графе три полных ветки :
1. А0-Б0
2. А0-Б1-С0
3. А0-Б1-Б0

Элемент Б0 встречается в первой ветке и в третьей. Вопрос : это зацикливание для представленного автором алгоритма или нет ?
11. ildarovich 7850 22.11.10 11:14 Сейчас в теме
(10)(6) Это не зацикливание.
Вот скриншот.

Здесь вес дуг предположен равным 1, а С0 заменена на В0 для вывода рисунка
13. Ish_2 1104 22.11.10 11:54 Сейчас в теме
(11) Отлично. Продолжим . Представим , что элемент Б0 из (10) представляет собой Вами первоначально представленный в теме граф 1-10-10-10-10-10-10. Почему нет ? У Вас же универсальная обработка графа, оптимизирующая повторения элементов. Что будет с Вашим алгоритмом ?
16. ildarovich 7850 22.11.10 14:00 Сейчас в теме
(13) Игорь! Я буквально придерживался условий Вашей задачи!
В посте (79) сказано
В справочнике Номенклатура создается ПЕРВЫЙ элемент НАЧАЛО и 7 десятков номенклатур. Каждый десяток отличается префиксом кода : А,Б,В,Г,Д,Е,Ж.

Еще там же сказано
Начминаем раскручивать таблицу для элемента НАЧАЛО и получим в конце раскрутки миллион элементов только с префиксами Ж . Группируем и на выходе должны иметь только 10 элементов
Ж001,Ж002...Ж010 со своими количествами.
Контроль зациклинности обязателен. Т.е. каждая ветка мысленно полученного дерева должна быть проверена на повторение элементов в этой ветке.
Реализовать алгоритм можно каким угодно образом.

В посте (116) сказано
Только в (79) я ошибся: не семь десятков номенклатур . а шесть десятков.

Таким образом дерево 1-10-10-10-10-10-10 Вы строите мысленно и не храните в базе.
Да и зачем его нужно было бы хранить? Чтобы отличать каждую из 100 000 "гаек" на последнем уровне на ней нужно выгравировать серийный номер, потом иметь 10 000 спецификаций на предпоследнем уровне, указав в каждой серийный номер гайки. Такое могут делать разве что в ракетах.
Я согласен, что кроме шести десятков номенклатур в справочнике может быть и другая номенклатура. Задайте, пожалуйста количество других элементов справочника номенклатура, чтобы я смог сообщить Вам время выполнения программы в таком случае, хотя это и не было предусмотрено исходным заданием.
18. Ish_2 1104 22.11.10 14:22 Сейчас в теме
(16) Начнем всё сначала. Весь смысл беседы на форуме сводился к тому :
Как эффективно работать с произвольным графом ?
Рассматривались родственные задачи . Общим свойством у которых является трудоемкость решения.
Каждый что-то предлагал ...
Как же узнать (протестировать) эффективность какого-либо алгоритма работы с произвольным графом ?
Вот и был придуман тест ,как критерий эффективности, который на очень малом количестве данных, мог быстро выявить эффективность предлагаемых решений. Тест этот - 1-10-10-10-10-10 хорош тем что легко , просто реализуется .
В С Ё ! Больше никакой нагрузки этот тест не несет ! Он играет вспомогательную роль !
Тесты не решают , потому что их решения хорошо проверяемы и известны заранее.

Скажите , зачем его решать ? Ведь это частный случай ,"не встречающийся в природе" !
Действительно ,что же я буду выдумывать вспомогательные тесты , а Вы будете находить для них решения ?
Замучаетесь поспевать за мной . Я буду с легкостью опрокидывать Ваши алгоритмы новыми примерами.

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

Представьте себе что все элементы в Вашем графе 1-10-10-10-10-10-10 уникальны . Нет повторений .
Что будет с Вашим алгоритмом ? у Владимира - это менее 200 сек . А у Вас ?
19. ildarovich 7850 22.11.10 14:32 Сейчас в теме
(18) Алгоритм универсальный, работает с произвольным графом. Для того, чтобы в этом убедиться, достаточно скачать конфигурацию и вручную ввести в справочник структуру этого произвольного графа. Если договоримся о формате, сделаю загрузку из файла.
Могу предложить текстовый файл, в каждой строке которого содержится строка спецификации в виде тройки чисел: код номенклатуры-набора, код номенклатуры-элемента, количество элемента в наборе.
20. Ish_2 1104 22.11.10 14:37 Сейчас в теме
(19) Заполнение Вашего графа 1-10-10-10-10-10-10 уникальными значениями в реквизите "Элемент" займет часа три.
Попробуете ? Если да , то сколько будет работать Ваше "разузлование" для такого примера ?
22. ildarovich 7850 22.11.10 14:54 Сейчас в теме
(20) Сначала я бы хотел, чтобы Вы признали, что поставленная Вами в посте #79 обсуждения "Реально написать хитрый запрос" задача была решена за 0,122 секунды.
Потом, согласились с тем, что графы 1-10-10-10-10-10-10 с уникальными "листьями", которые нужно хранить в информационных базах клиентов, в жизни практически не встречаются.
Ну а потом, я уже получал результат 180 секунд. Могу с этой точки начать оптимизацию.
Но хотелось бы убедиться в актуальности этой новой задачи.
24. Ish_2 1104 22.11.10 15:04 Сейчас в теме
(22)
Признаю , что
поставленная мной в посте #79 обсуждения "Реально написать хитрый запрос" задача была решена Сергеем за 0,122 секунды.
Признаю,
что графы 1-10-10-10-10-10-10 с уникальными "листьями", которые нужно хранить в информационных базах клиентов, в жизни практически не встречаются.
Grohovod; ildarovich; +2 Ответить
23. Ish_2 1104 22.11.10 14:59 Сейчас в теме
(20) Конечно , Сергей ! Нет таких практических примеров !
Для чего эти тесты ? Для того чтобы выявить предельные возможности того или иного алгоритма.
Ведь если уж алгоритм на миллионе работает быстро , то на реальных задачах (максимум 50 тыс -60 тыс в справочнике) будет просто летать. Вот для чего нужны тесты . А вариант с миллионом уникальных значений не высосан из пальца - и у меня и у Владимира время алгоритма практически неизменно.
Давайте конкретно.
Представьте себе алгоритм :
для Вашего графа в текущей теме 1-10-10-10-10-10-10 - он показывает время 20 сек .

Если в этом графе все значения уникальны - он показывает время 50 сек.
Раскроем 50 сек :
1. Копирование во временную таблицу всего справочника СпецификацииНоменклатуры 8 сек
2. Разузлование как таковое 25 сек.
3. Выгрузка результата запроса в таблицу значений на форме ( 1 000 000 строк) -18 сек.
Т.е. практически время разузлования как такового изменилось несущественно, учитывая что таблица Спецификаций увеличилась в десятки тысяч раз. Было 20 сек - стало 25 сек.
25. ildarovich 7850 22.11.10 15:19 Сейчас в теме
(23)(24) Игорь! Спасибо Вам за задачу.
Меня, конечно, интересует запрос в пункте "2. Разузлование как таковое", тем более, у меня есть свой симпатичный, но пока не эффективный вариант (в обсуждении "Хитрый запрос" я его показывал). Буду ждать Вашей публикации.
Ваш пример о суммировании квадратов средствами СУБД был очень убедителен.
30. hogik 443 22.11.10 18:14 Сейчас в теме
(25)
"Ваш пример о суммировании квадратов средствами СУБД был очень убедителен."(с)
1) Чтение файла большими блоками, а не по записям.
2) Чтение без использования индекса.
3) При повторном чтении - все данные уже в памяти (фактически в массиве).
4) Суммирование 1000000 "квадратов" в массиве НЕ на 1С - 1.5 миллисекунды.
5) Суммирование 1000000 "квадратов" в массиве на 1С - 1.8 секунды.
В данном примере нет никаких "средств" СУБД.
Арифметика... ;-)
32. Ish_2 1104 22.11.10 22:30 Сейчас в теме
(25) Я извмняюсь. Допускаю,что есть какой-то глубокий смысл в перечислении 1)-5).
Но мне он не доступен.
Смысл сравнения миллиона циклов в 1с и суммирования миллиона квадратов с помощью select был только один .
И не тот, что предположил Владимир.
Не в технике тут дело. А в способе работы с данными.
Отсюда прямой вывод :
нужно максимально использовать при обработке возможности сервера SqL Не качать данные туда -сюда (с клиента на сервер) , а обрабатывать данные полностью там , где они хранятся. Это значит в современных СУБД ТОЛЬКО одно - использовать запросы ,
как родной инструмент SQL-сервера. Груубо говоря, SQL- язык не выборки данных для последующей их обработки на клиенте ,
а язык выборки и ОБРАБОТКИ данных (там же на сервере) и передачи на клиента лишь результата вычислений.
В (30) - глубокое непонимание этого назначения SQL.
Рассмотрим п.4,5 в (30):
Суммирование 1000000 "квадратов" в массиве НЕ на 1С - 1.5 миллисекунды.
Суммирование 1000000 "квадратов" в массиве на 1С - 1.8 секунды.

Пример, конечно, убойный.
Владимиру тут всё ясно и обсуждать нечего :"В данном примере нет никаких "средств" СУБД."
Это значит , замени программное обеспечение на "не 1с" и получи в 1000(!!!!) раз быстрее .
Когда пройдет первая радость от такого счастья , выяснится что прежде чем сложить миллион квадратов на "не 1с"- массиве,
нужно их откуда-то взять... Откуда ? - оттуда, где хранятся данные, только с сервера. Как ? - Выбрать командой select.
Получай, бабушка, свой миллион чисел в оперативную память за 10 сек(!!!!) и складывай
их с сумашедшей скоростью за 1.5 миллисекунды.
Так, может , мы останемся на "медленном" 1с ? выдадим команду на сервер select sum(a*a) from table ,
получим с сервера ОДНО число-сумму и все вместе улыбнемся ?
33. hogik 443 22.11.10 23:56 Сейчас в теме
(32)
Игорь.
Фразы типа "глубокое непонимание этого назначения SQL."(с) говорите себе. Я могу Вам рассказать всю цепочку действий системы от "тупого" нажатия кнопки в "СКД", до команд ввода/вывода уровня команд порта - in,out.
В моем сообщении #30 сказано, что Ваш пример запроса с Sum() позволяет серверу БД выполнять суммирование "квадратов" на сервер и не передавать строки таблицы клиенту, а передать клиенту только одно число. Кроме этого, по сути SQL запроса, сервер имеет возможность просматривать таблицу без учета индекса и анализа условий отбора. А это означает, что он может применить операции чтения блоками по несколько логических записей. И эти блоки, после чтения с диска, представляют из себя массив (массивы) данных в оперативной памяти. При таких малых размерах таблицы, как в нашем примере - это может быть одним-двумя массивами, если используется специфическая для сервера БД файловая система. Данные в полях хранятся, скорее всего, в числовом, а не символьном виде и это не требует затратных действий по преобразованию типов данных (против языка 1С).
Таблица БД такого размера читается блокам в оперативную память, даже на файловой системе NTFS - за доли секунды. Если сервер использует многозадачность, то при чтении несколькими блоками всей таблицы - может использоваться параллельный подсчет сумм "квадратов".
Игорь, это азбука СУБД... ;-)
А Вы упрямо путаете два термина SQL и СУБД.
34. hogik 443 23.11.10 00:15 Сейчас в теме
(32)
+33
Игорь.
Вы в своих изысках на тему "Мы пишем запросы"(с) плавно и логично подошли к "последнему алгоритму" этой темы - обход "дерева". На протяжении всего Вашего цикла я, безуспешно, пытался обратить Ваше внимание, что "запросный" метод обработки информации не подходит для очень большого количества алгоритмов.
Вы упрямо, в своём цикле, "собирали" эти алгоритмы. Вы их собрали - почти все...
Но наличие этих алгоритмы (задач) уже поняли, даже, "разработчики" SQL серверов. Посмотрите внимательно на развитие этого языка. Всё, что добавлялось в него направлено на возможность решать SQL-ем не только задачи по выходным (отчетам) формам.
А Вы - всё упрямствуете... ;-)
35. hogik 443 23.11.10 02:29 Сейчас в теме
(32)
+33
Игорь.
Извините, я забыл самое главное написать в своих ответах на Ваше #32 сообщение - конкретику. Вам удалось свой пример про Sum() прицепить к задаче обхода "дерева"? Или это просто пример (ошарашить читателя) скоростями "запросов" безотносительно решаемой задачи? Типа - мы и "дерево" обойдем Sum-ами...
36. Ish_2 1104 23.11.10 05:39 Сейчас в теме
(35)Нет. Использовать sum(), как борбу с повторениями элементов в задаче не удалось.
Хотя тест 1-10-10-10-10-10-10 , казалось бы, просто требует этого.
Но при контроле зацикленности всё усложняется.
Проще говоря : Как нам не попасть на миллиард ? - я отказался от рассмотрения этого вопроса.
Непрактично, маловостребовано. Вообщем , в настоящий момент выгодней считать , что "зелен виноград".
37. ildarovich 7850 23.11.10 10:25 Сейчас в теме
(32) Игорь!
Если Вы заметили, я не спорю с Владимиром. Потому что он говорит правильные вещи.
Но в то же время мне не хотелось бы гасить Ваш энтузиазм в поиске задач, которые эффективней решать в запросной технике. Такие задачи есть. Просто это не все задачи, где "на входе миллион элементов, а на выходе - несколько чисел". Хотелось бы знать более точное универсальное правило, если оно существует. Мне кажется, Ваши поиски, пусть и не во всех случаях удачные, этому способствуют.
40. cool.clo 23.11.10 11:45 Сейчас в теме
39. ildarovich 7850 23.11.10 11:34 Сейчас в теме
(32) Игорь!
Если Вы заметили, я не спорю с Владимиром. Потому что он говорит правильные вещи.
Но в то же время мне не хотелось бы гасить ваш энтузиазм в поиске задач, которые эффективней решать в запросной технике. Такие задачи есть. Просто это не все задачи, где "на входе миллион элементов, а на выходе - несколько чисел". Хотелось бы знать универсальное правило, если оно существует. Мне кажется Ваши поиски, пусть и не во всех случаях удачные, этому способствуют.
21. ildarovich 7850 22.11.10 14:41 Сейчас в теме
(18) Алгоритм универсальный, работает с произвольным графом. Для того, чтобы в этом убедиться, достаточно скачать конфигурацию и вручную ввести в справочник структуру этого произвольного графа. Если договоримся о формате, сделаю загрузку из файла.
Могу предложить текстовый файл, в каждой строке которого содержится строка спецификации в виде тройки чисел: код номенклатуры-набора, код номенклатуры-элемента, количество элемента в наборе.

Хотелось бы узнать про практические примеры 10-арных 6-ти уровневых деревьев, элементы которых стоило бы хранить в информационной базе. На мой взгляд в жизни такие задачи практически не встречаются. Сколько у Вас пользователей, у которых в Справочнике "Номенклатура" 1 000 000 элементов, а 100 000 спецификаций?
5. WKBAPKA 214 21.11.10 23:51 Сейчас в теме
Ребята, я из этой темы на форуме вышел уже давно... т.к. абсолютно бесполезный спор... я привел пример простого динамического списка, у которого всегда есть ссылка на его родитель , тем самым у него никогда не может быть зацыкливания. Пример, иерархия папок в 1С. Например, в Excel если оперировать формулами в ячейках, может быть зацыкливание, однако это решается. Искать решение же задачи, типа "что может быть, а может и не быть", только одними запросами без дополнительных средств, тоже самое, что концатрептив натягивать на голову... Я предложил простой вариант: сделали запрос, выгрузили в промежуточную таблицу, проиндексировали поле, и ищите себе на здоровье...
8. hogik 443 22.11.10 00:38 Сейчас в теме
(5)
Ярослав.
В ТОЙ теме нет никакого спора. Про циклы - точно, нет спора.
Думаю, вопрос (условие) про цикл поставлено постановкой задачи от Игоря, чтобы НАМ не удалось сделать "простой вариант: запрос - выгрузили в таблицу - проиндексировали - ищите".
Игорь, я - прав? ;-)
9. hogik 443 22.11.10 00:50 Сейчас в теме
(5)
+(8)
Т.е. есть четкая, не изменяемая в процессе решения, схема БД. Есть условие - проверять "циклы" и считать количество изделий на нижнем уровне. Делать в реляционной модели БД. Делать на ЯМД реляционной СУБД. Использовать запросы. Всё...
7. WKBAPKA 214 21.11.10 23:57 Сейчас в теме
блин, нужно завтра на свежую голову перечитать...
12. Арчибальд 2706 22.11.10 11:37 Сейчас в теме
Исследовал произвольные графы с 1000 узлов и 1000, 2000, 3000, 4000 дуг (http://infostart.ru/public/78032/ ), а тут появилась эта статья. Будем пробовать и такой граф обходить...
Прикрепленные файлы:
14. Ish_2 1104 22.11.10 11:58 Сейчас в теме
(12) Арчибальд , э... ты что-то пропустил. У нас графы начинаются с миллиона узлов.
15. Арчибальд 2706 22.11.10 13:11 Сейчас в теме
(14) В данной статье - 510 дуг и 61 узел. Так что в тему :)
26. ildarovich 7850 22.11.10 15:51 Сейчас в теме
(12) К сожалению, в реальном программировании на 1С графы встречаются редко:
- разузлование;
- маршруты развоза товаров;
- подчиненность документов;
- аналоги номенклатуры;
- везде, где в справочниках или документах есть ссылка (может быть не прямая) на аналогичный объект;
- структура конфигураций, программных модулей.
Какие еще примеры Вы можете привести?
А если это вдруг действительно сложная в вычислительном отношении задача, то решать ее на языке 1С трудно - большие накладные расходы. Здесь лучше применять внешние компоненты. Тем более структуры графов легко транслируются через интерфейсы.
Так что боюсь, результаты исследований будут представлять чисто "академический" интерес.
27. Ish_2 1104 22.11.10 16:09 Сейчас в теме
(26) Подождите чуть -чуть. Я уже месяц откладываю публикацию.
28. Арчибальд 2706 22.11.10 16:26 Сейчас в теме
(27) Новый год на носу, однако :evil:
29. cool.clo 22.11.10 16:47 Сейчас в теме
(26) Соглашусь. А никто не пробовал прикрутить к 1С matlab (или maple )?
31. ildarovich 7850 22.11.10 18:44 Сейчас в теме
(29) 1С + MatLab было бы интересно! Не слышал пока о таком. Возможно, MatLab просто дорог.
38. cool.clo 23.11.10 11:23 Сейчас в теме
Кстати, matlab может работать с odbc совместимыми данными - т.е. и sql server-ом. Очень интересная задача, будет время - надо подумать. Мне кажется 1С несмотря на изворотливость программистов, все таки для таких задач не оптимальный вариант. А вот связка 1С - matlab - sql - была бы интересной, может кто осилит? И все таки описанный в статье метод мне нравится.
41. Ish_2 1104 23.11.10 15:06 Сейчас в теме
(0),(28),(30) Господа . Я старался для вас !
http://infostart.ru/public/78285/
42. huse 25.11.10 10:05 Сейчас в теме
(0) А в чем проблема - рекурсией спуститься до элемента Д0, посчитать сколько там элементо Е0...Е9, запомнить в кэш. Затем до элемента Д1, посчитать и в кэш. .... до Д9... На элементе Г0 уже не надо будет опускаться до элементов Д0-9 - все уже посчитано в кэше.

Итого мы получим 51 операцию разузловки - и никакого страшного миллиона.

PS В чем делали такой прикольный рисунок графа?
ildarovich; +1 Ответить
43. cool.clo 25.11.10 10:59 Сейчас в теме
(42) Это и не проблема, просто рекурсия проиграет, я думаю, в производительности. (времени выполнения)
44. huse 25.11.10 12:04 Сейчас в теме
(43) если Вы не будете пользоваться кэшем, то моя рекурсия с кэшем победит по скорости.
46. ildarovich 7850 25.11.10 22:05 Сейчас в теме
(43) Именно так! Только рекурсия не Ваша, а наша!

Статью планирую переписать, сделав ее более понятной.
45. ildarovich 7850 25.11.10 21:57 Сейчас в теме
(42) Именно такой метод и описан в статье. Приведен текст программы (на скриншоте). Она работает с любыми ориентированными графами!!! Вообще любыми. Можете скачать конфигурацию и проверить. Программа на фиг3 построена на массивах. Матрица - это массив массивов. Матрица[ё] - это тоже массив (вложенный) - кэш узла "Упаковка". У массивов недостаток - ограниченное число вершин. Сейчас переписал на соответствия. Решается вообще граф любого размера. В приложенной конфигурации все это есть.
А также обработка, рисующая граф (узлы кликабельны) - присмотритесь к приложенному изображению №2.

И еще - программа на фиг2 решает задачу тест №1 из статьи Мы пишем запросы за 0,122 секунды - в 200 раз быстрее запроса!

Сейчас закончил оптимизацию для графа из 1 111 111 вершин. Пишу тесты.

Статья написана не для Вас, Вы этот метод знаете и не будете пользоваться перебором, а многие пользуются и отказываться не хотят, споря о некой "абстрактной" рекурсии. Присмотритесь к фиг3 - это и есть работающая в этой и вообще в любых задачах разузлования рекурсия.
47. Ish_2 1104 07.12.10 19:30 Сейчас в теме
Так что , Сергей ?
Насчет новой темы со сравнительным анализом двух обработок ?
Вдруг рекурсия и правда - выиграет у запроса ? А почему бы и нет ?
Уже по Вашим правилам и тестам .
Почему бы не создать теперь уже не "пулялку" по тестам №1,№2 , а технологичное решение для БП 1.6 и
в сравнительном анализе - утереть всем нос : СМОТРИТЕ - мой товар лучший !
48. ildarovich 7850 08.12.10 10:59 Сейчас в теме
(47) Не вижу смысла:
1. Сравнительный анализ по быстродействию я провел, результаты опубликовал (в Вашей теме), закономерность определил, результаты других тестов будут "бить лежачего" (ваш подход). Зачем это Вам?
2. Сравнивать "юзабилити" (технологичность) в отсутствии Заказчика или объективного судейства невозможно. Хотя я представляю себе, как сделать удобный интерфейс, все же не считаю эту задачу сложной и нужной для себя.
Вам могу посоветовать убрать вкладку "ошибки" и отмечать ошибки цветом прямо на закладке спецификации. Цвет определять, используя "кодинг"-контроль зацикливания.
Кстати, обратите внимание, что в конфигурации, приложенной к статье есть обработка, рисующая граф средствами 1С, с кликабельными узлами! (присмотритесь к скриншоту №2, да и в заголовке - скриншот графа, нарисованной этой обработкой).
3. Будет время, я опубликую обработку, приложенную к данной статье, отдельно, снабдив описанием. Появилась идея еще немного ее ускорить на тесте 1<10<10<10<10<10<10 (улучшить результат 114 секунд) и увеличить число уровней в матрешке 1-1-1-1-1-1-1-1-1-1 -...-1-1. Сможете сами ее опробовать, сравнить со своей.
Ну, а "утирать Вам нос" - не моя задача. Хотел подсказать, объяснить, посоветовать...
49. Ish_2 1104 08.12.10 11:27 Сейчас в теме
(48) Подсказывать , советовать Вам рано.
При тестировании Ваши построения разлетелись вдребезги.
Вам нужно научиться практически доказывать свои измышления.

Я предложил Вам шанс - практически доказать , что Вы можете изготовить не "пулялку".
Вы отказались.
Вот и всё.
50. ildarovich 7850 08.12.10 12:55 Сейчас в теме
(49) Вы много раз повторяете одну и ту же НЕПРАВДУ!
При тестировании Ваши построения разлетелись вдребезги.

Повторение этой НЕПРАВДЫ ничего не меняет - приложенная к статье обработка на всех тестах работает очень
быстро и абсолютно правильно!


Учиться не отказываюсь, только вот нервируют термины "пулялка", "Сергей засыпался", "измышления", "разлетелись вдребезги", "очередная ошибка Сергея", "советовать Вам рано" в случаях, когда я почти наверняка знаю, что прав!
Свой шанс что-то Вам доказать я использовал по-максимуму - все мои доводы Вы пропустили мимо ушей! Почему?

Кстати, повторюсь, - один интересный для меня тест еще остался - "Электровоз"! Его бы я попробовал!
51. Ish_2 1104 08.12.10 14:33 Сейчас в теме
Всегда готов отбросить предубеждения и рассмотреть интересный практический вопрос.
ildarovich; +1 Ответить
52. Светлый ум 406 30.12.22 06:33 Сейчас в теме
Оставьте свое сообщение