"Далее более тонкими рассуждениями можно показать, что после встречи, если продвигать два указателя по 1 узлу за шаг, начав от начала списка и от места встречи соответственно, то эти указатели встретятся в начале цикла."
Насколько я могу судить, это неверно. На мой взгляд правильное решение, это делать по одному шагу из начала списка, и после каждого такого шага делать полный круг из точки встречи.
Там же на картинке все подписано. Серое - это именно "speedup", т.е. величина ускорения при использовании AVX-512 инструкций (конкретно IFMA инструкций, но в подписи не стали уже разжевывать). Поэтому и для серого отдельно числа указаны, чтобы было понятно, что это другие единицы измерения - "разы" вместо наносекунд для синего и красного.
Если на стандартных инструкциях x86-64 Centaur проигрывает всухую, то AVX-512 дают ему «впрыск нитро».
Совершенно неверная интерпретация картинки. Серая полоска - это во сколько раз получается ускорение при использовании AVX-512, т.е. равна отношению длин красной и синей. Т.е. эта архитектура проигрывает как по абсолютным показателям так и по относительными.
Реализация у вас неверная. По факту никакого path compression в ней не выполняется. Даже по выводу можно видеть, что число узлов получается такое же, как и без path compression, а должно быть меньше.
Если исправить, то число узлов будет почти в два раза меньше, но выигрыша по времени относительно реализации без path compression все равное не получается — усложняется логика ветвления и видимо это все съедает.
А что насчет префиксного дерева с узлом не из одного символа а из нескольких? Количество случайных доступов к памяти должно уменьшиться пропорционально, процент cache miss'ов наверное вырастет, но думаю не на столько, насколько уменьшиться количество самих обращений, т.ч. в общем должен быть выигрыш.
Ну, если нумеровать картинки по порядку, то неужели вы сами не видите, что картинка №5 является увеличенной областью(верхняя левая часть) картинки №4? Например большая горизонтальная структура на этих картинках имеет разный размер. Такое могло произойти либо при использовании части картинки №4 (что я и предположил), либо при увеличении масштаба на картинке (с увеличением размера в пикселях) и последующем обрезании до старого размера (возможный вариант, раз вы утверждаете, что размер в пикселях картинок одинаковый).
В принципе, демонстрация части картинки, это не проблема, если это делается в иллюстративных целях, но судя по тому, что потому вы эту же масштабированную картинку накладываете на оригинальное изображение (изображение №8), где явно видно несовпадение контуров, это масштабирование реально выполняется в ходе исполнения вашей реализации, что скорее всего приводит к тому, что по факту анализируется только часть картинки.
А почему у вас начиная с определенного шага размер картинки изменяется, т.е. по факту анализируется только часть картинки? Ну и из-за разных размеров, при наложение контуров на кадр, контуры не соответствуют объектам в кадре.
Из описания сначала не понял суть "второго варианта". Ну так да, он будет правильно обрабатывать. Наверное это самый простой и эффективный способ корректной реализации данного алгоритма.
Ну вообще то такой алгоритм не будет корректно различать такой случай: есть три последовательные точки многоугольника (для просто можно рассматривать треугольник) A, B и C. Луч проходит через точку B. Есть два случая: точки A и С лежать по разные стороны луча(линии проходящей через луч) или точки A и С лежат по одну сторону луча. В первом случае луч пересекает границу многоугольника, во втором, нет.
Тоже не так давно допиливал ryu для своих целей. О библиотеке у меня сложилось впечатление: отличная и эффективная внутренняя реализация и ужасный интерфейс (по крайней мере для моих целей). В результате переделал следующим образом ryu -> двоично десятичное представление -> строка. Преобразование в двоично десятичное представление очень эффективно выполняется ryu, а из него уже сделать любое форматирование строки очень просто.
Конечно то же самое, результат то в итоге получается одинаковый. Проекция радиу вектора любой точки треугольника на его нормаль дает высоту пирамиды с вершиной в начале координат. Просто на мой взгляд в таком виде это сложнее для понимания и реализации, как я написал выше.
Объем замкнутой триангулированной оболочки проще посчитать как сумму ориентированных объемов тетраэдров (треугольных призм), каждый из которых образован одним из треугольников оболочки (с учетом его ориентации) и произвольной точкой (например началом координат). Т.е. аналогично двумерному случаю, где площадь замкнутого невыпуклого многоугольника можно посчитать как сумму ориентированных площадей треугольников, образованных каждым ребром и произвольной точкой.
На мой взгляд это проще для понимания и реализации, по крайней мере для вычисления нужны только операция умножения и сложения/вычитания и не нужно вычисление квадратного корня.
Ну выглядит так, что -> там перегруженный оператор, которые возвращает nullptr, если has_value() возвращает false. Т.е. key_data_ это что то типа какого то умного указателя, типа shared_ptr.
Так это я сам на свой комментарий и ответил :)
Тут ситуация аналогичная такой: допустим есть указатель ptr на какой то класс, у которо есть метод foo(), возвращающий bool. Если написать
if ((ptr != nulptr) && ptr->foo())
то все будет нормально, даже если ptr будет nullptr, а если написать
if ((ptr != nullptr) & ptr->foo())
то ptr->foo() вызовется в любом случае и все упадет.
Не вижу, как эта ошибка могла на что то влиять. Поведение в обоих случаях должно быть одинаковым, если обе функции возвращают bool (на что указывает их название). Скорее просто исправили эту описку в процессе поиска реального бага.
Интерполяцию сплайнами тоже делал. Только использовал эрмитов сплайн, потому что он ведет себя более предсказуемо. Обычный кубический сплайн часто начинает осцилировать, особенно если в интерполируемых данных присутствует шум. Ну и при изменении одной точки эрмитов сплайн меняется только локально. Но зато вторая производная у него не непрерывна.
Поэтому делал так: интерполировал ломаную сплайном, а потом уже делал тесселяцию сплайна ломаной, но уже с более мелким шагом, и для нее уже использовал метод с поворотом координатной системы.
Я так понимаю, там в вычислениях участвуют числа гораздо большего порядка.
"Далее более тонкими рассуждениями можно показать, что после встречи, если продвигать два указателя по 1 узлу за шаг, начав от начала списка и от места встречи соответственно, то эти указатели встретятся в начале цикла."
Насколько я могу судить, это неверно. На мой взгляд правильное решение, это делать по одному шагу из начала списка, и после каждого такого шага делать полный круг из точки встречи.
Там же на картинке все подписано. Серое - это именно "speedup", т.е. величина ускорения при использовании AVX-512 инструкций (конкретно IFMA инструкций, но в подписи не стали уже разжевывать). Поэтому и для серого отдельно числа указаны, чтобы было понятно, что это другие единицы измерения - "разы" вместо наносекунд для синего и красного.
Совершенно неверная интерпретация картинки. Серая полоска - это во сколько раз получается ускорение при использовании AVX-512, т.е. равна отношению длин красной и синей. Т.е. эта архитектура проигрывает как по абсолютным показателям так и по относительными.
Если исправить, то число узлов будет почти в два раза меньше, но выигрыша по времени относительно реализации без path compression все равное не получается — усложняется логика ветвления и видимо это все съедает.
А что насчет префиксного дерева с узлом не из одного символа а из нескольких? Количество случайных доступов к памяти должно уменьшиться пропорционально, процент cache miss'ов наверное вырастет, но думаю не на столько, насколько уменьшиться количество самих обращений, т.ч. в общем должен быть выигрыш.
Ну, если нумеровать картинки по порядку, то неужели вы сами не видите, что картинка №5 является увеличенной областью(верхняя левая часть) картинки №4? Например большая горизонтальная структура на этих картинках имеет разный размер. Такое могло произойти либо при использовании части картинки №4 (что я и предположил), либо при увеличении масштаба на картинке (с увеличением размера в пикселях) и последующем обрезании до старого размера (возможный вариант, раз вы утверждаете, что размер в пикселях картинок одинаковый).
В принципе, демонстрация части картинки, это не проблема, если это делается в иллюстративных целях, но судя по тому, что потому вы эту же масштабированную картинку накладываете на оригинальное изображение (изображение №8), где явно видно несовпадение контуров, это масштабирование реально выполняется в ходе исполнения вашей реализации, что скорее всего приводит к тому, что по факту анализируется только часть картинки.
А почему у вас начиная с определенного шага размер картинки изменяется, т.е. по факту анализируется только часть картинки? Ну и из-за разных размеров, при наложение контуров на кадр, контуры не соответствуют объектам в кадре.
Из описания сначала не понял суть "второго варианта". Ну так да, он будет правильно обрабатывать. Наверное это самый простой и эффективный способ корректной реализации данного алгоритма.
Ну вообще то такой алгоритм не будет корректно различать такой случай: есть три последовательные точки многоугольника (для просто можно рассматривать треугольник) A, B и C. Луч проходит через точку B. Есть два случая: точки A и С лежать по разные стороны луча(линии проходящей через луч) или точки A и С лежат по одну сторону луча. В первом случае луч пересекает границу многоугольника, во втором, нет.
На мой взгляд это проще для понимания и реализации, по крайней мере для вычисления нужны только операция умножения и сложения/вычитания и не нужно вычисление квадратного корня.
Тут ситуация аналогичная такой: допустим есть указатель ptr на какой то класс, у которо есть метод foo(), возвращающий bool. Если написать
то все будет нормально, даже если ptr будет nullptr, а если написать
то ptr->foo() вызовется в любом случае и все упадет.
Поэтому делал так: интерполировал ломаную сплайном, а потом уже делал тесселяцию сплайна ломаной, но уже с более мелким шагом, и для нее уже использовал метод с поворотом координатной системы.