Balancer: Все сообщения за 13 Марта 2005 года

Zeus> Рома! Как не стыдно! Это же школьная задачка! Решается очень просто: последовательно суммируешь все углы [...] сумма углов будет 2пи, иначе 0. [»]

И это чёрный логик советует??? Да ужжж Только тригонометрии мне не хватало в линейных задачах

Да ещё eps вводить - вообще кошмар...

...

Кстати, как у этого метода с невыпуклыми областями?

•  1
•  инфо
•  инструменты
• Ответить на сообщение

GOGI> Он пользователям ниже координатора не показывается [»]

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

•  2
•  инфо
•  инструменты
• Ответить на сообщение

Татарин> Впрочем, с алгоритмом Балансера там тоже будет нехорошо... Да и в условии стоит "многоугольник". [»]

Мой алгоритм для окружностей тоже будет работать. Только такой объект нужно добавить

•  инфо
•  инструменты
• Ответить на сообщение

GOGI> У меня же написано, что я "Старожил" - где мой Остойник?!!! [»]

Группа: Пользователи

•  инфо
•  инструменты
• Ответить на сообщение

Татарин> Ну, что значит "море"? Сколько это численно?

CPU: Pentium III 600MHz EB

Время выполнения команд на GCC:
Целочисленка:
v=i-j; 12.48
v=i*j; 13.28

Плавучка:
fa=i; 12.48
fa=fb+fc; 14.96
fa=fb*fc; 11.68
fa=acos(i); 574.00

Ещё вопросы о порядках величин есть?

Татарин> Гм... Мне вот кажется, что про два порядка - это ты погорячился... Возьми эти слова обратно... а?

Считай сам

Татарин> Откуда более шерокий поток данных?

Это для варианта с хранением в плавучке. В противном случае - затраты на преобразования в обе стороны.

Татарин> Почему?

Потому что пишут решения очевидные, а не оптимальные

>Просто мне кажется, что плавающая точка тут не главный тормоз. [»]

Ну вот смотри ссылку выше

•  инфо
•  инструменты
• Ответить на сообщение

Татарин> Чуть попозже. В чем пишем? Ява? [»]

Я уже перевёл. Реализовал подсчёт углов через atan2

Только пока всё ещё не работает. Постоянная путаница со знаками углов. На отладку Зевсовского алгоритма уже ушло в несколько раз больше времени, чем на всё написание моей программы Впрочем, как я уже писал - у меня она сразу заработала.

Так что - тоже показатель

(пошёл дальше разбираться, почему со знаками такая катавасия )

•  инфо
•  инструменты
• Ответить на сообщение

-exec-> 1.луч из точки пересекает вершину многоугольника
-exec-> 2.луч из точки лежит на стороне многоугольника
-exec-> которые потребуют тригонометрической обработки.
-exec-> [»]

Эти случаи у меня легко отлавливаются. А дальше - в моей задаче пофиг, так что я игнорирую. В некоторых случаях такая точка принадлежит множеству, в некоторых - нет. Как бы там ни было, в практической задаче это не важно Но при желании - такие проверки сделать легко. И это будут именно проверки, а не дополнительные вычисления

•  инфо
•  инструменты
• Ответить на сообщение

Balancer>Целочисленный вариант проверяет у меня 10млн. точек на попадение в треугольник, занимающий 50% тестовой области за 6.8сек. [»]

Вот такой вариант (правда, сумма там выходит Pi, а не 2*Pi, но не принципиально - работает ):

1.         public boolean isInside(int x, int y)
2.         {
3.                 double xx[] = new double[_points.size()+1];
4.                 double yy[] = new double[_points.size()+1];
5.  
6.                 for(int i=0; i<_points.size(); i++)
7.                 {
8.                         xx[i] = _points.get(i).x - x;
9.                         yy[i] = y - _points.get(i).y;
10.                 }
11.  
12.                 xx[_points.size()] = xx[0];
13.                 yy[_points.size()] = yy[0];
14.  
15.                 double r = 0;
16.  
17.                 for(int i=0; i<_points.size(); i++)
18.                 {
19.                         double rr = Math.atan2(yy[i],xx[i]) - Math.atan2(yy[i+1],xx[i+1]);
20.                         if(Math.abs(rr) > Math.PI)
21.                                 rr -= Math.PI*Math.signum(rr);
22.                         r+=rr;
23.                 }
24.                 return Math.abs(r) > 0.00001;
25.         }

работает в тех же условиях 28 секунд.

Не порядок, конечно, в конечной программе, но учитывая, что обе задачи не максимально оптимизированы, всё равно, четырёхкратный проигрышь по скорости - это сильно

При серьёзной оптимизации разрыв будет расти и, ИМХО, в итоге легко превысит десятикратную разницу.

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

•  инфо
•  инструменты
• Ответить на сообщение

Татарин> Роман, так нечестно. "Невооруженным глазом" (С) видно, что один atan там лишний. Это - уже раза в полтора увеличит скорость.

Зато затраты на память. А выигрышь:

1.         public boolean isInside(int x, int y)
2.         {
3.                 double xx[] = new double[_points.size()+1];
4.                 double yy[] = new double[_points.size()+1];
5.                 double atan[] = new double[_points.size()+1];
6.  
7.                 for(int i=0; i<_points.size(); i++)
8.                 {
9.                         xx[i] = _points.get(i).x - x;
10.                         yy[i] = y - _points.get(i).y;
11.                         atan[i] = Math.atan2(yy[i],xx[i]);
12.                 }
13.  
14.                 xx[_points.size()] = xx[0];
15.                 yy[_points.size()] = yy[0];
16.                 atan[_points.size()] = atan[0];
17.  
18.                 double r = 0;
19.  
20.                 for(int i=0; i<_points.size(); i++)
21.                 {
22.                         double rr = atan[i] - atan[i+1];
23.                         if(Math.abs(rr) > Math.PI)
24.                                 rr -= Math.PI*Math.signum(rr);
25.  
26.                         r+=rr;
27.                 }
28.                
29.                 return Math.abs(r) > 0.00001;
30.         }

Впрочем, ты прав. Выигрышь почти полуторакратный. 19 секунд.

Татарин> Короче, все ж будем считать "два порядка" - гиперболой.
…

Дальше »»»

•  3
•  инфо
•  инструменты
• Ответить на сообщение

hcube> То есть если у тебя тупой угол - то в контуре образуется дырка? [»]

Кхм. Какие дырки? Какой контур? Там тупой пересчёт суммы углов. Впрочем, я же говорил, что алгоритм с тригонометрическими функциями всегда сложнее, чем без них и способен постоянно порождать новые ошибки из-за неучитывания углов. Периодичность функций отрицательно сказывается на надёжности

•  инфо
•  инструменты
• Ответить на сообщение

hcube> То есть если у тебя тупой угол - то в контуре образуется дырка? [»]

Перечитал к чему это относилось Кажется, мы друг друга недопоняли. Про какие углы ты в моём варианте говоришь? Что ты понимаешь под "дыркой"?

•  инфо
•  инструменты
• Ответить на сообщение

Zeus> Интересно, а поисковики к какой группе относятся? [»]

К "Гостям". С некоторыми особенностями. Например, старые топики только на сутки поднимают из архива.

•  инфо
•  инструменты
• Ответить на сообщение

Dem_anywhere> Ну и ССЗБ. Сколько матрица в обычной оптической мыше? [»]

Э... 1. какая там матрица? Там же принцип иной.
2. А что, мышам уже нужно образы распознавать?

•  инфо
•  инструменты
• Ответить на сообщение

Татарин> А ты уверен, что там нужен массив, а не пара временных переменых в стиле:

А как же в конце вернуться к первому значению? Завести ещё переменную, выставлять её вначале, а в цикл вводить лишнюю проверку? Так тормознее будет! А памяти на реальных объектах (несколько точек 3..6) сожрёт почти столько же.

Татарин> Понятно, что угол между нулевой и последней вершиной тоже надо учесть, но не суть... Массивы-то зачем?

Давай, напиши более оптимальный вариант, измерю скорость

Татарин> Откуда и получается, что теоретическую разницу в 50 раз (по тактам) в реале реализовать никак нельзя...

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

Татарин> Тут получился... да. Я и не упирался рогом, что тригонометрия именно тут рулит. Но если бы целочисленных операций было б раз в шесть-семь поболее, то могло бы выйти и наоборот, согласись?

Если б да кабы... Да, на сложениях вычитаниях в сопре плавучка будет работать также, как целочисленка. Но тригонометрия - всегда тормоза. Независимо от. Собственно, я только на эту тему спорил. Ну и всегда будут тормоза при загрузке/выгрузки данных, хотя уже и заметно меньшие.

Рекурсивный Фибоначи (никакой тригонометрии, одни сложения и сравнения), 41-е число. Целочисленка - 2сек. double - 5.5сек.

Татарин> Ну, это уже натуральная издевка.

Нет. У меня задача практическая - реалтаймовый игровой сервер

Татарин> Я несколько раз видел, как люди оптимизируют и вылизывают тонкости в алгоритме, который сам по себе неоптимален. Короче, слету отказываться от ПТ нельзя, надо смотреть.

С этим не спорю. Ну так этот принцип ещё во времена ПМК во главу угла ставился. "Не экономьте одну команду. Экономьте сразу 50!".

Татарин> Я отдаю должное твоей интуиции в данном случае и все такое ;), но бывает и иначе.

Когда иначе, я обычно в спор не лезу Просто с плавучкой я начал работать ещё в досопроцессорные времена, много работал во времена i386 и долго следил, как оно менялось, вплоть до Pentium (1-й который). С тех пор, каюсь, всякие MMX/SSE/SSE2/3DNow не изучал, но судя по слухам, кардинально ситуация не менялась. Да и занимаются этим делом уже компиляторы. А как с ними - см. выше цифры

Татарин> Вопрос сугубо личный... Мне с тригонометрией написалось бы быстрее. Наверное. [»]

Ну, вон, Зевсу - тоже. М.б. тимное?

•  инфо
•  инструменты
• Ответить на сообщение

Zeus> Это случилось еще на 1-м Пентиуме, если не на 486DX. Не с тригонометрическими функциями, конечно, но деление с плавающей точкой выполнялось быстрее, чем целочисленное.

По растактовке - да. С учётом времени загрузки - нет.

Вообще, см. реальные цифры выше. Если на банальном сложении с проверками в случае Фибоначи плавучка тормознее почти втрое, то что говорить о более сложных задачах?

Zeus> Это сморя в чем Вот что точно - то, что твой алгоритм гораздо менее нагляден.

Да, наверное, это тимное. Мне гораздо проще оперировать с положениями объектов, чем с углами

Что радует - то, что и поцессору с такими вещами работать проще

Кстати, повторюсь:

Balancer>> Может, ты и линии будешь по тригонометрии рисовать, а не по Брэзенхему? Или сортировать пузырьком? Или множители за пределы цикла не будешь выносить? [»]
Zeus> Смотря какая стоит задача.

Задача - быстро нарисовать линию

Zeus> Рома, это всего лишь показатель твоего, хм, незнакомства с тригонометрией. У меня на отладку ушло 5 минут, заработало со 2-го раза. На написание - минут 10.

Написание в Матлабе? Или же на чём-нибудь уровнем пониже?

Zeus> Это смотря какая задача стоит. Ты не сказал, что тебе надо самый быстродействующий алгоритм. Я и предложил самый простой и надежный.

Кхм. Смотрим первое сообщение: "Как быстрее определить, принадлежит ли этому многоугольнику заданная точка (x,y)?"

Разве слово "быстрее" применительно к алгоритму допускает трактовки?

Zeus> Скорее всего будет наоборот. Потому что явно можно считать прямо сумму косинусов. Но мне лень думать, как ее разложить (То есть помню для двух углов, но выводить дальше неохота )

Целочисленку тоже можно вылизать очень сильно. Загнать всё в целочисленные массивы, делать по ним один проход, минимизировать проверки...

Zeus> Глупости, сам алгоритм у меня несомненно проще

Проще - мой

•  4
•  инфо
•  инструменты
• Ответить на сообщение

Zeus> Вообще говоря, это лишь фича конкретных процессоров. Быстродействие алгоритма подсчитывается просто количеством операций.

Опять ЧЛ лезет в глобальные области. Только как-то неумело...

Zeus> Кстати говоря, для корректности ты должен проверять подсчет фиббоначи с int той же длины, что и double, т.е. int64.

Нет. Я не раз говорил об объёмах перекачиваемых данных. Это - тоже часть агоритма

Zeus> Да причем здесь именно углы и положения? Просто очевиднее, что сумма углов сразу дает нужный результат.

Мне - не очевидно. Зато все комбинации с отрезками я сразу вижу.

Zeus> Твоему процессору.

Ты знаешь массовые процессоры, у которых плавучка быстрее целочисленки?

Zeus> Быстро - начиная с момента выдачи задания или по быстродействию самого алгоритма? Я именно на это намекал. Кроме того, иногда наглядность - самоцель (например, для обучения).

Понял. Для меня быстрее будет по обоим параметрам по брезенхему Потому что пропорции я принимаю ближе и помню лучше, чем синусы с косинусами

Zeus> Практически без разницы. Отладка была бы такой же, а написание, может, раза в полтора дольше.

Ну так напиши вариант на Java

Zeus> Проверки тебе добавлять, а не минимизировать надо. А все остальное к обоим относится.

Зачем? Моя задача решена. Какие ещё проверки?

Zeus> Т.е. поставленную задачу ты все-таки не решил [»]

Задача стояла "для генерации распределения мобов по локациям на игровом сервере". Эта задача - решена

•  инфо
•  инструменты
• Ответить на сообщение

1. double fisrt_atan = Math.atan2(y - _points.get(i).y,_points.get(i).x - x);

Как я понимаю,

1.         double first_atan = Math.atan2(y - _points.get(0).y,_points.get(0).x - x);

?

Не работает. Ниодна точка теперь не попадает

Татарин> Не, с замыканием - там все ОК.

Давай, ищи ошибки дальше
Или, вон, Зевс пускай подключается. Как первый, предложивший эту идею

Татарин> А оно что, на яве писано?

Сервер. Не сама игра.
Впрочем, игры с Java в ядре тоже уже есть - тот же "Ил-2"

Татарин> Однако ж. [»]

Дык, проигрышь по скорости чистому С++ невелик (меньше, чем проигрышь плавучки целочисленке в наших тестах - на чистой математике проигрывает процентов 20 всего - Быстродействие языков тест2 ), зато больше возможностей, выше уровень языка, мощные библиотеки, сборка мусора...

•  1
•  инфо
•  инструменты
• Ответить на сообщение

digger> Тaкaя зaдaчa решaется функцией floodfill в грaфике. Прoвoдится гoризoнтaльнaя линия в oдну стoрoну. Если oнa пересекaет пoлигoн нечетнoе числo рaз, тo внутри, если четнoе, тo снaружи.Пересечение oтрезкa с гoризoнтaльным лучем - линейнoе урaвнение. [»]

Вот я так и сделал в итоге. И до сих пор идёт спор, какой вариант лучше

•  инфо
•  инструменты
• Ответить на сообщение

Zeus> Имхо, неумело тут твоя БЛ как-то работает. Скорость алгоритмов всегда определялась количеством операций, причем тут вообще ЧЛ?

Нет, это ты за БЛ хватаешься в чисто ЧЛ-задачах Есть конкретная задача. Смотри первую страницу. Есть два алгоритма, удовлетворяющих потребностям задачи. Один работает в 4 раза быстрее. У какого алгоритма выше скорость?

А число операций - скорость операций может различаться на порядки... Это не оценка

>И это именно глобальный показатель, не привязанный к конкретным техническим особенностям.

Вот-вот. А задача стоит конкретная. И не нужно тут сферических коней в вакууме

Zeus> Тогда придется признать, что возможности целочисленного алгоритма меньше - он заткнется на значениях, которые еще доступны double

И что из этого? Если максимальные координаты по карте составляют лишь ~2¹⁷, какие ещё "заткнётся" тут могут быть?

Zeus> Оффтопичный вопрос: ты хоть раз участвовал в олимпиадах по информатике? Вот там страсть как любят такие приколы. Вроде решишь задачу - а они зададут 20-значное число на тесте, и уж непременно выставят все "особенные" случаи. Все это приучает к корректности.

Ты не поверишь, но я именно с тестированием плотно знакомился, когда работал (пусть официально только админом) в российском подразделении Honeywell

А олимпиады - это фигня. Вот на собеседовании в контору, где делали Cybiko - вот там экзамен так экзамен был. Дикая смесь математики, разных платформ, языков... Единственное, на чём я выступил не блестяще - это была смесь комбинаторики с теорвером - по ней я всегда плавал Но что касалось оптимизации и предельных значений - это как раз был мой конёк

Zeus> Очень странно. Не могу даже объяснить ИМом

Ну, я не один тут, вон, этим страдаю

Zeus> Не все, коли пропустил столь элементарный случай. А когда дошло, просто махнул рукой - тоже типично современный подход.

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

>А еще ЧЛогиков ругаешь. Сам такой!

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

И уж тем более это было важно после, на процессах и аппаратах.

Так что, считай, что это впитано с молоком практики

Zeus> Зачем мне массовые? Мне хоть и приходилось работать на таком, но это в данном случае малосущественно, речь шла о показателе алгоритма, а не реализации.

Теоретик, блин. Опять сферические кони в вакууме. Мне что, в условия дописать "быстрый на Xeon 1800"?

Zeus> У меня ее нету. Точнее, машина есть, а среды нету. С командной строки пускать и тем более отлаживать - ну его нафик.

Кхм. У тебя что, FAR с Colorer'ом не установлен? Мне его по уши хватает, чтобы сейчас рулить проектом в 450 файлов, суммарным объёмом 2.5Мб

А уж для тестов - это вообще смешно, IDE требовать

И отладка - Java-VM при ошибке выдаёт подробнейшую диагностику, вплоть до номера строки файла с ошибкой и имени функции со всем стеком вызовов.

Расслабились, блин... Я последний раз IDE использовал... Даже уже и не помню когда. Когда там вышел C++ Builder 3.0? Вот как он вышел, так я IDE больше и не пользовался

>Тем более я сейчас не смогу скорость замерять - у меня комп постоянно занят рассчетами.

start /HIGH

Zeus> Не решена, коли валится на такой простой проверке. Решена лишь до уровня "и так сойдет!" - что еще хуже. Имхо, ненадежная программа хуже отсутствующей, при любых бенчмарках.

Хм. Задача решена с заданной точностью. Боюсь, в нашем институте тебе бы пришлось очень нелегко...

Zeus> P.S. А почему множественное цитирование перестало работать? [»]

Понятия не имею. Движок форума чёрным логиком писан, ИМХО

•  инфо
•  инструменты
• Ответить на сообщение