Ну даже если данные реально с плавающей точкой, но диапазон их значений известен, то возможно проще их квантовать и считать статистику по квантованным целочисленным значениям. Конечно квантование будет вносить свою ошибку, но она должна быть постоянной и ее величиной можно управлять, меняя шаг квантования. Зато от накопительной ошибки можно полностью избавиться.
А откуда берутся значения с плавающей точкой? Если речь о данных из "реального мира", то обычно они приходят с АЦП, т.е. по факту целочисленны. В этом случае можно все накопление/обновление сумм выполнять в целочисленной арифметике и никаких проблем с точностью не будет.
Книга действительно читается с таким же интересом как художественная, сложно оторваться. Я не физик, но на мой взгляд изложено все понятно и логично, в отличие от всякого научпопа по той же теории инфляции, где при чтении чувствуешь себя дураком.
Хотелось бы узнать, как обстоят дела с данной теорией в научном сообществе в текущий момент? Какая критика присутствует? Какие основные аргументы оппонентов?
Потому что на основе одного графика никаких выводов сделать нельзя. А выводы о наличии эффекта делаются на основе совместного анализа двух графиков, конкретно их разницы: если разница больше нуля - переоценка, меньше нуля - недооценка.
Вообще обычно нужны ближайшие точки двух прямых. Пересечение - это частный случай, когда эти точки совпадают.
Решается достаточно просто. Даны две прямые:
a(t) = a0 + a * t
b(s) = b0 + b * s
Вектор между ближайшими точками прямых должен быть перпендикулярен обеим прямым. Т.е. имеем систему двух линейных уравнений:
dot(a, a(t) - b(s)) = 0
dot(b, a(t) - b(s)) = 0
Если уравнения линейно зависимы - прямые параллельны. Если нет, решаем, находим t и s. Если расстояние между соответствующим им точками равно нулю - прямые пересекаются, если не равно - это кратчайшее расстояние между прямыми.
"Далее более тонкими рассуждениями можно показать, что после встречи, если продвигать два указателя по 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, а из него уже сделать любое форматирование строки очень просто.
Конечно то же самое, результат то в итоге получается одинаковый. Проекция радиу вектора любой точки треугольника на его нормаль дает высоту пирамиды с вершиной в начале координат. Просто на мой взгляд в таком виде это сложнее для понимания и реализации, как я написал выше.
Через SVD это просто делается:
https://www.ltu.se/cms_fs/1.51590!/svd-fitting.pdf
Часть 3: Fitting Planes and Lines by Orthogonal Distance Regression
Ну даже если данные реально с плавающей точкой, но диапазон их значений известен, то возможно проще их квантовать и считать статистику по квантованным целочисленным значениям. Конечно квантование будет вносить свою ошибку, но она должна быть постоянной и ее величиной можно управлять, меняя шаг квантования. Зато от накопительной ошибки можно полностью избавиться.
А откуда берутся значения с плавающей точкой? Если речь о данных из "реального мира", то обычно они приходят с АЦП, т.е. по факту целочисленны. В этом случае можно все накопление/обновление сумм выполнять в целочисленной арифметике и никаких проблем с точностью не будет.
Книга действительно читается с таким же интересом как художественная, сложно оторваться. Я не физик, но на мой взгляд изложено все понятно и логично, в отличие от всякого научпопа по той же теории инфляции, где при чтении чувствуешь себя дураком.
Хотелось бы узнать, как обстоят дела с данной теорией в научном сообществе в текущий момент? Какая критика присутствует? Какие основные аргументы оппонентов?
Потому что на основе одного графика никаких выводов сделать нельзя. А выводы о наличии эффекта делаются на основе совместного анализа двух графиков, конкретно их разницы: если разница больше нуля - переоценка, меньше нуля - недооценка.
Вообще обычно нужны ближайшие точки двух прямых. Пересечение - это частный случай, когда эти точки совпадают.
Решается достаточно просто. Даны две прямые:
a(t) = a0 + a * t
b(s) = b0 + b * s
Вектор между ближайшими точками прямых должен быть перпендикулярен обеим прямым. Т.е. имеем систему двух линейных уравнений:
dot(a, a(t) - b(s)) = 0
dot(b, a(t) - b(s)) = 0
Если уравнения линейно зависимы - прямые параллельны. Если нет, решаем, находим t и s. Если расстояние между соответствующим им точками равно нулю - прямые пересекаются, если не равно - это кратчайшее расстояние между прямыми.
Я так понимаю, там в вычислениях участвуют числа гораздо большего порядка.
"Далее более тонкими рассуждениями можно показать, что после встречи, если продвигать два указателя по 1 узлу за шаг, начав от начала списка и от места встречи соответственно, то эти указатели встретятся в начале цикла."
Насколько я могу судить, это неверно. На мой взгляд правильное решение, это делать по одному шагу из начала списка, и после каждого такого шага делать полный круг из точки встречи.
Там же на картинке все подписано. Серое - это именно "speedup", т.е. величина ускорения при использовании AVX-512 инструкций (конкретно IFMA инструкций, но в подписи не стали уже разжевывать). Поэтому и для серого отдельно числа указаны, чтобы было понятно, что это другие единицы измерения - "разы" вместо наносекунд для синего и красного.
Совершенно неверная интерпретация картинки. Серая полоска - это во сколько раз получается ускорение при использовании AVX-512, т.е. равна отношению длин красной и синей. Т.е. эта архитектура проигрывает как по абсолютным показателям так и по относительными.
Если исправить, то число узлов будет почти в два раза меньше, но выигрыша по времени относительно реализации без path compression все равное не получается — усложняется логика ветвления и видимо это все съедает.
А что насчет префиксного дерева с узлом не из одного символа а из нескольких? Количество случайных доступов к памяти должно уменьшиться пропорционально, процент cache miss'ов наверное вырастет, но думаю не на столько, насколько уменьшиться количество самих обращений, т.ч. в общем должен быть выигрыш.
Ну, если нумеровать картинки по порядку, то неужели вы сами не видите, что картинка №5 является увеличенной областью(верхняя левая часть) картинки №4? Например большая горизонтальная структура на этих картинках имеет разный размер. Такое могло произойти либо при использовании части картинки №4 (что я и предположил), либо при увеличении масштаба на картинке (с увеличением размера в пикселях) и последующем обрезании до старого размера (возможный вариант, раз вы утверждаете, что размер в пикселях картинок одинаковый).
В принципе, демонстрация части картинки, это не проблема, если это делается в иллюстративных целях, но судя по тому, что потому вы эту же масштабированную картинку накладываете на оригинальное изображение (изображение №8), где явно видно несовпадение контуров, это масштабирование реально выполняется в ходе исполнения вашей реализации, что скорее всего приводит к тому, что по факту анализируется только часть картинки.
А почему у вас начиная с определенного шага размер картинки изменяется, т.е. по факту анализируется только часть картинки? Ну и из-за разных размеров, при наложение контуров на кадр, контуры не соответствуют объектам в кадре.
Из описания сначала не понял суть "второго варианта". Ну так да, он будет правильно обрабатывать. Наверное это самый простой и эффективный способ корректной реализации данного алгоритма.
Ну вообще то такой алгоритм не будет корректно различать такой случай: есть три последовательные точки многоугольника (для просто можно рассматривать треугольник) A, B и C. Луч проходит через точку B. Есть два случая: точки A и С лежать по разные стороны луча(линии проходящей через луч) или точки A и С лежат по одну сторону луча. В первом случае луч пересекает границу многоугольника, во втором, нет.