gifts2017

Графин 7.7. (окончание)

Опубликовал Александр Рытов (Арчибальд) в раздел Программирование - Практика программирования

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

 

Предыдущие мои публикации Граф(ин) 7.7. и Граф(ин) 7.7. (дополнение) носили, скорее, умозрительный характер, имея одной из целей продемонстрировать, что деревья в частности и графы вообще вполне уживаются с семерочной платформой. Однако после появления статьи Запрос против рекурсии или "разузлование" номенклатуры мне просто некуда было деваться – и вот пришлось сваять небольшую конфигурацию для исследования «разузловательных» процессов. В конфигурации присутствуют два справочника: НоменклатурныеПозиции и Наборы. Содержимое справочника Наборы (с реквизитами Отец, Сын, Количество) как раз и определяет исследуемый граф.

Разумеется, я начал с 

Тест № 1. "Десять" Справочник  содержит 6-уровневый 10-арный граф , имеющий 1 000 000 различных ветвей и при обходе такого графа таблица ВремТаблица6 на выходе цикла алгоритма содержит 1 000 000  записей. Проще говоря, корневому элементу подчинены 10 элементов, каждому из которых подчинен одинаковый набор из десятка следующих элементов и т.д.

Ориентиром для меня служил пост № 118 из темы http://forum.infostart.ru/forum14/topic35991/ :

Через таблицу значений в 77 это сделать сложнее.  У вас отсутствует команда НайтиСтроки , выбирающая по фильтру нужные строки из таблицы значений. Ну, раз взялся , то помни : - контроль зацикленности каждой ветки обязателен. 1. 4 мин - не о чем говорить 2. 3 мин - очень плохо 3. 2 мин - просто плохо 4. 1.5 мин - посредственно 5. 1 мин - хорошо 6. 40 сек - отлично 7. 20 сек - Арчибальд - СУПЕРСТАР на все времена ! ( в указанное время входит копирование элементов из справочника в таблицу значений)

Ну, и сразу получил 0.777 секунды, из которых 0.5 - преобразование графа и 0.276 - собственно разузлование (скрин 1). Отнюдь не 20 сек, как в упомянутой статье. Но похуже, чем в статье Как не «попасть на миллион», решая задачу разузлования , хоть и не на два порядка.

Ладно, думаю, попробуем 100 000 000 (скрин 2). 0.993 секунды.

Добрался аж до 100 000 000 (скрин 3). 1.525 сек. То есть "деревья" (которые и не деревья вовсе, на самом-то деле) из Теста №1 обходить неинтересно.

А вот заполнять список дуг (справочник Наборы) произвольным (псевдослучайным) образом, находить в полученном графе вершины, не имеющие родителей (корни), и разузловывать сразу все эти корни, либо несколько (по отметкам в списке корней) – достаточно познавательно (скрин 4). Все-таки 3.02 секунды. Правда, разузловывались десять позиций. Бывает и больше.

Все действия производятся в форме справочника Наборы. В частности, на форме кнопки для двух вариантов заполнения исходного справочника. Кнопка Преобразовать запускает конвертацию представления графа дугами в представление вершинами. Все коды открыты. В архиве – сохраненная конфигурация.

Попробуйте поиграться!

Ну и, наконец, вывод. Успешность (эффективность) решения задач весьма призрачно зависит от платформы. Зато сильно зависит от спроектированной структуры данных... 

 

29.11.2010. Еще несколько слов о задаче разузлования. Теоретическая сложность этой задачи - О(N * lg N), где N - число (различных) узлов графа. Именно так вел бы себя алгоритм в упомянутой статье "Запрос против рекурсии...", если бы автор не отказался от конструкции "СГРУППИРОВАТЬ ПО" и не искал вместо ошибочной дуги графа все ошибочные цепочки, порожденные этой дугой. Применительно к задаче разузлования такой подход не учитывает наличия стандартизации узлов и деталей - а она реально существует. Гайка М10х17 - она и есть гайка...

 

 

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

Наименование Файл Версия Размер Кол. Скачив.
10Cv7.zip
.zip 33,48Kb
26.11.10
46
.zip 33,48Kb 46 Скачать

См. также

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

Комментарии

1. Сергей (ildarovich) 26.11.10 17:05
Две просьбы:
1. Перепишите, пожалуйста, абзац с упоминанием моей статьи, а то с лету кажется, что описанное в моей статье решение занимает 20 секунд, хотя на самом деле результат правильной программы, описанной в моей статье - 0,122 секунды! Там же есть скриншот графа с 33-мя уровнями, который решается за 3,5 секунды. Разница между Вашими и моими результатами - в 5 раз (0,122 и 0,777). Это преимущества платформы. Могу обосновать.
2. Давайте называть вещи своими именами: в задаче, которую Вы решили за 0,777 секунды НЕТ ДЕРЕВА! Там есть граф из уровней с 0-го по 6-ой, вершины в смежных уровнях которого попарно связаны! В моей статье, есть рисунок этого графа, программа рисования которого на 8 занимает 10-ть строк! В ДЕРЕВЕ ветви принципиально не пересекаются! А вот преимущества запросов в немоей статье обосновываются их якобы хорошей работой для структур типа ДЕРЕВО. Там реально создаются в базе и связываются спецификациями 1 111 111 номенклатур. В том дереве 111 111 дуг! Но даже в этом случае реальные результаты рекурсии лучше!
support; hogik; Арчибальд; +3 Ответить 2
2. Александр Рытов (Арчибальд) 26.11.10 17:17
(1) Согласен. Подредактировал.
3. Александр Рытов (Арчибальд) 26.11.10 17:40
(1) Кстати, рекурсия полностью эквивалентна "бесконечному" циклу. Рекурсивная процедура, вообще говоря, выглядит так:


Процедура Проц() 
   //что-то сделали, при этом изменилось контекстное окружение 
   Если ПораЗаканчивать Тогда 
      Возврат;//контекст - из стека 
   Иначе 
      Проц(); //контекст - в стек ОС 
   КонецЕсли; 
КонецПроцедуры
...Показать Скрыть


То же самое делает цикл

Пока 1=1 Цикл
   //что-то сделали, при этом изменилось контекстное окружение
   //возможно, потребуется "затолкать" это окружение в некий самодельный "стек"
   Если ПораЗаканчивать Тогда
   //возможно потребуется извлечение из стека
      Прервать;
   Иначе
      Продолжить;
   КонецЕсли;
КонецЦикла
...Показать Скрыть

Так что сравнивать имеет смысл Запрос vs Рекурсия/Цикл, а не Рекурсия vs Цикл
ildarovich; hogik; +2 Ответить
4. Владимир (hogik) 26.11.10 19:25
(0)
Ставлю "плюс" на публикацию за сам алгоритм.
А с точки зрения СУБД доказано (показано), что много записей в БД - плохо, а мало - хорошо. А много бесполезных записей - очень плохо. Но это уже другая тема - тема про "запросы". ;-)
Шёпот теней; +1 Ответить 1
5. Игорь Исхаков (Ish_2) 27.11.10 20:21
(4) Вы меня удивляете , Владимир. Вы ведь знаете эту задачу ,её цену и сами её решали. Человек щелкнул миллионный граф за секунду....
Вместо того, чтобы предостеречь Арчибальда - Вы его поощряете.
Я сейчас я ему вроде как конкурент, меня он не послушает , а Вы то что ?
6. Владимир (hogik) 27.11.10 23:21
(5)
Игорь.
Я четко понимаю (знаю), что Александр решал совершенно другую задачу. И Сергей - другую. Но еще, я четко понимаю, что вы ставите и решаете "свою" задачу из-за отсутствия "нормальных" средств для её решения. Типа, жизнь заставляет.

ДалееРассуждизм.
Есть такое выражение: "Если изнасилование неизбежно, то надо расслабиться и получить удовольствие." Вы расслабились, получаете... ;-) Но это не означает, что следует пропагандировать такую схему получения "удовольствия". Т.к. на самом деле больше всего удовольствия получает "насильник". А Вы его поощряете к дальнейшим деяниям, подставляя множество очередных жертв. Соучастник, Вы - наш... ;-)
КонецРассуждизма.

Вот, написано:
"Успешность (эффективность) решения задач весьма призрачно зависит от платформы. Зато сильно зависит от спроектированной структуры данных..."(с)

Т.е. думать и работать надо. А не искать готовые решения, типа: 1С, 2С...nC...."СКД"...0С.
Я Вашу "деятельность" называю поиском "Волшебной палочки".
Но, это очень мягко сказано... :-( :-( :-(
7. Игорь Исхаков (Ish_2) 28.11.10 01:09
8. Владимир (hogik) 28.11.10 05:48
(7)
Игорь.
А как может быть ещё?
Я ничего нового Вам сказать не могу.
Я задаю Вам вопросы - Вы не отвечаете.
Ну, хоть, в этой теме ответьте мне на простые вопросы.
Как дерево из 1111111 узлов может использоваться для описания "разузлования, спецификаций..." 60 изделий? Это специально под запросы и 20 секунд сделано?
И почему Вы никак не комментируете результат по скорости на задаче в 1111111 номенклатур? А значение на ADS-е без запросов 20-35 секунд в "файловом" режиме, и 60-70 секунд в клиент-серверном режиме, именно, для 1111111 номенклатур. И почему при написании этого моего алгоритма на языку 1С-а время становится за 200 секунд? Или Вам пояснить Вашу же фразу "...если реализовать задачу на Си или Delfi, то удастся достичь лучшего быстродействия, чем указано в теме ?"(с)
Эх...
P.S. Прощу прощения у Автора данной темы. Но меня, опять, возмутил призыв Игоря к объективности при сравнении "абсолютных величин"...
9. Игорь Исхаков (Ish_2) 28.11.10 07:51
(8) Перескакивать не будем. Сначала разберемся с разработками Сергея и Арчибальда .
Там ,слава Богу, разговор пошел "узко-конкретный".
10. Владимир (hogik) 28.11.10 19:32
(9)
Игорь.
"разговор пошел "узко-конкретный"."(с)
Да, уж... Очень - конкретный:
2 > 1 - верно.
2 грамма > 1 килограмм - ошибка.
2 грамма > 1 миллиметр - бред !!!
Сравнивайте решения для различных 1111111 номенклатур.
Или вернитесь к "изначальному" описанию схемы БД:
СвойID, РодительID, Количество, СсылкаНаНоменклатуру
Т.е. не извращайте схему БД под удобства решения частной задачи запросами.
Частных задач ("узко-конкретных") очень много - схем БД не напасётесь... ;-)
Извините. Повторяюсь. Всё написано в форуме ещё до публикации Ваше статьи. :-(
11. Игорь Исхаков (Ish_2) 28.11.10 19:42
(10) Браво , Владимир !
Смотрите тему , развязка близка.
12. Александр Рытов (Арчибальд) 29.11.10 09:54
Как моя оценка сложности/времени (N * lg N / 10000) сек. соотносится с реальностью для деревьев с уникальными узлами:
1<10<10<10<10<10<10 (~ 1 000 000 узлов) оценка 600 реальность 630
1<10<10<10<10<10 (~ 100 000 узлов) оценка 50 реальность 40
1<10<10<10<10 (~ 10 000 узлов) оценка 4 реальность 3.3
1<10<10<10 (~ 1 000 узлов) оценка 0.3 реальность 0.3
1<10<10 (~ 100 узлов) оценка 0.02 реальность 0.12


13. Владимир (hogik) 30.11.10 03:05
(12)
Александр.
А Вы запустите свою программу под отладчиком.
И посмотрите на "качество" компиляции/интерпретации операторов 1С по времени. Не ввода/вывода, а умножения, деления, сложения, вызова функций, СоздатьОбъект() и т.д.
Эта скорость 30-и летней давности!!!
Я такую скорость имел на IBM/370 (Ряд 2, ЕС-1045).
Я замерял время выполнения инструкции: x=x+a[i]*a[i].
На "Си" это выполняется в 1000 раз быстрее чем на 1С.
А время ввода/вывода можете считать как, порядка, 30 секунд для чтения 1111111 записей по ключу. В случае DBF в локальном режиме, думаю, и того меньше.
И еще печальный факт про "1С 7.7".
Методы внешней компоненты вызываются медленнее чем родная функция 1С-а.
Т.е. если расчетные алгоритмы пытаться ускорить на ВК, то весь алгоритм в неё и придется помещать.
14. Владимир (hogik) 30.11.10 04:01
(12)
+13
Думаю, в Вашем алгоритме поможет turbobl и пересоздание индексов.
Ну, а в сетевом режиме будет всё плохо.
Только "охват" транзакцией всего куска алгоритма в части чтения БД.
15. Александр Рытов (Арчибальд) 30.11.10 07:34
(13)
А Вы запустите свою программу под отладчиком.
А что такое отладчик? © Вовочка :D
16. Игорь Исхаков (Ish_2) 30.11.10 11:54
(0) Там , слава Богу, мы закончили. Теперь здесь на правах вольного стрелка :
Именно так вел бы себя алгоритм в упомянутой статье "Запрос против рекурсии...", если бы автор не отказался от конструкции "СГРУППИРОВАТЬ ПО" и не искал вместо ошибочной дуги графа все ошибочные цепочки, порожденные этой дугой. Применительно к задаче разузлования такой подход не учитывает наличия стандартизации узлов и деталей - а она реально существует. Гайка М10х17 - она и есть гайка...


Так вот оно что ! Я твой алгоритм не проверял , но теперь все понятно , как ты контролируешь зацикленность .

Секрет СУПЕРскорости представленных обработок один -
отказ от надежного гарантированного контроля зацикленности каждой ветки.
К чему это приводит - почитай в теме "Запрос против.." , чем закончились тестирование обработки Сергея на зацикленность.
Ведь если бы Сергей исправил вторую ошибку - я бы подросил ему уже заготовленную третью.. И латал бы он свой СУПЕРбыстрый алгоритм до бесконечности.
Если у тебя в алгоритме нет надежного контроля зацикленности ,
то ты тоже мог оказаться в положении Сергея : то ли
- признать ненадежность своего алгоритма и тогда все предыдущие утверждения , СУПЕРхарактеристики , сравнительные таблицы полетят в тартарары
- то ли ли просто прекратить разговор дескать Нет ! и всё.

Так вот .
"СГРУППИРОВАТЬ ПО " не применяется в алгоритме именно потому , что нужно контролировать КАЖДУЮ ВЕТКУ графа. Применение этой опции приводит к резкому ускорению в тесте №1 (тот самый опрометчивый "щелчок за секунду" как в товей обработке) , но потере контроля зацикливания каждой ветки.
17. Александр Рытов (Арчибальд) 30.11.10 13:21
(16) У меня есть контроль зацикленности. Для каждого узла проверяется, не пересекаются ли множества его предков (всех) и "сыновей". Контроль абсолютен.
18. Игорь Исхаков (Ish_2) 30.11.10 13:45
(17) Если у тебя контроль абсолютен , то ты не можешь применять ".Свернуть(...)" для промежуточной таблицы - ты потеряешь ветки для контроля и тогда непонятно твоё выступление по поводу "СГРУППИРОВАТЬ ПО".
19. Александр Рытов (Арчибальд) 30.11.10 14:33
(18) "Сгруппировать по" у меня в кавычках. Я группирую перечень предков узла.
Т.е. как бы для ТЗ с колонками "Узел","СписокПредков" делаю ТЗ.Свернуть("Узел","СписокПредков"). Реально так:

Для ы = 1 по ТекСписок.РазмерСписка() Цикл
ТекЗнач = ТекСписок.ПолучитьЗначение(ы);
Если ПромРез.СписокПредков.НайтиЗначение(ТекЗнач) = 0 Тогда
ПромРез.СписокПредков.ВставитьЗначение(ы,ТекЗнач);
КонецЕсли;
КонецЦикла;
20. Игорь Исхаков (Ish_2) 30.11.10 15:42
(19) Вот тебе и поспорить с Владимиром. У него ведь тоже 77.
И он-то реализовал миллионный граф 1-10-10-10-10-10-10 с уникальными узлами за 180+-40 сек ,
а у тебя 600 сек. Разница впечатляет.
21. Игорь Исхаков (Ish_2) 30.11.10 17:59
(19) У тебя ПромРез имеет два поля Узел,СписокПредков.
Пусть в твоей таблице ПромРез колонка СписокПредков - это строка (у меня это "СтрокаКодов") и тогда ТекСписок содержит строковые коды справочника+ символ разделителя:

Для ы = 1 по ТекСписок.РазмерСписка() Цикл
ТекЗначКод = ТекСписок.ПолучитьЗначение(ы);
Если Найти(ПромРез.СписокПредков,ТекЗначКод) = 0 Тогда
ПромРез.СписокПредков = ПромРез.СписокПредков+ТекЗначКод;
КонецЕсли;
КонецЦикла;

Если так ,то не быстрее ли ?
22. Игорь Исхаков (Ish_2) 01.12.10 07:59
(0) Виноват. Только сейчас прочитал содержание темы. Читал и хмыкал.
Погнавшись за званием
7. 20 сек - Арчибальд - СУПЕРСТАР на все времена !

ты попал в ловушку. И влетел на 10 мин. в главном тесте.
23. Александр Рытов (Арчибальд) 01.12.10 08:00
(21) Оптимизацией я не занимался вообще. Возможно, ты прав.
24. Александр Рытов (Арчибальд) 01.12.10 09:22
(22) Черта с два. Прочитай еще раз твой текст теста №1 -
каждому из которых подчинен одинаковый набор из десятка следующих элементов и т.д.
- там я в секунду уложился, т.е. в 20 раз лучше, чем с твоими запросами ;) . А специально под конкретный граф "заточки" не было - алгоритм универсален.
25. Игорь Исхаков (Ish_2) 01.12.10 09:24
26. Игорь Исхаков (Ish_2) 02.12.10 09:27
Арчибальд , скачал твою конфигурацию - сижу тыкаюсь...
Ты мне скажи сколько зацикливаний определит твоя программа для нижеследующего графа.
Прикрепленные файлы:
27. Александр Рытов (Арчибальд) 02.12.10 10:20
Если граф такой, как на рисунке (твою табличку не очень понимаю) - найдет одну ошибочную ветку (выделена цветом
Прикрепленные файлы:
28. Александр Рытов (Арчибальд) 02.12.10 10:26
На таком - тоже одну
Прикрепленные файлы:
29. Александр Рытов (Арчибальд) 02.12.10 10:26
А на таком - две
Прикрепленные файлы:
30. Александр Рытов (Арчибальд) 02.12.10 10:34
А на таком - 4
Прикрепленные файлы:
31. Александр Рытов (Арчибальд) 02.12.10 10:46
Я понял! Тебя интересует такая ситуация, как на картинке. Мой ответ - 2. А вот у тебя, похоже, побольше :D
Прикрепленные файлы:
32. Игорь Исхаков (Ish_2) 02.12.10 11:07
Теперь я ничего не понял. Ты о чем ?

У меня на рисунке в (26) нарисовано дерево -
совершенно стандартный во всех пакетах мира вид.


Элемент "ОшГ000001" имеет двух детей : "ОшД0000001" и "Я зациклен..." и так далее.
У меня один простой вопрос : сколько, каких зацикленных элементов (или ветвей) покажет твоя программа ?
33. Игорь Исхаков (Ish_2) 02.12.10 11:22
Или полсмотри как это выглядит в твоем справочнике :
Прикрепленные файлы:
34. Александр Рытов (Арчибальд) 02.12.10 11:32
Понял. Ответ - 2. Не 4!
Суть в том, что ты из графа делаешь дерево, дублируя подграфы, а я работаю с произвольным графом непосредственно. Только в качестве начальной выбираю вершину, не имеющую предков.
Прикрепленные файлы:
35. Игорь Исхаков (Ish_2) 02.12.10 13:31
Что такое АБСОЛЮТНЫЙ КОНТРОЛЬ ?
Разложим граф на элементарные ветки
(пытаемся двигаться от корня по каждой ветке,пока по ней и только по ней, не встретим зацикливания) :

1. Корень -  КОшД01         - КошЕ01 - КОшД01                    - зациклен элемент "КошД01"
2. Корень -  КОшД01         - КошЕ01 - К я зациклен !   - КошЕ01 - зациклен элемент "КошЕ01" 
3. Корень -  К я зациклен ! - КОшЕ01 - КОшД01           - КошЕ01 - зациклен элемент "КошЕ01" 
4. Корень -  К я зациклен ! - КОшЕ01 - К я зациклен !            - зациклен элемент "К я зациклен !"

Вопрос : А с чего это я взял , что именно так жестко нужно проходить от корня - по каждой ветке
и не используется пред . информация о том что какой-то элемент зациклен ?
А с того, что в таком случае мы не зависим от порядка обхода графа и выдаем ПОЛНУЮ(всю) информацию о зацикливаниях в виде дерева(графа).
Как только мы начинаем использовать пред. информацию о зацикливании, то в попадаем зависимость от порядка обхода графа. И начинаем выдавать разный состав зацикленных элементов в зависимости от порядка обхода.
А это полная жуть ! Поиграйся порядком пунктов обхода 1-2-3-4, 4-3-2-1 и т.д. , учитывая пред.зацикливания, и получишь разный состав зацикленных элементов.

Поэтому НУЖЕН АБСОЛЮТНЫЙ КОНТРОЛЬ !
И правильный ответ - 3 элемента. Только 3 элемента дают полную постоянную информацию о зацикливании.
Как граф не обходи -получишь 3 элемента.
36. Игорь Исхаков (Ish_2) 02.12.10 13:53
Продолжим.
У тебя , Huse, Сергея - контроль зацикливания относительный (облегченный).
Отсюда и СУПЕРскорости . Если попытаться организовать такой надежный контроль в ваших алгоритмах - то всё.
Всему КОНЕЦ.
Конец скорости, конец надежности
(памяти клиента может и не хватить для хранения стольких строк(веток) графа).
Таков мой скромный прогноз.
37. Александр Рытов (Арчибальд) 02.12.10 14:21
На картинке в 26 посте у тебя 6 красных строчек. Не 2 - по числу ошибок. И не три - по числу вершин, входящих в циклы.
А гшраф, нарисованный здесь опять-таки, по моему варианту даст 1 (дугу), по твоему алгоритму - 5 (позиций в "дереве"), а по соображениям из (35)долже бы дать 2 (вершины).
И насчет начала обхода. Мой алгоритм выявляет все возможные корни (стартовые для разузлования) и позволяет "с кнопки" находить все ошибочные дуги.
Наконец, о безызбыточности. Ты все время говорил, что вся информация о графе должна содержаться в ТЗ {Отец,Сын,Количество}, т.е. в перечне дуг графа. Если даже поиск циклов дает тебе перечень узлов - куда ты его денешь? У меня все ясно: помечу на удаление ошибочный элемент (или даже обнулю поле Количество) и продолжу работу. В конце концов, исходной задачей было разузлование, а не раскрашивание "дерева" из найденных в графе путей.
Прикрепленные файлы:
38. Игорь Исхаков (Ish_2) 02.12.10 15:02
Виноват не объяснил.
Это картинка из моей программы рисующей граф ошибок ,
на котором завалился Сергей . На красный цвет не нужно обращать внимание.

Давай для простоты ориентируйся только на (33) - это практически тот же граф , но в табличном виде .

Итак , в (33) - наш граф. А (35) - все соображения по раскрутке этого графа.
Корень в графе - один . Это позиция номенклатуры с именем "Корень". (33)
Идя последовательно от "Корень" по таблице Справочника (33) мы вытащим всю цепочку.
в (35) показано , что всех возможных ветвей для позиции номенклатуры "Корень" может быть 4.
И далее по тексту (35). Ты согласен с этими рассуждениями ?

А ты изобрази своим рисунком граф в (33).
39. Александр Рытов (Арчибальд) 02.12.10 15:29
(38) См. картинку из (34) без А, Б, В (т.е. Корень - это Г).
40. Игорь Исхаков (Ish_2) 02.12.10 16:15
(39)
В машине рисунков нету. Нужно последовательно обойти весь граф (34)
побывав в каждом узле и построив все возможные ветки.
Двигаемся по одинарной ветке , пока не сработало зацикливание.
Напоминаю, зацикливание есть факт нахождение на любой из веток от корня до вершины двух одинаковых элементов.
Все ! такие факты мы должны выявить.

Начинаем движение вслепую.

Ветка 1. А-Б-В- Г- Я_тоже - Е - Я_ТОЖЕ. На последнем сработало зацикливание , движение прекращаем.

Ветка 2. А-Б-В- Г- Я_тоже - Е - Д - Е.

Ветка 3. А-Б-В- Г- Д - Е - Д.

Ветка 4. А-Б-В- Г- Д - Е - Я_Тоже - Е

Итого З элемента (Е- дважды)

И число 3 и состав Е,Д,Я_тоже НЕ ЗАВИСИТ от порядка обхода.

Если же мы начнем хитрить при обходе то потеряем элемент.
41. Игорь Исхаков (Ish_2) 02.12.10 16:33
Так вот я храню ВСЕ ветки 1-4. И по ним в любой момент могу построить ВЕСЬ граф на котором отображу ошибки для пользователя и он их быстро найдет.
Исправить сложные ошибки зацикливания - не так-то просто. У меня пользователь получит полную картину, где что лежит и что с чем связано. Вы граф не храните : у вас два элемента Е и Д НИЧЕГО не дадут пользователю и он полностью не увидит всю картину зацикливания. Т.е. функционал у меня в сто раз выше чем у тебя или Сергея .
Мало того , на больших объемах еще и обгоняет вас всех по скорости.
42. Владимир (hogik) 02.12.10 18:37
(41)
"Так вот я храню ВСЕ ветки 1-4. И по ним в любой момент могу построить ВЕСЬ граф на котором отображу ошибки для пользователя и он их быстро найдет."(с)
А если пользователей много? И они "в любой момент..."(с) ;-)
Игорь.
Ваш алгоритма не будет работать в "теме" СУБД.
Т.к. СУБД придумали не для удобства программиста писать запросы (отчеты).
А для обеспечения множества пользователей (алгоритмов) достоверной информацией из БД.
Ну не годятся "регистры накопления" для задач "разузлования". ;-)
43. Игорь Исхаков (Ish_2) 02.12.10 18:48
(42) Попытаюсь объяснить .
В начале обработки , копируется из базы Справочник (ВЕСЬ!) СпецификацииНоменклатуры во временную таблицу "Спецификации". На время копирования можно блокировать Справочник от изменений (пример демо и этого не показано). В дальнейшем работа идет только с временной таблицей. И никакие пользователи не мешают.

Необходимость блокирования Справочника на время исполнения всей обработки в статье не рассматривается вовсе.
Это отдельная тема другого разговора. В статье рассматривается узкий вопрос "алгоритм разузлования", сопутствующие вопросы не рассматриваются вовсе.
44. Игорь Исхаков (Ish_2) 02.12.10 19:01
(0) Саша, в (41) гордыня обуяла. Виноват.
45. Владимир (hogik) 02.12.10 19:42
(43)
1) "рассматривается узкий вопрос"(с)
Тогда уберите в свой статье фразы типа:
"На предприятиях ,осуществляющих сборку"(с)
"доходить в реальных задачах"(с)
"самый быстрый, надежный" (с)
"в статье идет речь не о "заточке" для тестов №1 и № 2, а об универсальной обработке"(с)
"достаточно для создания надежного и эффективного механизма "разузлования""(с)
"она более технологична и надежна"(с)
И т.д.
2) "В дальнейшем работа идет только с временной таблицей. И никакие пользователи не мешают."(с)
Ага. ;-)
Они просто работают с разными исходными данными. Один скопировал во временную таблицу. Работает. Другой пользователь уже "поработал" и начал менять исходную таблицу. А тут подоспел результат второго пользователя. И...
3) "Необходимость блокирования Справочника на время исполнения всей обработки в статье не рассматривается вовсе."(с)
Т.е. этой "необходимости" нетУ ??? ;-)
4) "Это отдельная тема другого разговора."(с)
Нет. Игорь. Эта не отдельная тема. Т.к. скорость выполнения алгоритма - это одна из многих характеристик алгоритма. И, далеко, не первая характеристика. Но любой алгоритм в "теме" многопользовательских СУБД ОБЯЗАН обеспечивать достоверность данных для ВСЕХ пользователей. Или "потребитель" системы будет решать задачу бесконечной "консолидации документов" даже в рамках ОДНОЙ подсистемы. И если "алгоритм" не обеспечивает требуемой достоверности, то это не алгоритм, а НЕЧТО. Но работает оооо-чень быстро. ;-)
5) "Попытаюсь объяснить"(с)
Игорь. Еще раз вынужден Вам ответить и на эту фразу.
Объясните ЭТО себе!!!
46. Игорь Исхаков (Ish_2) 02.12.10 19:52
(45) Всё будет хорошо, Владимир.
Давайте не портить тему Арчибальду. Ок.
47. Владимир (hogik) 03.12.10 05:23
(0)
Александру, про "отладчик". ;-)
Две программы.
Первая загружает в справочник "дерево" с 1111111 вершинами, из теста #1 от Игоря.
Вторая выполняет обход дерева рекурсивным методом с анализом циклов ;-) и подсчетом количеств "изделий". Каждая программа выполнялась три раза. Система 1С 7.7 на DBF, локально, монопольно. Но, в конфигурации определено 1007 таблиц. И одинаковое дерево представлено трижды. По файлу 1Cv7.DD - таблица "ДеревоА" на 8-ом месте, "ДеревоБ" на 508-ом месте, "ДеревоВ" на 1007-ом месте. Остальные таблицы БД - пустые.
Времена загрузок "дерева":
ДеревоА 148 сек.
ДеревоБ 615 сек.
ДеревоВ 1083 сек.
Времена обходов "дерева":
ДеревоА 194 сек.
ДеревоБ 673 сек.
ДеревоВ 1136 сек.
А мы тут про "графины" разговариваем... :-(
P.S. В комплексной конфигурации многие "боевые" таблицы находятся в конце файла DD.
P.P.S. При проведении тестов вентилятор процессора ревел на полную мощность. ;-)
Арчибальд; +1 Ответить
48. Александр Рытов (Арчибальд) 03.12.10 08:54
(40)
Начинаем движение вслепую.
Я не хочу вслепую. Начинать движение имеет смысл от тех узлов, которые не имеют предков. А если таких узлов нет, значит в графе полный бардак: Все узлы расположены на путях, содержащих циклы. Идем от корня.

Шаг 1. (А)(А-Б). Норма.
Шаг 2. (А,Б)(Б-В). Норма.
Шаг 3. (А,Б,В)(В-Г). Норма.
Шаг 4. (А,Б,В,Г)(Г-Д)(Г-Я_тоже). Норма.
Шаг 5. (А,Б,В,Г,Д,Я_тоже)(Д-Е)(Я_тоже-Е). Норма.
Шаг 6. (А,Б,В,Г,Д,Е,Я_тоже)(Е-Д)(Е-Я_тоже). Две ошибочные дуги. Их и отмечаем как ошибочные в справочнике дуг (исходном или его копии) Больше ошибок в справочнике (графе) нет.

И число 3 и состав Е,Д,Я_тоже НЕ ЗАВИСИТ от порядка обхода.
Если же мы начнем хитрить при обходе то потеряем элемент.
Обойди "бесхитростно" граф на рисунке, начиная с узла Е (Г,Д,Я_тоже). Не получается? Правильно, начиная откуда попало, ориентированный граф не обойдешь. Т.е. твой алгоритм точно так же зависит от порядка обхода, как и мой - только я это заранее предусмотрел, и не позволяю начинать откуда попало.
В машине рисунков нету
А как же http://infostart.ru/public/78976/ ;)
Прикрепленные файлы:
49. Игорь Исхаков (Ish_2) 03.12.10 09:19
(48)
А я тебе еще раз говорю : ты должен выдать весь список зацикленных элементов.
Ты мне сказал ДВА.
Я тебе говорю ТРИ !
и спрашиваю : Чем Я_тоже - хуже(лучше) чем Е и Д.
Или Чем Е хуже (лучше) , чем Я_Тоже и Д ?
Соображения как мы обходим граф, какие там дуги, когда в нем бардак или нет не имеют никакого смысла.

Еще раз : зацикливание есть факт нахождения на одной элементарной(одинарной) ветке графа одного и того же элемента в качестве "ребенка" и "родителя".
Точка.
"Вынь и положь" такие факты на стол. Любым способом !
Этот факт обнаруживается в текущем графе для ТРЕХ элементов. Е,Д,Я_ТОЖЕ.
Этот способ я описал.

Какой в этом практический смысл и что это дает ?

Исправить ошибку зацикливания не так-то просто - пользователю нужны ВСЕ зациклившие элементы, которые должны быть отображены на графе. Ему нужно видеть полную картину , как у тебя на рисунке , только подсвечены красным цветом Е,Д, Я_ТОЖЕ.
Чтобы выдать эту полную картину , мы должны иметь все три элемента и все их ветки.

P.S. Я тебе обойду граф с любого места (получу два графа : "все родители" и "все потомки") . Могу и с Е.

Другими словами, ты идешь в своих рассуждениях от программиста, от того , как удобно обходить граф,
А я иду от пользователя , ему удобнее видеть ВСЕ зацикленные элементы.
50. Александр Рытов (Арчибальд) 03.12.10 09:40
(49)
А я тебе еще раз говорю : ты должен выдать весь список зацикленных элементов.
Это у тебя юношеский максимализм :D
Берем граф из знаменитого теста № 1 и добавляем одну ошибочную дугу (см. рис.). При поиске циклов я одну дугу и найду - это то, что я реально должен. А ты найдешь 10 000 цепочек. То-то обрадуется твой пользователь ;).
Даже если ты выдашь ему список из 42 узлов - мало не покажется. Все равно это необозримо, и значит, бесполезно. Мы же прикладную задачу решаем, а не абстрактную.
Пишите, Шура, запросы. Внутри они золотые © Паниковский
Прикрепленные файлы:
51. Александр Рытов (Арчибальд) 03.12.10 09:47
(49)
Я тебе обойду граф с любого места (получу два графа : "все родители" и "все потомки") . Могу и с Е.
В тебе я не сомневаюсь. А вот твоя обработка ЗапросПротивРекурсии не обойдет.
52. Игорь Исхаков (Ish_2) 03.12.10 09:48
(50) Я записал в красную книжицу : "4. обозвал Балагановым".

Конечно , ты старый и умный.. хихикаешь над нами , над молодежью.
Так вот, я тебе с юношеским максимализмом толкую :
программа обработки графа должна зафиксировать ВСЕ факты зацикливания,
а как их потом будет обрабатывать пользователь или промежуточная программа представления ошибок
- это не её ума дело. Зафиксируй и полоЖь !
53. Игорь Исхаков (Ish_2) 03.12.10 09:53
(51) Обработка ЗапросПротивРекурсии.epf работает только в одну сторону ищет "детей".
Поэтому обойдет и получит только граф детей для Е.

Е-Д-Е
Е-Я_Тоже-Е
54. Александр Рытов (Арчибальд) 03.12.10 09:59
(52)
промежуточная программа представления ошибок
Еще и отдельную программу представления ошибок приплел :D Будь проще, и люди к тебе потянутся. Есть справочник дуг (больше, по твоему условию, нет ничего), пометил в нем ошибочные на удаление - вот и все представление.
55. Игорь Исхаков (Ish_2) 03.12.10 10:15
(54) Ага, приплел. В моей обработке она есть.
А как бы я тогда анализировал ошибки , подбрасывал Сергею то одно ,то другое ?

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

На рисунке представление обработки ошибок из ЗапросПротивРекурсии.epf
Прикрепленные файлы:
56. Игорь Исхаков (Ish_2) 03.12.10 10:41
Вообщем , я в своей теме написал уже. Надеюсь тебе понравилась вся эта история..
57. Александр Рытов (Арчибальд) 03.12.10 11:05
(55) Берем граф из (50) и получаем картинку, внятно описывающую ситуацию. И разузлование прошло с игнорированием ошибочной дуги. Это называется практика.
Сейчас нарисую граф совсем уж конкретно такой, как ты хочешь.
Прикрепленные файлы:
58. Игорь Исхаков (Ish_2) 03.12.10 11:18
(57) Арчибальд , я не смог ничего проверить и сымитировать в твоей программе.
Никаких средств контроля правильности обработки графа для пользователя не существует.
Вспоминал 77,тужился , пыжился , чертыхался..
Потом плюнул и написал тебе (26) , дескать скажи как оно будет ?
Давай лучше по рисункам графа. Стрелочки , картинки..
59. Александр Рытов (Арчибальд) 03.12.10 11:18
Вот
Прикрепленные файлы:
60. Игорь Исхаков (Ish_2) 03.12.10 12:29
(59) У тебя изумительный(!) есть рисунок проясняющий суть наших разногласий.

1. Допустим , обработка дошла до Б-В и говорит тебе человеческим голосом :
"Арчибальд , это зацикливание дальше нет смысла искать..
да и запутаться можем.. там сам черт ногу сломит !".
Ты как культурный человек и говоришь ей (тоже человеческим голосом) :
"Хорошо , родная , дальше не пойдем !"
И загрустил Арчибальд,так как увидел только одну ветку-обрубок : А-Б-В.

2. Допустим , обработка дошла до Б-В и говорит мне человеческим голосом :
"Ish_2 , это зацикливание дальше нет смысла искать..
да и запутаться можем.. там сам черт ногу сломит !".

Я ей говорю запросто :
"Молчи , дура ! Твоё дело искать ! "
И пошла она дальше , и нашла все ветки и принесла мне их.
Я и выбрал ,что и как показать на экране , а что не показывать.
Смотри ниже , что я увидел :
Прикрепленные файлы:
61. Александр Рытов (Арчибальд) 03.12.10 13:16
(60) Да ничего похожего. Спокойно помечает (исключает) ошибочную ветку и дальше движется. С разузлованием правильной части.
Прикрепленные файлы:
62. Игорь Исхаков (Ish_2) 03.12.10 13:40
(61)
Нет , Арчибальд , не отпирайся !
Главный художественный смысл - робость перед обработкой передан верно.
А где ты оробел то ли в Б-В , то ли на кольце Г-Д-Е-Я_ТОЖе - это детали.

Теперь конкретно :
ТЫ не ПОСТРОИЛ КОЛЬЦО ! У тебя только 3 зацикленных элемента.
Ты не выдал все 4(четыре) зацикленных элемента.
Байка - верна.
63. Александр Рытов (Арчибальд) 03.12.10 14:44
(62) Это уж вообще бред какой-то.
Ты все время талдычишь, что я не сделал того или другого. Я утверждаю, что делать это мне здравый смысл не позволяет, ты же мне - забудь, мол про здравый смысл, делай как я сказал.
Вот цитируем тебя
И загрустил Арчибальд,так как увидел только одну ветку-обрубок : А-Б-В.

2. Допустим , обработка дошла до Б-В и говорит мне человеческим голосом :
"Ish_2 , это зацикливание дальше нет смысла искать..
да и запутаться можем.. там сам черт ногу сломит !".

Я ей говорю запросто :
"Молчи , дура ! Твоё дело искать ! "
И пошла она дальше , и нашла все ветки и принесла мне их.
Первое утверждение опровергнуто картинкой в 61 посте. Граф полностью пройден, отмечены все ветки, приводящие к зацикливанию, разузлование корректного подграфа проведено.
Займемся утверждением "и нашла все ветки и принесла мне их". Понятно, что оно ложно в части "ВСЕ". Не найдено бесконечное количество веток:
А-Б-В-Б-В
А-Б-В-Б-В-Б
А-Б-В-Б-В-Б-В
А-Б-В-Б-В-Б-В-Б
А-Б-В-Б-В-Б-В-Б-В
...
Обработка твоя может, конечно, сказать что-то типа "тут мы уже не первый раз ходим, зациклились" - но это уже будет элемент здравого смысла, т.е. вроде бы западло для тебя. Значит, должен сказать "молчи, дура, еще не все ветки построены".
Возьми, нарисуй свою картинку для гафа из 37 поста - и все понятно будет...
А еще лучше - вот для этой картинки отработай. Выдай пользователю 16 дуг, 9 вершин и 8 цепочек.
Прикрепленные файлы:
64. Игорь Исхаков (Ish_2) 03.12.10 15:56
(63)
Ты все время талдычишь, что я не сделал того или другого. Я утверждаю, что делать это мне здравый смысл не позволяет, ты же мне - забудь, мол про здравый смысл, делай как я сказал.


Ммм... ну, талдычу.
Это такой способ("наезд"), попытка сблизить наши здравые смыслы , э... предложение взаимопонимания.
Первое утверждение опровергнуто картинкой в 61 посте.


Подтверждаю. Твоя обработка пройдет Б-В . Правда застрянет на кольце.
Сильно не придирайся к неточностям в байке.Она же - байка.

Займемся утверждением "и нашла все ветки и принесла мне их". Понятно, что оно ложно в части "ВСЕ". Не найдено бесконечное количество веток:


Ну, разумеется, не все. Ты очень , очень строг к художественной байке .
Конечно, речь идет о движениях по веткам до первого зацикливания.
И тогда всё становится понятно.
Прикрепленные файлы:
65. Александр Рытов (Арчибальд) 03.12.10 16:11
(63)
Подтверждаю. Твоя обработка пройдет Б-В . Правда застрянет на кольце.
Опять ложь. Мой алгоритм никогда не застревает. Он фиксирует все случаи, когда потомок узла встречается в перечне предков, и все случаи, когда начало и конец дуги совпадают. Он строит максимально возможный подграф без циклов и разузловывает его.
Приведенная картинка показывает, что дляграфа с одним циклом из двух узлов твой алгоритм находит три ошибки. Вполне очевидно, что такой алгоритм корректным считаться не может.
66. Игорь Исхаков (Ish_2) 03.12.10 16:25
А вот и самый первый пример. Как обработка ЗапросПротивРекурсии.epf
представила пользователю первый граф.
Прикрепленные файлы:
67. Игорь Исхаков (Ish_2) 03.12.10 16:56
Опять ложь. Мой алгоритм никогда не застревает.


"Застревает" - это значит не проходит и не показывает все зацикленные элементы .
Напоминаю, зацикливание есть факт когда в графе один элемент и "родитель" и "ребенок".
Ты не все такие факты определяешь - значит, именно застреваешь.

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


Может , Арчибальд, может.
После прохождения обработки я имею таблицу со строковой колонкой "СтрокаКодов" и три записи в ней:
А-Б-В-Г-В
А-Б-В-Г-В
А-Б-В-Г-В

Только по этой таблице и надо ориентироваться. Подчеркиваю, по ней и только по ней.
Эта информация служит исходной для визуального построения дерева.
Из неё мы получаем :
Фактов зацикливания обнаружено 3.
Различных Элементов зацикливания - 1.

Как уж изобразить это на экране - это мой вопрос. Как хочу так и рисую.
Что нужно показать пользователю ?
Если факты зацикливания, то с этой точки зрения картинка правильная.
Если максимально сжатое изображение то
Прикрепленные файлы:
68. Игорь Исхаков (Ish_2) 03.12.10 17:17
Слово "застревает" - здесь точное, на мой взгляд.
Т.е. у меня алгоритм "прёт во все щели" - он не интеллектуальный.
И в этом его сила. Нашлась связь - зацикливания нет - значит можно "переть" дальше.
Поэтому он и обходит больше ветвей , чем твой.

Вопрос для твоего алгоритма , появились новые ветки в графе- какие из них определит твой алгоритм :
Просьба по "буквам" показать путь прохождения твоего алгоритма , как идет движение и где стопорится.
Прикрепленные файлы:
69. Александр Рытов (Арчибальд) 03.12.10 17:38
(67)
"Застревает" - это значит не проходит и не показывает все зацикленные элементы .
Напоминаю, зацикливание есть факт когда в графе один элемент и "родитель" и "ребенок".
Ты не все такие факты определяешь - значит, именно застреваешь.
Еще раз. Зацикливание есть факт, когда ребенок числится среди предков отца (перечень предков включает и самого отца). Такой (и только такой) ребенок считается незаконным. Мой алгоритм находит всех таких детей (и выводит на печать вместе с отцами. Определяются все факты появления дуги, приводящей к зацикливанию.
Ну, а все цепочки предков, приводящие к отцу незаконного ребенка, остаются при этом вполне легитимными - соответственно, в перечень ошибок попадать не должны.
Играть можно с кем угодно, драться - только с равными © Д. Винтер
Для восстановления равенства (с учетом того, что я тебе сообщил свои результаты на твоих тестах) предлагаю тебе прогнать мой
Тест № 1А. "Десять+ошибка"
Справочник "СпецификацииНоменклатуры" содержит 6-уровневый 10-арный граф , имеющий 1 000 000 различных ветвей и при обходе такого графа таблица ВремТаблица6 на выходе цикла алгоритма содержит 1 000 000 записей. Но сам справочник "СпецификацииНоменклатуры" в своей табличной части содержит лишь 60 записей.
Проще говоря , корневому элементу подчинены 10 элементов, каждому из которых подчинен одинаковый набор из десятка следующих элементов и т.д.
"+ошибка" - это еще одна дуга, ведущая с 6-го уровня на 1-й

Ну и результаты сообщить, конечно. Мои прилагаю.
Прикрепленные файлы:
70. Игорь Исхаков (Ish_2) 03.12.10 18:03
(69) Арчибальд , давай так. По порядку.
Предки , дети , зациленности...

Я собираюсь доказать , что слово "застревает" здесь самое точное.
Это значит , что если твой алгоритм не показывает все связи для графа (68) ,
то слово "застревает" - здесь самое точное !

Действительно , Дано :
есть граф (68) описан нами на рисунке и в табличной форме.
Ничего запретного в нем - НЕТ. Он вполне реален.

Теперь мы говорим обработке - обойди его , мы хотим его увидеть.
А твоя обработка говорит :
Не-А. Дальше кольца я не пойду , не хоцца - там сложности!

Что имеем ? Имеем Реальный граф - и имеем обработку, которая его полностью
не обойдет и не покажет нам его !
А зачем нам такая обработка , Арчибальд? Какой в ней прок ?
Это покажу , это не покажу...

Обработка должна обойти весь граф , зафиксировать все зацикленности.
А что делать , с этой информацией , как её интерпретировать - это не ёё ума дело !
Поэтому фраза из байки "Молчи , дура ! Твоё дело - искать !" - более чем оправдана.

И сама байка (60) несет в себе четкий , неискажающий сути проблемы смысл.
71. Александр Рытов (Арчибальд) 03.12.10 18:25
(68) Да пожалуйста. Только не смогу показать где стопорится - нет такого места.
Итак, А=0,Б=1,В=2,Г=3,Д=4,Я_тоже=5,Е=6,Ж=7,З=8,И=9,К=10 (в смысле, Поз00010 на скрине).

По шагам (вызовам следующего уровня): слева список предков, справа - дуги-дети
1. (0)(0-1)
2. (0,1)(1-2)
3. (0,1,2)(2-3)
4. (0,1,2,3)(3-4)(3-5) детей теперь двое, так что шаг в две строчки будет
5. (0,1,2,3,4) (4-6)
(0,1,2,3,5) (5-6)(5-9) В этом поколении уже трое детей
6. (0,1,2,3,4,6) (6-4)(6-5)(6-7)
Фиксируем ошибочную дугу (6-4)и разрываем ее
(0,1,2,3,5,6) (6-7)(6-5) Дуги (6-4) уже нет!
Фиксируем ошибочную дугу (6-5) и разрываем ее.
Свертывем предков 7-го в один список (0,1,2,3,4,5,6,7)
(0,1,2,3,5,9) (9-10)
7. (0,1,2,3,4,5,6,7) (7-8)
(0,1,2,3,5,9,10)
8. (0,1,2,3,5,6,7,8)
Прикрепленные файлы:
72. Игорь Исхаков (Ish_2) 03.12.10 18:30
(71) Э... это что ? Нехорошо, Арчибальд, смеяться ..
73. Владимир (hogik) 03.12.10 18:43
(49)
Игорь.
Вы пишете: "...зацикливание есть факт нахождения на одной элементарной(одинарной) ветке графа одного и того же элемента в качестве "ребенка" и "родителя". "(с)
Но Ваш алгоритм это делает не в графе, а в "дереве".
Я Вам представил простейший алгоритм для решения задачи для "дерева". Хотя для "дерева" поиск циклов - это... ;-)
Вы "забраковали" мой алгоритм.
Почему?
А потому, что в моём решении нет ключевых, для Вас слов - "решить задачу надо запросами". И о чём тогда разговор в данной теме про "графины"? Давайте я Вам расскажу - почему очень многие задачи не следует решать запросами. Но это совсем другая тема - эта тема про запросы... ;-)
74. Игорь Исхаков (Ish_2) 03.12.10 18:53
Арчибальд, перенесем на воскресенье ? Время 18-50 .Идет ?
75. Игорь Исхаков (Ish_2) 03.12.10 19:02
Мда.. Успел только посмотреть мельком . Как же я это проверю ?
С Сергем было проще , я рисовал искусственные кольца в справочнике , какие хочешь - легко.
И сразу проверял результат. А тут... мамочки.
76. Сергей (ildarovich) 04.12.10 14:04
(71) Александр!
Желаю успехов разорвать, наконец, все ошибочные связи в рассуждениях Игоря.
Хотя у нас похожие подходы и выводы, возможно, мое понимание проблемы чем-то Вам поможет.
1. Игорь ошибочно считает, что контроль зацикленности - это перечисление всех циклов. Поскольку множество циклов - подмножество путей,
то задача оказывается NP-полной. Вы, как и я, понимете, что Заказчика интересует не миллион циклов, а неупорядоченное множество вероятно-ошибочных дуг,
которые нужно перечислить и дать на проверку оператору. Эта задача гораздо проще - в наихудшем случае сплошной зацикленности будет выдан полный список дуг,
существенно (слабо сказано!) более короткий, чем полный список путей. Также как если бы в IQ-тесте человека спрашивали: какая цифра в перечне кажется лишней,
а он отвечал бы перечнем чисел, содержащих ошибочные цифры!

Вроде бы все просто, да не очень! Есть пример, из-за которого Игорь "не доезжает".
Есть ациклический орграф (гамак): А->В, А->Г, Б->В, Б->Г, В->Д, В->Е, Г->Д, Г->Е. Если зациклить его дугой Е->Б, то Ваша обработка выдаст (и исключит) дуги Б->В, Г->Е (могу ошибиться).
Этот список не содержит действительно ошибочной дуги: Е->Б! Простой выход здесь в том, чтобы при обнаружении цикла в Вашем (и моем) алгоритме включить в
список подозрительных все дуги обнаруженного цикла, даже, если они окажутся потом лишними. Это не скажется на быстродействии и, возможно, будет последним аргументом
в пользу кодинга!

Я (в своем алгоритме) не спешу этого делать и вот почему: это не моя задача и не мой Заказчик. Для своего Заказчика я бы разработал специальный алгоритм, который позволил
бы указать место ошибки с максимальной точностью (найти минимальный разрез, делающие граф ациклическим). Идею этого алгоритма я изложил в теме Игоря (пост #177).
Сейчас не могу сказать, но, возможно, есть и более простой метод.

2. Мне кажется, что Игорь нечетко разделяет понятия графа и дерева. Для него граф - это такое компактное (и неудобное) представление дерева, вроде формулы
или теста для проверки "настоящих", "боевых" графов - деревьев. Хотя в жизни (но не в программах!) деревья встречаются гораздо реже. Видимо, занятия программированием,
анализ таких структур как справочники, интерпретация вложенных циклов, левого соединения в запросах, дали ему такое искаженное представление действительности. Из-за этого
он и проверяет свою и наши обработки прежде всего на деревьях, в результате чего результаты сравнения оказываются необъективными.
Арчибальд; +1 Ответить 2
77. Владимир (hogik) 05.12.10 00:06
(76)
Сергей.
Извините, вмешаюсь.
Вы пишите: "Игорь ошибочно считает, что контроль зацикленности - это перечисление всех циклов."(с) А я думаю, что Игорь ошибочно считает, что "контроль зацикленности"(с) является самой важной составляющей в обсуждаемых алгоритмах. Т.к. слово "цикл" - это единственный термин объединяющий обсуждаемые (разные!!!) задачи, проблемы, решения...
Игорь, в моём понимании, поставил вопрос - как обойти дерево минимальным количеством запросов и перенести хоть что-то из дополнительных (надуманных) действий с узлами дерева, на сервер. Обязательно - дерево! Обязательно - запросами! Обязательно - на сервер!
Больше Игоря ничего не интересует. Печально... И, чего мы обсуждаем?
78. Игорь Исхаков (Ish_2) 05.12.10 12:19
Арчибальд, все мои рассуждения относились к какой-то другой версии.
Скачал последнюю сегодня, но она отличается от старой которая была у меня.
Ведь мы же спорим именно о твоей текущей конфигурации.
Всё-таки лучше было меня явно предупредить о всех изменениях в твоей конфигурации с момента публикации.

На всякий случай,
сразу после опубликования я в свой файл обработки одно изменение Добавил колонку "Количество" на панели Спецификации.
Убрал лишнюю строку НачДата = Текущаядата(); И всё!
Как только началось тестирование в моей теме мой файл обработки неизменен как скала.
Алгоритм у меня не менялся вовсе с момента публикации.
Все мои утверждения о своей обработке касались именно этого неизменного алгоритма,
к тому же опубликованного основном тексте темы.
Если бы пришлось внести в него какие-то изменения - я бы обязательно объявил об этом всем собеседникам.
79. Александр Рытов (Арчибальд) 06.12.10 08:32
(78)
Предыдущие мои публикации Граф(ин) 7.7. и Граф(ин) 7.7. (дополнение) носили, скорее, умозрительный характер, имея одной из целей продемонстрировать, что деревья в частности и графы вообще вполне уживаются с семерочной платформой. Однако после появления статьи Запрос против рекурсии или "разузлование" номенклатуры мне просто некуда было деваться – и вот пришлось сваять небольшую конфигурацию для исследования «разузловательных» процессов.
Конфигурация, приведенная здесь, алгоритмически не менялась с момента публикации за исключением добавления двух "галочек "Не учитываль", т.е. не ограничиваться заданной длиной цепочек, и "Выводить ошибки" - печатать/не печатать перечень ошибочных дуг.
Ведь мы же спорим именно о твоей текущей конфигурации.
Вот именно. Странно было бы здесь спорить о конфигурации из предыдущей публикации, которая демонстрировала поведение алгоритма нахождения корректных цепочек максимальной длины в случайных графах.
(76) У меня нашлись бы дуги Б-В и Б-Г. ;) А подход у нас, естественно, похож, только я ищу не минимальный корректирующий разрез, а строю максимальное по количеству поколений семейство потомков выбранного предка. Да к тому же, позволяю выбирать в качестве "патриархов" только тех, кто предков не имеет. Таким образом, при появлении в Вашем примере дуги Е-Б я увижу, кроме появления двух ошибочных дуг, еще одно событие: исчезновение узла Б из списка патриархов.
80. Игорь Исхаков (Ish_2) 06.12.10 08:47
Начало дискуссии положил пост (26),задающий начальный пример

В (37) ты пишешь ссылась на (26):

А гшраф, нарисованный здесь опять-таки, по моему варианту даст 1 (дугу), по твоему алгоритму - 5 (позиций в "дереве"), а по соображениям из (35)долже бы дать 2 (вершины).

Это и послужило пружиной, толчком ко всей дальнейшей дискуссии.
Теперь же у тебя алгоритм выдает 2 дуги.
81. Александр Рытов (Арчибальд) 06.12.10 09:18
(80) Ссылаясь на (26), я написал в (37):
На картинке в 26 посте у тебя 6 красных строчек. Не 2 - по числу ошибок. И не три - по числу вершин, входящих в циклы.
Т.е. я указал, что ошибочных дуг в графе из (26), по моим подсчетам, две. И в (34) я это говорил. И в (59).

Ты же цитируешь из 37 поста ту часть, которая к 26-му отношения не имеет, а относится к другому графу, там же и изображенному. Этот граф имеет одну ошибочную дугу - это по-моему. А по-твоему - пять ошибочных цепочек.
82. Игорь Исхаков (Ish_2) 06.12.10 09:54
(81) Не люблю незаконченных дел.
У тебя сделана обработка "для сэбэ", заранее предполагая что тестировать её никто не будет.
Попытавшись интерактивно что-то создать в твоём справочнике я только чертыхался.
Если ты действительно хочешь узнать правду , насколько твой алгоритм надёжен.
Создай удобный интерфейс для проверки при помощи элемента дерева формексом или еще как.

Посмотри как сделано у меня :
Пользователь может без труда интерактивно задать любой граф, используя дерево.
Тут же проверить и увидеть ПОЛНЫЙ граф ошибок (см. 26).
Обработка в таком виде уже используется в УПП с легкими исправлениями.
Посмотри http://forum.infostart.ru/forum24/topic36726/message402436/#message402436

Я веду речь о том , что твою и мою обработки нужно выровнять по функционалу. В таком виде как у тебя - они не сопоставимы.

P.S. Важность тестирования любого утверждения явно вытекает из моей темы :
все рассуждалки...
соображения и размышлизмы...
цифирьки о сверхскоростях ...
разлетелись в дребезги после проверки.
83. Александр Рытов (Арчибальд) 06.12.10 10:57
(82) Обработка у меня выложена. Код открыт. Ошибок не найдено. Все тесты прогнаны. То есть о моем алгоритме известно все.
Теперь касательно твоей обработки. Она не прошла тест из 50-го поста (текстуально он продублирован как Тест № 1А в посте 69). Я уже не говорю, что тест на 10 миллиардов (как Тест № 1, только вместо 6 поколений 10) она вообще не сможет пройти. Вот где-то здесь несопоставимость функционала и проглядывает.
Пользователь может без труда интерактивно задать любой граф, используя дерево.
Тут же проверить и увидеть ПОЛНЫЙ граф ошибок (см. 26).
Поздравляю Вас, гражданин, соврамши © Коровьев
Что увидит пользователь на тесте № 1А "Десять+ошибка"? Да ничего!
И поясни мне, каков будет процесс интерактивного задания графа с картинки ниже.
Прикрепленные файлы:
84. Игорь Исхаков (Ish_2) 06.12.10 11:10
(83) Не спеши.
Так мы закончили рассматривать твою обработку ?
Ты считаешь , что пользователь должен лезть в код чтобы задать нужную ему ошибку зацикливания ?
И этого достаточно :
Обработка у меня выложена. Код открыт. Ошибок не найдено. Все тесты прогнаны. То есть о моем алгоритме известно все.


Кем не найдено ? - Тобой ?
Кем прогнаны ? - Тобой ?
Известно всё , кому ? - Тебе ?

Я тебе как раз и толкую о том , что автор разработки САМ должен создать удобный интерфейс
для проверки правильности своих суждений. Чтобы пользователь САМ интерактивно мог всё проверить и смоделировать ситуацию. У тебя этого просто нет.

И все твои утверждения повисают в воздухе - кто полезет ковыряться в чужом коде ?
85. Игорь Исхаков (Ish_2) 06.12.10 11:37
+84 Прежде чем предлагать другому тест при сравнительном анализе ,
ты должен показать другому тест на своей обработке:
ВОТ ОНО ! СДЕЛАЙ КАК У МЕНЯ !


Как я проверю правильность создания хотя бы одной ветки в твоём тесте 10-10-10-10-10-10..., интерактивно ?
Как внесу туда нужную ошибку ?
У меня это делается так : последовательно открываешь нужную ветку и видишь какие там элементы и сколько их ? Интерактивно открываешь часть графа (спецификацию) и правишь её .
То есть я не требую от тебя такого чего нет у меня самого.

Еще и еще раз повторяю если хочешь меряться - создай удобный интерфейс проверки твоей обработки.
Без этого ты можешь утверждать что угодно - НИКТО В ТВОЙ КОД проверять не полезет.
86. Александр Рытов (Арчибальд) 06.12.10 12:47
(84) При чем здесь спешка? Это ведь ты написал
Посмотри как сделано у меня :
Пользователь может без труда интерактивно задать любой граф, используя дерево.
Тут же проверить и увидеть ПОЛНЫЙ граф ошибок (см. 26).
Вот я и говорю: покажи. Не буду же я покупать БП или УПП, чтобы взглянуть. Ты покажи, я тебе на слово поверю.
И касательно удобного интерфейса для построения графов. Куда уж удобнее: вля каждой дуги указать начало, конец, количество (последнее - только для разузлования). Нет и не может быть других интерфейсов для "произвольных графов, заданных таблицей наборов {Отец, Сын, Количество}" - именно таким было твое начальное условие. Ну, а то, что в восьмерке есть встроенный объект "дерево", как в формексе, ничего не прибавляет к твоему алгоритму разузлования.
Ты обыгран на твоем поле и по твоим правилам - если в качестве правил брать условия задачи из твоей статьи, а не из комментариев к моей. Доказательство: Добавление всего одной ветки к твоему Тесту №1 ставит тебя в тупик. Это не висящее в воздухе, а твердо опирающееся на факты утверждение.
87. Александр Рытов (Арчибальд) 06.12.10 13:08
(85) Порверить меня легко, без залезания в код. На форме нажимаем кнопку "Заполнить деревом" - и прямо на той же форме списка в справочнике видим искомые 510 дуг. Это не миллион веток, как у тебя, это обозримо. Внести одну ошибку, как я предлагаю, - это внести одну строчку в список, 511-ю. Скрин в 69 посте легко воспроизводится.
Покажи мне картинку (твое дерево) для графа из 83-го поста. Я не требую от тебя ничего такого, чего у тебя, по твоим утверждениям, нет. Я даже не буду выяснять, как ты строил картинку. Короче, сделай хоть что-нибудь помимо безответственного трепа.
88. Игорь Исхаков (Ish_2) 06.12.10 13:21
Демо БП не нужно покупать. Покупается только платформа 1с8.
Посмотри сценарий. Здесь мы не делаем никакого разузлования.
Только смотрим и корректируем то , что создано тестом № 2
Прикрепленные файлы:
89. Игорь Исхаков (Ish_2) 06.12.10 13:29
Добавляю : в обработке помимо разузлования - создан специальный интерфейс , который позволяет без разузлования корректировать, просматривать,
Справочник СпецификацииНоменклатуры ( у тебя это "Отборы").
90. Игорь Исхаков (Ish_2) 06.12.10 13:47
Продолжаю. Обладая таким интерфейсом - за 15 мин я интерактивно создам такие кольца - ловушки , в т.ч. и звезды , что тебе и не снилось.
После запуска разузлования - тут же проверю у себя правильно ли сформировался Граф ошибок .
См.ниже
Заметь : пользователь имеет не обрубок какой- то ветки а ВЕСЬ ГРАФ , т.е. информацию удобную для анализа.
И тут же можно исправить ошибку или внести новую.
Прикрепленные файлы:
91. Александр Рытов (Арчибальд) 06.12.10 14:21
(90)
Обладая таким интерфейсом - за 15 мин я интерактивно создам такие кольца - ловушки , в т.ч. и звезды , что тебе и не снилось.
Много не надо. Мне достаточно звездочки из 87 поста. А ты все с деревьями только носишься.
Задача была не в создании доп. интерфейса работы со справочником, а в разузловании. Эта задача на твоих тестах у меня решается на порядок быстрее, чем у тебя. А отобразить заодно "дерево разузлования" - это вообще смехотворное дополнение.
92. Игорь Исхаков (Ish_2) 06.12.10 14:54
Понял. Разница в подходах к задаче - колоссальная.

Для меня - это прежде всего технологичное функциональное решение - рабочее место для человека , занимающегося спецификациями в реальной конфигурации, например БП 2.0. Первое требование - здесь простота и надежность контроля и доп.функционал.

Для тебя же - это прежде всего решалка тестов №1 и №2, а доп.функционал - это так для галочки.

Пожалуй при такой разнице в подходах - сравнительный анализ и правда невозможен.
93. Александр Рытов (Арчибальд) 06.12.10 15:14
(92) Ничего похожего. Покажи мне простоту контроля в твоей обработке на тесте 1А. Ну, хотя бы работоспособность.
Первое требование всегда - работоспособность. Именно в этом разница в подходах заключается. У тебя же все технологично (правда, без ответа на вопрос из 83 поста), но на реальном небольшом графе с 511 дугами не работает.
Без твоего сообщения о результатах теста 1А я вынужден констатировать, что твоя обработка, возможно, способна отловить ошибки на графе с десятком дуг, но в боевых условиях непригодна.
ildarovich; +1 Ответить 1
94. Игорь Исхаков (Ish_2) 06.12.10 15:28
(93) У меня уже есть именно такой тест № 3. Посмотри на верзнем рисунке в (88).
Сейчас пришлю отчет в скриншотах.
95. Игорь Исхаков (Ish_2) 06.12.10 15:36
Вот и сам отчет.Ты всегда можешь обратиться к любому восьмерочнику.
Он с легкостью нажмет две кнопки и получит результат. Он у меня равен 19 сек.

Но нужно добавить.
Во временной таблице после окончания работы "разузлования" у меня хранятся ВСЕ ошибочные ветки.
Но Количество ошибок выдаваемых пользователю на монитор у меня ограничено - 100 ошибок.
Безболезненно можно увеличить до 1 000 шт. Только зачем ?
Прикрепленные файлы:
96. Игорь Исхаков (Ish_2) 06.12.10 16:11
...Исправлено. Как ненужное....

Спор выхолащивается по смыслу. Пора завершать.
97. Владимир (hogik) 06.12.10 18:07
(82)
"Я веду речь о том , что твою и мою обработки нужно выровнять по функционалу. В таком виде как у тебя - они не сопоставимы."(с)
Гениально!
Тема, плавно, перешла в обсуждение интерфейса. Цвет обсуждать будем? ;-)
Игорь.
Вы уже себе доказали, что любую постановку задачи следует подгонять под доступные средства (инструменты) программисту. Что еще может сделать Ваш алгоритм с "деревом" кроме проверки циклов и подсчета "изделий"? Это всё, что требуется для "разузлования"?
98. Игорь Исхаков (Ish_2) 06.12.10 18:11
(97) Ладно , Владимир. Пустой спор.
99. Владимир (hogik) 06.12.10 18:22
(98)
Игорь.
Спор - с кем?
Лично, я с Вами не спорю. ;-)
Я Вам задаю вопросы.
Вы мне не отвечаете. :-(
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа