[NEDIS]

Доброго времени суток коллеги.
Хочу поделиться наработками по программке.
Сразу хочу попросить сильно меня не пинать в плане грамотности написания кода, начал изучать LISP только с весны этого года, благодаря dwg.ru. Наверняка я наделал неподъемную кучу косяков, поэтому очень рад буду выслушать рекомендации по оптимизации и рад буду любой оказываемой помощи.
Хочу выразить благодарность всем чьи наработки я использовал в частности: Кулику Алексею (aka kpblc), VVA и hwd (и остальных участников форума, кого я забыл упомянуть в силу своей некомпетентности).

Алгоритм Флойда (Проба пера).
Немного о содержимом:
1. Два файла Lisp Команды и Функции
2. DWG файл с планировками и тестовыми закладными устройствами «скелетами» по которым выполняется трассировка полилиниями.
3. Команды:
a. NEDIS-input-system-for-tracing – Команда создает набор примитивов по которым будет выполняться трассировка, обрабатывает эти примитивы и выдает конечные матрицы для трассировки.
b. NEDIS-tracing-point-to-point - Трассировка точка-точка (выбор пользователя).
4. Функции:
a. NDS-start-finish-for-Floyd - Находит ближайший примитив, точку пересечения с ним и узлы для трассировки
b. NDS-manipulation-for-Floyd - Создает определенного вида списки для дальнейшей обработки функцией NDS-solution-matrix-Floyd (Работает только с LWPOLYLINE и LINE)
c. NDS-solution-matrix-Floyd - Создает и решает матрицу Флойда и матрицу маршрутов (алгоритм взят от сюда http://khpi-iip.mipk.kharkiv.edu/lib.../din_0124.html )
d. NDS-tracing - Выполняем трассировку (т.е. находим кротчайший путь по matrica-route-end, проверяя возможность такого пути по matrica-floyda-end (не должен рассматриваемый элемент быть равен "NO") получаем список узлов оптимального маршрута)
e. dwgru-geom-point-on-line - Проверяет принадлежность точки отрезку
f. pln - Создает полилинию по списку вершин lst, c - nil/T - разомкн/замкнт или '(с слой цвет)
5. Логику работы программ объяснять не буду, старался внутри все пояснять. По мере обсуждения буду «повествовать» почему делал так.
6. Основная проблема кроется в функции NDS-solution-matrix-Floyd шибко долго она решает Вариант 1 планировки. Вообщем-то это и понятно, так как чем больше точек для построения матрицы Флойда тем больше циклов оня будет проделовать (а их три и они все внутри друг друга). Над оптимизацией сам не работал, сильно загружен по работе.

Алгоритм Дейкстры (Проба пера-2).
Оказался наиболее шустрым.
Некоторые нюансы:
1. Иногда вылетает ошибка типа переменной (непосредственно уже при трассировке) – думаю где-то намутил с обработкой списков (не разбирался), надеюсь с помощью однофорумчан ее решить.
2. Полилиния не должна сама себя пересекать, функция не увидит такую точку пересечения и, как следствие, не будет создано корректное разрешение для этой точки
Отличая от предшественника:
1. Взамен NDS-manipulation-for-Floyd пришел NDS-manipulation-for-Dijkstra с соответствующими доработками, сильно его не менял – времени нету, но укоротить код можно прилично для быстродействия.
2. По замечаниям более опытных коллег убрал лишние setq.
3. NDS-solution-Dijkstra – создает разрешения для точек (от куда куда можно) все загоняет в одномерный массив (список).
4. NDS-tracing-all-in-one – функция определяет из 4-х вариантов трасс (1 – стартовая точка, ближайший узел справа от стартовой точки, … , ближайший узел справа от финишной точки, финишная точка; 2 - стартовая точка, ближайший узел слева от стартовой точки, … , ближайший узел справа от финишной точки, финишная точка; и т.д) наиболее короткую.

Ну вот такой винегрет получился .

[Vov.Ka]

Offtop: я бы посоветовал использовать Autodesk Map

[zamtmn]

Vov.Ka
Хороший совет... я бы понял если Map был бы бесплатен. а так он вообщето совсем не про то.

[NEDIS]

Сообщение от Vov.Ka Offtop: я бы посоветовал использовать Autodesk Map

Offtop: MAP не знаю и времени особо тоже нет его осваивать, есть какие-нибудь руководства толковые?

[Vov.Ka]

zamtmn, разница в цене между чистым акадом и мапом 10%, и почти все прибамбасы мапа пригодятся любому чертежнику

NEDIS, если есть возможность установить мап, то посмотри здесь http://www.theswamp.org/index.php?to...6521#msg366521
функция SolveLabyrinth ищет кратчайший маршрут по выбранным линиям

[NEDIS]

Так ... 13 просмтров архива и ниодного отголоска чего и как, у всех то работают команды? И как быстро?

Сообщение от Vov.Ka NEDIS, если есть возможность установить мап, то посмотри здесь http://www.theswamp.org/index.php?to...6521#msg366521 функция SolveLabyrinth ищет кратчайший маршрут по выбранным линиям

Интересная ссылочка, а вообще есть какой-нибудь user guide (желательно на русском)?

[zamtmn]

>>Так ... 13 просмтров архива и ниодного отголоска чего и как, у всех то работают команды? И как быстро?

Работают. NEDIS-input-system-for-tracing - как я понял строит граф? почему так медленно?

[ShaggyDoc]

13 просмтров архива и ниодного отголоска чего и как

Так там всякие матрицы-шматрицы, да еще какого-то бродяги Флойда. Мало кому интересна такая частная, редкая задача. По которой только сам автор знает, чего он хочет.

Чисто по коду, не вникая в алгоритмы.

1. В целом написано грамотно, работа большая проделана, интересная. Разделены функции и команды. Но:

2. Режут глаз многочисленные последовательные setq. "Хочется рвать и метать, рвать и метать!" (С). Это делает код плохочитаемым (на глаз "лиспера", а не "сиониста" или "басикиста"). Кроме того, последовательный вызов setq замедляет работу. Это каждый раз загрузка, разбор аргументов и прочее. В обычных программах это некритично, а в такой, да еще с многочисленными вложенными циклами, значительно влияет на скорость.

Сравним

Код:

[Выделить все]

(while
				(> (length spisok-all-vershin) 0)
				(progn
					(setq vershina-N (car spisok-all-vershin))
					(setq spisok-all-vershin (vl-remove vershina-N spisok-all-vershin))
					(setq spisok-vershin (vl-list* vershina-N spisok-vershin))
				)
			)

с вариантом:

Код:

[Выделить все]

(while
  (> (length spisok-all-vershin) 0)
	(setq vershina-N (car spisok-all-vershin)
	        spisok-all-vershin (vl-remove vershina-N spisok-all-vershin)
                spisok-vershin (vl-list* vershina-N spisok-vershin)
       )
)

Избавились от вызова progn и двух вызовов setq. И от связанных с этим "накладных расходов". А таких мест в программе множество.

3. Запросы с помощью get-функций надо защищать от прерывания или неправильного ввода. Если пользователь введет что-то не то, не так или не введет - будут ошибки и всё псу под хвост. Или коту.

[Дима_]

Сообщение от NEDIS Так ... 13 просмтров архива и ниодного отголоска чего и как, у всех то работают команды? И как быстро?

А что ты хочешь, чтоб тебе написали о программе которая не понятно чего делает? Хочешь совет поставь грамотно вопрос. По коду - оптимизация бывает двух типов на уровне кода и алгоритма - вторая ГОРАЗДО важней - а по ней-то как раз и сказать нечего - т.к. - конечная задача не ясна. По коду - там полно "детских болезней" (без обид), но в целом в правильном направлении - например - в том-же куске кода, который приводит ShaggyDoc есть комбинация:

Код:

[Выделить все]

(while (> (length spisok-all-vershin) 0)...

здесь идет явное не понимание сути списка - список это не массив - чтоб посчитать его длинну надо пройтись по всем его элементам (то есть по сути выполнить количество cdr'ов равных длинне списка), а все, что с ним делается - это сравнивается равна ли его длинна нулю (примерно то же самое, что Вы бы проверяли "больше-ли одного шага шагать до Камчатки все время перешагивая все расстояние"). И делается это на каждом шагу.
Эта конструкция "без потерь" меняется на

Код:

[Выделить все]

(while spisok-all-vershin ...

так как nil и '() в лиспе - синонимы.
p.s. дальше рассказывать не буду т.к. тут затрагиваються гораздо более "глубокие вещи" в целом, повторюсь, совсем не плохо.
p.p.s У тебя прослеживаеться "неправильный" для лиспа императивный подход - работать с ПЕРЕМЕННОЙ в ЦИКЛЕ, оба понятия "аттавизм" в лиспе почитай что такое функциональное программирование, аргументы и рекурсия.

[ShaggyDoc]

Эта конструкция "без потерь" меняется на

Совершенно верно. Тоже хотел написать, но отвлекся и не выкинул из своего примера

Жалко, куда то sir Alaspher пропал. Вот уж он любит код оптимизировать!

И по алгоритму. Не вникал. Но матрицы у меня вызывают подозрение. Это "вузовский" подход. Но в практике часто оказывается, что и без них гораздо проще обойтись, особенно если обработку приходится самому писать. Особенно на LISP

Вот мой любимый пример шедевра Лиспа:

(defun ru-list-Douglas-Wilson-transpose (lst) ;| Здесь мы используем функцию транспонирования списка по алгоритму Дугласа Вильсона (Douglas Wilson) http://xarch.tu-graz.ac.at/autocad/lisp/ |; (apply 'mapcar (cons 'list lst)) )

Всего одна строчка, но трансформирует список. Грубо говоря колонки и строки "матрицы" местами меняет.

[NEDIS]

Сообщение от ShaggyDoc Так там всякие матрицы-шматрицы, да еще какого-то бродяги Флойда. Мало кому интересна такая частная, редкая задача. По которой только сам автор знает, чего он хочет.

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

Сообщение от ShaggyDoc 3. Запросы с помощью get-функций надо защищать от прерывания или неправильного ввода. Если пользователь введет что-то не то, не так или не введет - будут ошибки и всё псу под хвост. Или коту.

Приведи пример если не трудно .

Сообщение от Дима_ А что ты хочешь, чтоб тебе написали о программе которая не понятно чего делает? Хочешь совет поставь грамотно вопрос. По коду - оптимизация бывает двух типов на уровне кода и алгоритма - вторая ГОРАЗДО важней - а по ней-то как раз и сказать нечего - т.к. - конечная задача не ясна. По коду - там полно "детских болезней" (без обид), но в целом в правильном направлении - например - в том-же куске кода, который приводит ShaggyDoc есть комбинация:

Я понимаю, что косяков кучу наделал и алгоритм взял не оптимальный (или реализовал не оптимально).
Суть идеи следующая:
Создается набор примитивов, этот набор обрабатывается и создается несколько списков 1- всех вершин и 2 – «разрешения» узлов, где можно «сворачивать», далее все это компонуется в матрицу Флойда (сам его случайно в инете нашел), эта матрица решается и выдает результат из какой точки в какую можно попасть по кротчайшему пути если не возможно то элементу присваивается «NO» если возможно то присваивается длина трассы между этими точками.

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

[Do$]

Даже с представленным чертежом не могу понять, что делают программы NEDIS-input-system-for-tracing и NEDIS-tracing-point-to-point
Как работать с программой ясно, похоже, только автору... Что указывать при запросах программы?
Я пару раз попробовал наугад что-то указывать, вводить единички и двоечки - один раз напрочь повесил автокад, во второй раз программа прервалась ошибкой.
Помогли бы делу подробное руководство по эксплуатации (буквально по буковкам: на запрос такой-то указываем то-то и то-то, вводим в командную строку то-то и т.д.), а лучше пример работы с программой (видео или пошаговые скриншоты). Пока этого нет, разобираться с работой программы нужно долго и нудно, методом проб и ошибок - а на это нет времени.

[NEDIS]

Сообщение от Do$ Даже с представленным чертежом не могу понять, что делают программы NEDIS-input-system-for-tracing и NEDIS-tracing-point-to-point Как работать с программой ясно, похоже, только автору... Что указывать при запросах программы? Я пару раз попробовал наугад что-то указывать, вводить единички и двоечки - один раз напрочь повесил автокад, во второй раз программа прервалась ошибкой. Помогли бы делу подробное руководство по эксплуатации (буквально по буковкам: на запрос такой-то указываем то-то и то-то, вводим в командную строку то-то и т.д.), а лучше пример работы с программой (видео или пошаговые скриншоты). Пока этого нет, разобираться с работой программы нужно долго и нудно, методом проб и ошибок - а на это нет времени.

Вечером сделаю видео .

P.S. NEDIS-input-system-for-tracing - рамка, необходимо выделить этаж после расчета выполняется трассировка командой NEDIS-tracing-point-to-point ввод 1 или 2 взависимости от предлогаемого условия трассировки.
P.S.S. А с анализаторами ошибок я вообще не работал еще, мне бы вычисления ускорить.

[ShaggyDoc]

Приведи пример если не трудно

А что если, в момент запроса точки пользователь нажмет ESC? Нажмет Enter? Напишет нехорошее слово?

Все примеры я привел в книге САПР на базе AutoCAD - как это делается. Для любого ввода делается специальная функция, которая работает абсолютно надежно.

Например, если требуется ввод обязательной точки используется функция

Код:

[Выделить все]

(defun ru-get-point-reguired (message base_point)

                             ;|
Запрос ввода точки с обязательным указанием

(ru-get-point-reguired "Вторая точка" (trans (getpoint "\nПервая точка: ") 1 0))
(ru-get-point-reguired "Вторая точка"  nil)

|;

  (trans (_ru-get-with-default
           message
           nil
           'getpoint
           1
           nil
           (if (ru-is-point base_point)
             ;; base_point всегда в WCS переводим
             ;; в ПСК для getpoint
             (trans base_point 0 1)
             base_point
           ) ;_ end of if
           nil
         ) ;_ end of _ru-get-with-default
         1
         0
  ) ;_ end of trans
) ;_ end of defun

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

Код:

[Выделить все]

(defun ru-get-point-or-exit (message keywords / result)
                            ;|
(ru-get-point-or-exit "Первая точка" "Начало Образец" (list)
(ru-get-point-or-exit "Первая точка" nil)
|;

  (if (ru-is-point
        (setq result (_ru-get-with-default
                       message "Выход" 'getpoint nil keywords nil T) ;_ end of _ru-get-with-default
        ) ;_ end of setq
      ) ;_ end of ru-is-point
    (trans (ru-conv-point-to-3d-point result) 1 0)
    result
  ) ;_ end of if
) ;_ end of defun

И еще несколько десятков подобных. И все они используют низкоуровневую функцию

Код:

[Выделить все]

(defun _ru-get-with-default (message
                             default_str
                             quoted_get_func
                             initget_param
                             keywords
                             base_point
                             esc_enabled
                             /
                             result
                             question
                             lst_params
                             key_str
                             alt_key_str
                             alt_word
                             lst_alt_words
                             lst_words
                            )
                            ;|

Выполняет функцию quoted_get_func с возможностью получения значения
по умолчанию
Параметры:
message - строка запроса
default_str - строка, выводящаяся в <default_str>
quoted_get_func - имя getxxx-функции с апострофом
initget_param - биты для initget или nil
keywords - ключевые слова для initget или nil
base_point - базовая точка или nil в ПСК!!!

Возвращает значение, ключевое слово или nil

|;
 (setq key_str ""
       alt_key_str
       " _"
       lst_alt_words
       '()
 ) ;_ end of setq

 

 (if keywords
  (progn
   (setq lst_words (ru-string-to-list keywords " "))
   (foreach word lst_words
    (setq key_str       (strcat key_str
                                word
                                (if (/= word (last lst_words))
                                 "/"
                                 ""
                                ) ;_ end of if
                        ) ;_ end of strcat
          alt_word      (ru-conv-string-win-translit word)
          lst_alt_words (cons alt_word lst_alt_words)
          alt_key_str   (strcat alt_key_str
                                alt_word
                                (if (/= word (last lst_words))
                                 " "
                                 ""
                                ) ;_ end of if
                                " "
                        ) ;_ end of strcat
    ) ;_ end of setq
   ) ;_ end of foreach
   (setq key_str       (ru-string-format "[%1]" key_str)
         lst_alt_words (reverse lst_alt_words)
   ) ;_ end of setq
  ) ;_ end of progn
 ) ;_ end of if
 (if default_str
  (setq question (ru-string-format
                  "\n%1  %2<%3>:"
                  (list message key_str default_str)
                 ) ;_ end of ru-string-format
  ) ;_ end of setq
  (setq question
        (ru-string-format "\n%1  %2:" (list message key_str))
  ) ;_ end of setq
 ) ;_ end of if
 (if base_point
  (setq lst_params (list base_point question))
  (setq lst_params (list question))
 ) ;_ end of if
 ;;------------- Новый цикл с возможностью esc ------------
 (setq end nil)
 (while
   (not end)
   (ru-error-catch
    (function (lambda ()
        (cond ((and initget_param keywords)
               (initget initget_param (strcat keywords alt_key_str))
              )
              ((not (null initget_param))
               (initget initget_param)
              )
              ((not (null keywords))
               (initget (strcat keywords alt_key_str))
              )
        ) ;_ end of cond

        (setq result (vl-catch-all-apply quoted_get_func lst_params)
              end T)
          result      
                      
              ) ;_ end of lambda
    ) ;_ end of function
    ;;Это выполняется при ошибке
      (function
       (lambda (msg)
        (if esc_enabled
         (setq result nil
               end t
         ) ;_ end of setq
         (progn 
         (princ "\nЗдесь прерывание по ESC недопустимо!")
          (setq ;;result nil
               end NIL
         )
         )
        ) ;_ end of if
        (princ)
       ) ;_ end of lambda
      ) ;_ end of function
 
   ) ;_ end of ru-error-catch
 ;;------------- Новый цикл с возможностью esc ------------

 ) ;_ end of while
 ;; а здесь бы и вернуть "настоящее" ключевое слово. Чтобы не в каждой программе анализировать
 ;; Но обратный транслит не сделать, надо сопоставлять списки
 ;; есть lst_words  
 ;; (vl-position "A" (list "A" "B" "F"))
 (if
  (ru-is-string result)
  (setq result (nth (vl-position result lst_alt_words) lst_words))
 ) ;_ end of if
 (if (ru-is-point result)
  (setq result (ru-conv-point-to-3d-point result))
 ) ;_ end of if
 result
) ;_ end of defun

Она выполняет любую get* в возможностями задавать ключевые слова, значения по умолчанию и прочее нужное.

Но, для начала, при использовании get-функций необходимо приучиться использовать initget.

[zamtmn]

>>Автоматическая трассировка по существующему скелету для Autocad (оптимизируем код общими усилиями)

оптимизировать тут нужно не код, а алгоритм. что NEDIS-input-system-for-tracing делает такого, что результата ее работы невозможно дождаться на исходных данных чуть сложнее чем в примере?

[NEDIS]

Сообщение от zamtmn >> оптимизировать тут нужно не код, а алгоритм. что NEDIS-input-system-for-tracing делает такого, что результата ее работы невозможно дождаться на исходных данных чуть сложнее чем в примере?

Матрицу маршрутов решает, а решает очень медленно. Нужно скорее всего подход к решению марицы поменять, как честно не знаю (алгоритм).

ShaggyDoc

Сообщение от zamtmn А что если, в момент запроса точки пользователь нажмет ESC? Нажмет Enter? Напишет нехорошее слово?

В будующем учту, сейчас все таки больше меня мучает скорость решения матрицы.

[zamtmn]

>>Матрицу маршрутов решает, а решает очень медленно. Нужно скорее всего подход к решению марицы

я с методом флойда не знаком, что значит решает? заранее ищет все возможные маршруты?

[NEDIS]

Сообщение от zamtmn >>я с методом флойда не знаком, что значит решает? заранее ищет все возможные маршруты?

Обсалютно точно - создает матрицу которая содержит информацию из какой точки (любой) в какую (любую) и через какие можно быстро попасть.

[ShaggyDoc]

Сообщение от NEDIS Обсалютно точно - создает матрицу которая содержит информацию из какой точки (любой) в какую (любую) и через какие можно быстро попасть.

Вот в этом и "корень зла". Матрица ведь не сама "знает". Её надо заполнить - по большей части заведомо ненужными данными. А потом их анализировать. И всё это в многочисленных циклах...

А любая "тетка" безо всякой науки сразу отбросит заведомо ненужное и будет перебирать только несколько вариантов.

Менять надо алгоритм. Забыть вообще про матрицу и действовать простыми методами. Вообще про "математические методы" забыть.

PS. Несколько лет назад форумчанин Lexa разработал программу автоматической трассировки кабелей в 3D. Задавались фиксированные точки в пространстве ("хомуты") в виде окружностей, через центр которых должна была оптимально пройти трасса. И не просто точки отбирались, а трасса вычерчивалась, да еще с учетом радиуса гнутья кабеля и "запретных" мест. Всё работало достаточно точно и быстро. Никакой "высшей математики", только "арихметика Магницкого". Так как подобные задачи могут не иметь оптимального решения (просто длина маршрута не всегда главный показатель), во время работы её можно было "направить". Чтоб не искала путь из Иркутска на Камчатку через Бердичев. К сожалению, Lexa теперь Автокадом не занимается...

[zamtmn]

>>Обсалютно точно - создает матрицу которая содержит информацию из какой точки (любой) в какую (любую) и через какие можно быстро попасть.

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

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