10^6 это уже хорошо. Тогда остается вопрос, достаточно ли закодировать какой-нибудь из эквивалентных кодов и какова максимальная глубина дерева (она зависит от размера исходной статистики). Если одного кода хватит, а глубина, скажем, не больше 31, то достаточно 21 бита на символ (точнее, 2^m+N*5 на весь букварь): маска присутстующих символов и длина кода каждого из них.
Есть ли какие-нибудь ограничения на число символов, по которому строилась статистика? Потому что в общем случае, когда максимальная длина кода одного из символов может равняться N-1, Ваш результат улучшить трудно, но в реальности длина ограничена более разумным числом (логарифмом объема входных данных). И какое ожидается соотношение между N и m, т.е. какая доля m-битных чисел присутствует в алфавите?
Вопрос по ситуации с «миллионом точек». Есть ли там ограничения на то, в какой (по размерам) области могут оказаться видимые кубики? Можно ли для каждого кубика перечислить те, которые могут быть видимы одновременно с ним?
Вроде сказал. А потом прозвучали «датчики расстояния». Если это мишени, промеренные лазерным теодолитом, то это одна задача. Если сигналы, полученные роботом от маяков — другая. Есть и третья: известны и направления и расстояния, но неизвестно, как они связаны друг с другом :)
То есть, направления неизвестны? Тогда, конечно, только метод «колец». Другой вариант: берем два сигнала (с наименьшими расстояниями), перебираем все пары точек, расстояние между которыми допустимо (лежит между суммой и разностью измеренных), строим два возможных положения наблюдателя, и для каждого проверяем — есть ли точки на трех остальных расстояниях. Проблема в том, что если наблюдатель оказался между двумя датчиками, его положение определяется слишком неточно.
Любопытно. Решение совершенно не учитывает направлений — только расстояния. Обычно направления известны точнее. Если только наблюдатель — не летучая мышь :)
Не зависит. 2d и 3d тут различаются мало. А «расстояния в полярных координатах»(не знаю, правда, что это такое) не инварианты относительно перемещения в пространстве, поэтому не помогут. Чтобы спастись от близких координат, можно искать треугольники — им совпасть сложнее, и при 20 опорных точках их немного (всего 1140). Мне хуже, у меня точек 150 :(
Зависит от цели и ресурсов. Научно правильное решение легко может оказаться стрельбой из пушки по воробьям. И кроме ожидаемого воробья выдать пользователю еще и стаю убитых комаров, которые тому совсем не нужны. Если программа будет 15 секунд гарантированно строить все компоненты графика, а потом еще 5 секунд выделять и выбраывать компоненты размером меньше порогового, то это будет несколько хуже, чем если она сза 0.1 секунду построит основную компоненту каким-нибудь эвристическим методом.
После небольшой правки с первым уравнением программа справилась (перебрав 8.6 миллионов квадратов, размером до 2^(-21)). Но вот построить график 9*x*x-6*x+9*y*y-1.25=0 ей не под силу: окружность касается прямой y=1/2 в точке, не являющейся двоично-рациональной. Доказать, что в смежном квадратике (где y>=1/2)есть точка кривой, интервальный метод не сможет :(
Конечно, если результат «много красного» допустим и кажется более ценным, чем «пропущены части графика, которые меньше ячейки сетки», то алгоритм имеет смысл применять — он дает хорошую оптимизацию на огромных (по числу ячеек мелкой сетки) площадях. Но надо хорошо подготовить функцию f к вычислению в интервальной арифметике, там разный порядок вычислений может дать очень разные по качеству результаты.
Возможно, я чего-то в алгоритме не понял. Я попробовал его применить, чтобы построить график уравнения
2*x*x-3*x*y-2*y*y-x+2*y=0 на квадрате [0,1]x[0,1] с разрешением 1024x1024. При этом глубину разбиения ограничил 30 шагами (т.е. интервальному алгоритму разрешалось спускаться только до квадратов со стороной 2^(-30) ). Программа тут же заявила, что 30 шагов ей мало (остаются красные пиксели), а всего (даже для неполного результата) потребовалось проанализировать 258 миллионов квадратиков. Правда, нарисовать итоговую картинку я еще не пытался.
А у Вас этот алгоритм заработал?
Так написали же — «такую f(x,y), которая бы по методу наименьших квадратов проходила ближе всего к заранее заданному массиву точек». Точки я возьму из «заданного массива». При такой формулировке очевидно, что надо искать компоненту, которая проходит где-то между точками. Конечно, если пространство функций слишком замысловато, то и самая близкая кривая может оказаться «пеной» из многих компонент, но это будет означать, что пространство выбрано не совсем удачно.
А статью прочитаю. Как можно справиться с цилиндрической декомпозицией без решения систем, это уже интересно :)
Тогда всесовсем просто. Для заданных точек найдется две, для которых f будет разных знаков, где-то между ними — отрезок, на котором f меняет знак (ищется за логарифм, делением пополам). А дальше — обход компоненты, как я написал. Общее время работы — линейное от длины кривой.
А насчет того, что перебирать все (x,y) долго, возникает вопрос — а какие требования? F(x,y) долго вычислять? Или разрешение экрана очень высокое? Или нужно какое-нибудь особое быстродействие (перерисовка в реальном времени)? Потому что в остальных случаях вычислить 10 миллионов значений функций не должно быть проблемой.
Значит, в кладовке нужен еще и какой-нибудь примус. И керосиновая лампа на всякий случай. Что же, возможно. Проблема только в том, что через 20 лет хранения они могут и не заработать.
