Здравствуйте, Юрий Лазарев, Вы писали:
ЮЛ>>>Вообще то я не люблю "готовые" решения;
B>>Почему же тогда использовали "готовую" сортировку и map?
ЮЛ>Потому что это уже "вполне очевидно" (формально: поддерживается стандартом).
Допустим. И всё же, чем вам не угодили готовые решения? Какие аргументы?
ЮЛ>>>если такие были в бусте, это вполне мог бы знать Манагер, по его рассказам уже собаку съевший на этом. Молчание доказывало, что там нечего искать. Сейчас очевидно, что его знакомство с бустом ненамного опережало мое.
B>>В общем же случае задача сбора всей информации и поиска оптимального плана действий, в том числе поиск готовых решений — лежит на разработчике.
ЮЛ>Считайте, я и выбрал свой оптимальный план действий. Если кому то не нравится, — надо аргументировать, "мне не нравится" как аргумент не годится.
Из месячной работы был ли потрачен хотя бы час на поиск готовых библиотек или описаний алгоритмов?
B>>Что же в ней плохого? На мой взгляд очень даже хорошая документация.
ЮЛ>Попытаюсь еще раз, может быть мне больше повезет. Но вообще документация явно готовилась доксигеном, это удобное чтение для роботов, но не для людей.
Doxygen там не было. В документации сгенерированного содержания минимум.
Покажите мне тот "доксиген" который сгенерирует подобное содержание и робота который его поймёт:
http://www.boost.org/doc/libs/1_57_0/libs/graph/doc/planar_graphs.html
http://www.boost.org/doc/libs/1_57_0/libs/graph/doc/planar_face_traversal.html
B>>Boost.Graph вообще собирать не требуется, это header-only библиотека:
B>>DON'T! The Boost Graph Library is a header-only library and does not need to be built to be used. The only exceptions are the GraphViz input parser and the GraphML parser.
B>>Да и кто вас заставляет использовать msvc-7.0? Она скорей всего уже не поддерживается в новых версиях Boost.
ЮЛ>Да-да, но она преподносится как работающая на любых платформах, и для любых компиляторов. Смотрим еще раз (это цитата из самой последней версии boost): "If you're using an earlier version of Visual C++, or a compiler from another vendor,"...
ЮЛ>т.е. при желании ранние версии msvc можно трактовать как a compiler from another vendor. Как я понял, в этом случае должен собраться какой то их собственный Build, дополняющий возможности компиляторов. Но он вообще не собирается!
Boost это набор библиотек.
Некоторые из них нужно предварительно компилировать, большинство же нет. Некоторые работают на старых компиляторах (плохо поддерживающих стадарт C++) и являются кросс-платформенными, другие же работают только на конкретных платформах и компиляторах.
Boost.Graph — это header-only библиотека, то есть не требует предварительной сборки. В Boost появилась довольно давно, и скорей всего поддерживает даже очень старые компиляторы. Если же вдруг в новой версии сломали поддержку какого-то древнего компилятора, то просто достаточно взять Boost старой версии.
ЮЛ>Поддерживается у них официально msvc-7.1 А кто заставляет использовать msvc-7.0 — жизнь! Или вы полагаете, что не имея работы, я могу позволить себе ставить самые последние навороченные версии,
Непонятно о чём речь. У MSVC есть бесплатные Express версии, есть абсолютно бесплатные gcc и clang.
Да даже если поставить себе компилятор и Boost это прям такая проблема — то есть ведь онлайн-компиляторы. Вот пример planar_face_traversal из Boost.Graph запущенный в такой онлайн-среде:
http://coliru.stacked-crooked.com/a/63829dee31ffbd98
Играйтесь на здоровье.
ЮЛ>которые так завораживают местных хомячков?
Кого вы называете хомячками? Инженеров предпочитающих работать инструментами, которые лучше соответствуют международным стандартам?
ЮЛ>>>Формула Эйлера вообще то верна не только для планарных графов, это грани определяются в планарном графе, а в общем случае есть просто контуры — замкнутые циклы.
B>>Допустим. Вот комментарий из вашего кода:
B>>B>>// where CONTOURS = (EDGES + COMPONENTS — VERTICES) by Euler formula
B>>Вот граф:
B>>Image: 100px-Complete_graph_K5.svg.png
B>>Получается CONTOURS = 6, так? И где эти 6 контуров?
ЮЛ>Обозначая последовательно узлы 1,2,3,4,5, эти контуры будут, например 123, 234, 345, 451, 512 и 12345.
Не, не пойдёт, это уже натягивание совы на глобус.
Во-первых вы пытаетесь посчитать внешнюю грань, хотя в своей интрепретации формулы Эйлера её отбросили. Вот полная формула Эйлера, учитывающая внешнюю грань:
faces = edges + components — vertices + 1
в вашем же варианте нет "+ 1".
Во-вторых не учитываете 134 и ещё четыре подобных цикла.
ЮЛ>Если вам такое объяснение кажется верхом абстракции и удобства, то как я должен в этих понятиях закодировать случай двух (или более) ребер, идущих из одной и той же точки в другую, тоже общую им? Разве они не совпадут (т.е. не сделаются "параллельными"?)
В планарном графе нет параллельных рёбер. Если в оригинальном чертеже есть совпадающие отрезки, и например вам нужно оба отмечать при обходе соответвующего контура, то просто сделайте соответсвие: одно ребро графа (то есть абстрактного представления) -> несколько отрезков в оригинальной моделе. Подобно тому, как в вашем же коде одна вершина графа соответсвует нескольким оригинальным точкам.
ЮЛ>>>Почему то библиотека не обрабатывает параллельные ребра — у меня это типичный случай, надо или игнорировать их или обрабатывать как все прочее. Exception тут не лучшее решение.
B>>Где конкретно?
ЮЛ>Где то было, а вы не видели? Странно, такая хорошая документация...
Я спросил где конкретно, потому что там это есть в нескольких местах.
B>>Разбить можно по-разному, часто есть три основных варианта:
B>>1. Без возможностей универсального применения в других местах, просто вынос кода в отдельную функцию. Упрощает разработку, позволяет легко делать юнит-тесты, упрощает последующее чтение и поддержку. Реализуется элементарно, я бы сказал даже механически — есть даже утилиты которые делают это сами (выедляется фрагмент кода, и нажимается одна кнопка).
ЮЛ>Разве у меня код не вынесен в "отдельную функцию"?
В функцию длинной более тысячи строк и цикломатической сложностью за 300 (при рекомендованных значениях 10-15). При том что в этой функции элементарно очерчиваются обособленные алгоритмы.
B>>2. К 1. добавить минимальную степень общности. Буквально щепотка полиморфизма и/или небольшая реогранизация открывают множество возможностей повторного использования.
ЮЛ>И тут нет возражений.
B>>3. Большая степень общности (как в Boost.Graph), плюс возможно оптимизация специальных случаев.
ЮЛ>Да, но время? Время?
На 3. действительно ушло бы очень много времени, но этого никто и не требовал. У вас же нет даже 1.
B>>Разбиение алгоритма на отдельные/обособленные части — не означает создание аналога Boost.Graph, а подразумевает хотя бы выполнения пункта 1. Опять таки, Boost.Graph был приведён в качестве доказательства того, что такое разбиение возможно, а отнюдь не как единственный возможный вариант.
ЮЛ>Для меня применение "готовых решений" не очень еще и по опыту применения и разработок ActiveX — вещь сильно завязана на автора, пользователь ограничен в возможностях расширения (автор сам решает, что можно, что нельзя).
Опять двадцать пять. Прийдётся даже скопировать: Boost.Graph был приведён в качестве доказательства того, что такое разбиение возможно.
ЮЛ>Это подобно собиранию кода из Лего — какую то игрушку-самолет, даже очень на вид неплохую вы и соберете, но настоящий самолет заведомо из набора Лего не получится. Хотя, для наших хомячков, предпочитающих писать код, не особо размышляя над его алгоритмом, Лего — самый лучший подход.
Настоящий самолёт собирают из готовых деталей, агрегатов. Либо делают новые детали, но уже на готовых станках. Либо создают новые станки, используя уже готовые инструменты.
Ну не выходят авиаконструкторы в поле, для создания каменных молтков голыми руками.
B>>Вот, например, как вы тестировали правильность работы той части, которая ищет компоненты связности? Каждый раз вручную запускали программу, давали разные данные, делали дополнительный debug вывод, вручную проверяли результат?
ЮЛ>Я проверял именно те его части, которые вызывали сомнения. Для того и подбирались данные, а тестирование случайных данных я не делаю. Для того есть лучшее решение — тесты у заказчика, которых набралось уже за тысячи.
То есть тесты вы делали только когда уже отдали работу заказчику, на его тестовых данных? А до этого вообще код не запускали?
B>>Да, я говорю про locCurvesPool (стили?) — сложность квадратична от их числа. Обходится действительно элементарно, причём сходу, а не когда выстрелит.
ЮЛ>Ну да, можно применить map или set по стилям, но зачем городить огород и усложнять код ненужными обобщениями?
Да нет огорода, а получается проще чем с ручным линейным поиском:
map<Style, vector<Curve>> locCurvesPool;
// ...
locCurvesPool[currentStyle].push_back(currentCurve);
