IE 2016

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

Опубликовал ildarovich в раздел Программирование - Практика программирования

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

 

Задача, рассматриваемая в статье, приводится здесь с разрешения ее автора 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. Там всего лишь несколько более длинный код. Также возможно будет интересным показать, как решается эта задача с использованием техники «одного запроса». 

 

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

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

См. также

Лучшие комментарии

24. Ish_2 (файл скачал) 22.11.2010 15:04
(22)
Признаю , что
поставленная мной в посте #79 обсуждения "Реально написать хитрый запрос" задача была решена Сергеем за 0,122 секунды.
Признаю,
что графы 1-10-10-10-10-10-10 с уникальными "листьями", которые нужно хранить в информационных базах клиентов, в жизни практически не встречаются.
Ответили: (25)
+ 2 [ Grohovod; ildarovich; ]
# Ответить
36. Ish_2 (файл скачал) 23.11.2010 05:39
(35)Нет. Использовать sum(), как борбу с повторениями элементов в задаче не удалось.
Хотя тест 1-10-10-10-10-10-10 , казалось бы, просто требует этого.
Но при контроле зацикленности всё усложняется.
Проще говоря : Как нам не попасть на миллиард ? - я отказался от рассмотрения этого вопроса.
Непрактично, маловостребовано. Вообщем , в настоящий момент выгодней считать , что "зелен виноград".
+ 1 [ hogik; ]
# Ответить
50. ildarovich 08.12.2010 12:55
(49) Вы много раз повторяете одну и ту же НЕПРАВДУ!
При тестировании Ваши построения разлетелись вдребезги.

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


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

Кстати, повторюсь, - один интересный для меня тест еще остался - "Электровоз"! Его бы я попробовал!
+ 1 [ hogik; ]
# Ответить

Комментарии

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

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

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

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


Какой прок пользователю ведущему работу по спецификациям узнать о какой-то вершине.
Для того чтобы исправить ошибку пользователь должен знать и видеть всю ветку содержащую ошибку начиная от корневого элемента . Еще раз внимательно посмотрите на прикрепленном скриншоте , как нужно показывать ошибки зацикливания пользователю .
Ответили: (17)

Прикрепленные файлы:

Граф ошибок.png
# Ответить
3. Ish_2 (файл скачал) 21.11.2010 20:53
Разговор же о том , как сделать алгоритм более устойчивым к повторениям элементов и не попасть на миллиард в произвольном графе:( например,1-1000-1000-1000 ) - достаточно сложен , в реальной практике даже не знаю где встречается и я ,честно говоря, не решаюсь его даже начинать .

Прикрепленные файлы:

Граф ошибок.png
# Ответить
4. Ish_2 (файл скачал) 21.11.2010 20:59
Вопрос :
Имеем граф целиком :

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


Посмотрите на элемент Б0 на третьем уровне. Мы уже раньше побывали в Б0 - это будет считаться зацикливанием ? Такой граф будет решен Вашей обработкой ?
Ответили: (6)
# Ответить
5. WKBAPKA 21.11.2010 23:51
Ребята, я из этой темы на форуме вышел уже давно... т.к. абсолютно бесполезный спор... я привел пример простого динамического списка, у которого всегда есть ссылка на его родитель , тем самым у него никогда не может быть зацыкливания. Пример, иерархия папок в 1С. Например, в Excel если оперировать формулами в ячейках, может быть зацыкливание, однако это решается. Искать решение же задачи, типа "что может быть, а может и не быть", только одними запросами без дополнительных средств, тоже самое, что концатрептив натягивать на голову... Я предложил простой вариант: сделали запрос, выгрузили в промежуточную таблицу, проиндексировали поле, и ищите себе на здоровье...
Ответили: (8) (9)
# Ответить
6. WKBAPKA 21.11.2010 23:52
2(4): Б0 - кто у этого элемента родитель?
Ответили: (10) (11)
# Ответить
7. WKBAPKA 21.11.2010 23:57
блин, нужно завтра на свежую голову перечитать...
# Ответить
8. hogik 22.11.2010 00:38
(5)
Ярослав.
В ТОЙ теме нет никакого спора. Про циклы - точно, нет спора.
Думаю, вопрос (условие) про цикл поставлено постановкой задачи от Игоря, чтобы НАМ не удалось сделать "простой вариант: запрос - выгрузили в таблицу - проиндексировали - ищите".
Игорь, я - прав? ;-)
Ответили: (9)
# Ответить
9. hogik 22.11.2010 00:50
(5)
+(8)
Т.е. есть четкая, не изменяемая в процессе решения, схема БД. Есть условие - проверять "циклы" и считать количество изделий на нижнем уровне. Делать в реляционной модели БД. Делать на ЯМД реляционной СУБД. Использовать запросы. Всё...
# Ответить
10. Ish_2 (файл скачал) 22.11.2010 05:38
(6) В этом графе три полных ветки :
1. А0-Б0
2. А0-Б1-С0
3. А0-Б1-Б0

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

Здесь вес дуг предположен равным 1, а С0 заменена на В0 для вывода рисунка
# Ответить
12. Арчибальд 22.11.2010 11:37
Исследовал произвольные графы с 1000 узлов и 1000, 2000, 3000, 4000 дуг (http://infostart.ru/public/78032/ ), а тут появилась эта статья. Будем пробовать и такой граф обходить...
Ответили: (14) (26)

Прикрепленные файлы:

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

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

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

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

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

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

Представьте себе что все элементы в Вашем графе 1-10-10-10-10-10-10 уникальны . Нет повторений .
Что будет с Вашим алгоритмом ? у Владимира - это менее 200 сек . А у Вас ?
Ответили: (19) (21)
# Ответить
19. ildarovich 22.11.2010 14:32
(18) Алгоритм универсальный, работает с произвольным графом. Для того, чтобы в этом убедиться, достаточно скачать конфигурацию и вручную ввести в справочник структуру этого произвольного графа. Если договоримся о формате, сделаю загрузку из файла.
Могу предложить текстовый файл, в каждой строке которого содержится строка спецификации в виде тройки чисел: код номенклатуры-набора, код номенклатуры-элемента, количество элемента в наборе.
Ответили: (20)
# Ответить
20. Ish_2 (файл скачал) 22.11.2010 14:37
(19) Заполнение Вашего графа 1-10-10-10-10-10-10 уникальными значениями в реквизите "Элемент" займет часа три.
Попробуете ? Если да , то сколько будет работать Ваше "разузлование" для такого примера ?
Ответили: (22) (23)
# Ответить
21. ildarovich 22.11.2010 14:41
(18) Алгоритм универсальный, работает с произвольным графом. Для того, чтобы в этом убедиться, достаточно скачать конфигурацию и вручную ввести в справочник структуру этого произвольного графа. Если договоримся о формате, сделаю загрузку из файла.
Могу предложить текстовый файл, в каждой строке которого содержится строка спецификации в виде тройки чисел: код номенклатуры-набора, код номенклатуры-элемента, количество элемента в наборе.

Хотелось бы узнать про практические примеры 10-арных 6-ти уровневых деревьев, элементы которых стоило бы хранить в информационной базе. На мой взгляд в жизни такие задачи практически не встречаются. Сколько у Вас пользователей, у которых в Справочнике "Номенклатура" 1 000 000 элементов, а 100 000 спецификаций?
# Ответить
22. ildarovich 22.11.2010 14:54
(20) Сначала я бы хотел, чтобы Вы признали, что поставленная Вами в посте #79 обсуждения "Реально написать хитрый запрос" задача была решена за 0,122 секунды.
Потом, согласились с тем, что графы 1-10-10-10-10-10-10 с уникальными "листьями", которые нужно хранить в информационных базах клиентов, в жизни практически не встречаются.
Ну а потом, я уже получал результат 180 секунд. Могу с этой точки начать оптимизацию.
Но хотелось бы убедиться в актуальности этой новой задачи.
Ответили: (24)
# Ответить
23. Ish_2 (файл скачал) 22.11.2010 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)
# Ответить
24. Ish_2 (файл скачал) 22.11.2010 15:04
(22)
Признаю , что
поставленная мной в посте #79 обсуждения "Реально написать хитрый запрос" задача была решена Сергеем за 0,122 секунды.
Признаю,
что графы 1-10-10-10-10-10-10 с уникальными "листьями", которые нужно хранить в информационных базах клиентов, в жизни практически не встречаются.
Ответили: (25)
+ 2 [ Grohovod; ildarovich; ]
# Ответить
25. ildarovich 22.11.2010 15:19
(23)(24) Игорь! Спасибо Вам за задачу.
Меня, конечно, интересует запрос в пункте "2. Разузлование как таковое", тем более, у меня есть свой симпатичный, но пока не эффективный вариант (в обсуждении "Хитрый запрос" я его показывал). Буду ждать Вашей публикации.
Ваш пример о суммировании квадратов средствами СУБД был очень убедителен.
Ответили: (30) (32)
# Ответить
26. ildarovich 22.11.2010 15:51
(12) К сожалению, в реальном программировании на 1С графы встречаются редко:
- разузлование;
- маршруты развоза товаров;
- подчиненность документов;
- аналоги номенклатуры;
- везде, где в справочниках или документах есть ссылка (может быть не прямая) на аналогичный объект;
- структура конфигураций, программных модулей.
Какие еще примеры Вы можете привести?
А если это вдруг действительно сложная в вычислительном отношении задача, то решать ее на языке 1С трудно - большие накладные расходы. Здесь лучше применять внешние компоненты. Тем более структуры графов легко транслируются через интерфейсы.
Так что боюсь, результаты исследований будут представлять чисто "академический" интерес.
Ответили: (27) (29)
# Ответить
27. Ish_2 (файл скачал) 22.11.2010 16:09
(26) Подождите чуть -чуть. Я уже месяц откладываю публикацию.
Ответили: (28)
# Ответить
28. Арчибальд 22.11.2010 16:26
(27) Новый год на носу, однако :evil:
Ответили: (41)
# Ответить
29. cool.clo 22.11.2010 16:47
(26) Соглашусь. А никто не пробовал прикрутить к 1С matlab (или maple )?
Ответили: (31)
# Ответить
30. hogik 22.11.2010 18:14
(25)
"Ваш пример о суммировании квадратов средствами СУБД был очень убедителен."(с)
1) Чтение файла большими блоками, а не по записям.
2) Чтение без использования индекса.
3) При повторном чтении - все данные уже в памяти (фактически в массиве).
4) Суммирование 1000000 "квадратов" в массиве НЕ на 1С - 1.5 миллисекунды.
5) Суммирование 1000000 "квадратов" в массиве на 1С - 1.8 секунды.
В данном примере нет никаких "средств" СУБД.
Арифметика... ;-)
Ответили: (32) (41)
# Ответить
31. ildarovich 22.11.2010 18:44
(29) 1С + MatLab было бы интересно! Не слышал пока о таком. Возможно, MatLab просто дорог.
# Ответить
32. Ish_2 (файл скачал) 22.11.2010 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) (34) (35) (37) (39)
# Ответить
33. hogik 22.11.2010 23:56
(32)
Игорь.
Фразы типа "глубокое непонимание этого назначения SQL."(с) говорите себе. Я могу Вам рассказать всю цепочку действий системы от "тупого" нажатия кнопки в "СКД", до команд ввода/вывода уровня команд порта - in,out.
В моем сообщении #30 сказано, что Ваш пример запроса с Sum() позволяет серверу БД выполнять суммирование "квадратов" на сервер и не передавать строки таблицы клиенту, а передать клиенту только одно число. Кроме этого, по сути SQL запроса, сервер имеет возможность просматривать таблицу без учета индекса и анализа условий отбора. А это означает, что он может применить операции чтения блоками по несколько логических записей. И эти блоки, после чтения с диска, представляют из себя массив (массивы) данных в оперативной памяти. При таких малых размерах таблицы, как в нашем примере - это может быть одним-двумя массивами, если используется специфическая для сервера БД файловая система. Данные в полях хранятся, скорее всего, в числовом, а не символьном виде и это не требует затратных действий по преобразованию типов данных (против языка 1С).
Таблица БД такого размера читается блокам в оперативную память, даже на файловой системе NTFS - за доли секунды. Если сервер использует многозадачность, то при чтении несколькими блоками всей таблицы - может использоваться параллельный подсчет сумм "квадратов".
Игорь, это азбука СУБД... ;-)
А Вы упрямо путаете два термина SQL и СУБД.
# Ответить
34. hogik 23.11.2010 00:15
(32)
+33
Игорь.
Вы в своих изысках на тему "Мы пишем запросы"(с) плавно и логично подошли к "последнему алгоритму" этой темы - обход "дерева". На протяжении всего Вашего цикла я, безуспешно, пытался обратить Ваше внимание, что "запросный" метод обработки информации не подходит для очень большого количества алгоритмов.
Вы упрямо, в своём цикле, "собирали" эти алгоритмы. Вы их собрали - почти все...
Но наличие этих алгоритмы (задач) уже поняли, даже, "разработчики" SQL серверов. Посмотрите внимательно на развитие этого языка. Всё, что добавлялось в него направлено на возможность решать SQL-ем не только задачи по выходным (отчетам) формам.
А Вы - всё упрямствуете... ;-)
# Ответить
35. hogik 23.11.2010 02:29
(32)
+33
Игорь.
Извините, я забыл самое главное написать в своих ответах на Ваше #32 сообщение - конкретику. Вам удалось свой пример про Sum() прицепить к задаче обхода "дерева"? Или это просто пример (ошарашить читателя) скоростями "запросов" безотносительно решаемой задачи? Типа - мы и "дерево" обойдем Sum-ами...
Ответили: (36)
# Ответить
36. Ish_2 (файл скачал) 23.11.2010 05:39
(35)Нет. Использовать sum(), как борбу с повторениями элементов в задаче не удалось.
Хотя тест 1-10-10-10-10-10-10 , казалось бы, просто требует этого.
Но при контроле зацикленности всё усложняется.
Проще говоря : Как нам не попасть на миллиард ? - я отказался от рассмотрения этого вопроса.
Непрактично, маловостребовано. Вообщем , в настоящий момент выгодней считать , что "зелен виноград".
+ 1 [ hogik; ]
# Ответить
37. ildarovich 23.11.2010 10:25
(32) Игорь!
Если Вы заметили, я не спорю с Владимиром. Потому что он говорит правильные вещи.
Но в то же время мне не хотелось бы гасить Ваш энтузиазм в поиске задач, которые эффективней решать в запросной технике. Такие задачи есть. Просто это не все задачи, где "на входе миллион элементов, а на выходе - несколько чисел". Хотелось бы знать более точное универсальное правило, если оно существует. Мне кажется, Ваши поиски, пусть и не во всех случаях удачные, этому способствуют.
Ответили: (40)
+ 1 [ hogik; ]
# Ответить
38. cool.clo 23.11.2010 11:23
Кстати, matlab может работать с odbc совместимыми данными - т.е. и sql server-ом. Очень интересная задача, будет время - надо подумать. Мне кажется 1С несмотря на изворотливость программистов, все таки для таких задач не оптимальный вариант. А вот связка 1С - matlab - sql - была бы интересной, может кто осилит? И все таки описанный в статье метод мне нравится.
# Ответить
39. ildarovich 23.11.2010 11:34
(32) Игорь!
Если Вы заметили, я не спорю с Владимиром. Потому что он говорит правильные вещи.
Но в то же время мне не хотелось бы гасить ваш энтузиазм в поиске задач, которые эффективней решать в запросной технике. Такие задачи есть. Просто это не все задачи, где "на входе миллион элементов, а на выходе - несколько чисел". Хотелось бы знать универсальное правило, если оно существует. Мне кажется Ваши поиски, пусть и не во всех случаях удачные, этому способствуют.
Ответили: (40)
# Ответить
40. cool.clo 23.11.2010 11:45
(37)(39) начался цикл :D
# Ответить
41. Ish_2 (файл скачал) 23.11.2010 15:06
(0),(28),(30) Господа . Я старался для вас !
http://infostart.ru/public/78285/
# Ответить
42. huse 25.11.2010 10:05
(0) А в чем проблема - рекурсией спуститься до элемента Д0, посчитать сколько там элементо Е0...Е9, запомнить в кэш. Затем до элемента Д1, посчитать и в кэш. .... до Д9... На элементе Г0 уже не надо будет опускаться до элементов Д0-9 - все уже посчитано в кэше.

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

PS В чем делали такой прикольный рисунок графа?
Ответили: (43) (45)
+ 1 [ ildarovich; ]
# Ответить
43. cool.clo 25.11.2010 10:59
(42) Это и не проблема, просто рекурсия проиграет, я думаю, в производительности. (времени выполнения)
Ответили: (44) (46)
# Ответить
44. huse 25.11.2010 12:04
(43) если Вы не будете пользоваться кэшем, то моя рекурсия с кэшем победит по скорости.
# Ответить
45. ildarovich 25.11.2010 21:57
(42) Именно такой метод и описан в статье. Приведен текст программы (на скриншоте). Она работает с любыми ориентированными графами!!! Вообще любыми. Можете скачать конфигурацию и проверить. Программа на фиг3 построена на массивах. Матрица - это массив массивов. Матрица[ё] - это тоже массив (вложенный) - кэш узла "Упаковка". У массивов недостаток - ограниченное число вершин. Сейчас переписал на соответствия. Решается вообще граф любого размера. В приложенной конфигурации все это есть.
А также обработка, рисующая граф (узлы кликабельны) - присмотритесь к приложенному изображению №2.

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

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

Статья написана не для Вас, Вы этот метод знаете и не будете пользоваться перебором, а многие пользуются и отказываться не хотят, споря о некой "абстрактной" рекурсии. Присмотритесь к фиг3 - это и есть работающая в этой и вообще в любых задачах разузлования рекурсия.
# Ответить
46. ildarovich 25.11.2010 22:05
(43) Именно так! Только рекурсия не Ваша, а наша!

Статью планирую переписать, сделав ее более понятной.
# Ответить
47. Ish_2 (файл скачал) 07.12.2010 19:30
Так что , Сергей ?
Насчет новой темы со сравнительным анализом двух обработок ?
Вдруг рекурсия и правда - выиграет у запроса ? А почему бы и нет ?
Уже по Вашим правилам и тестам .
Почему бы не создать теперь уже не "пулялку" по тестам №1,№2 , а технологичное решение для БП 1.6 и
в сравнительном анализе - утереть всем нос : СМОТРИТЕ - мой товар лучший !
Ответили: (48)
# Ответить
48. ildarovich 08.12.2010 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)
# Ответить
49. Ish_2 (файл скачал) 08.12.2010 11:27
(48) Подсказывать , советовать Вам рано.
При тестировании Ваши построения разлетелись вдребезги.
Вам нужно научиться практически доказывать свои измышления.

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

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


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

Кстати, повторюсь, - один интересный для меня тест еще остался - "Электровоз"! Его бы я попробовал!
+ 1 [ hogik; ]
# Ответить
51. Ish_2 (файл скачал) 08.12.2010 14:33
Всегда готов отбросить предубеждения и рассмотреть интересный практический вопрос.
+ 1 [ ildarovich; ]
# Ответить
Внимание! За постинг в данном форуме $m не начисляются.
Внимание! Для написания сообщения необходимо авторизоваться
Текст сообщения*
Прикрепить файл