Двойной ассоциативный массив

чтобы (|X-X₀| + a*|Y-Y₀|) было минимальным

чтобы X + a*Y было минимальным, а то люди запутаются.

А нет, ступил.

Нужно просто написать свой less

Это получается двумерная сетка Воронова (гугль в помощь).

А для std::map будет неоднозначность, less так сделать увы не получится, так что map неприменим (ну или это будет ооочень хитровыкрученный map).

Нужно просто написать свой less

Ага... напишете? Мне очень интересно посмотреть.

А сколько исходных точек и насколько неравномерно они расположены? Если точек немного, то проще всего поиск тупым перебором. Если точек много, то вводим прямоугольную сетку (если точки раскиданы равномерно то равномерную, если нет то рекурсивную или через тот же map), в каждую ячейку кладем точки, которые могут быть найдены при попадании ключа в эту ячейку, дальше перебор по ячейке.

вообще то соврал, не сетка Воронова, там метрика другая... но идеологически близко к ней. Это где ж такие извращения требуются?;-)

Да, сейчас сделано именно так: по одной переменной бининг дискретный, по другой непрерывный. Проблема в том, что если бины по первой переменной сделать слишком узкими, они оказываются недозаселенными, и найденный в результате объект оказывается не самым лучшим, а если они слишком широкие, то страдает точность по первой переменной.

Возникла идея и по первой переменной сделать непрерывный бининг. Пока что самый лучший вариант из рассматриваемых - нарезать очень узких бинов, и искать по 3-5 бинам в окрестностях найденного. Но меня не покидает идея сделать все «по уму».

А что есть бининг и кто такие бины?;-)

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

кури квадро деревья

твоя поправка ( маштобирование оси y ничего неменяет (т.е прежде чем искать соседа умножаеш Y и в структруре аY храниш (для уточнение а>0?)))

метрика котороя у тебя - гугль_знает метрика НьюЙорка(ститы и авеню)

найди(их море) готовое потюнь

А требуются они для ускорения симуляции. Мы симулируем поведение частицы в зависимости от ее параметров. Когда энергия частицы становится достаточно маленькой, мы прекращаем симуляцию, и вместо этого подставляем значение из библиотеки. Вот для библиотеки это и надо: найти объект с параметрами максимально близкими к параметрам частицы.

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

Т.е сначала преобразовываем ключ (шкалирование по x и поворот) потом ищемся. Если лень искать квадро дерево, могу поделится реализацией через std::map;-)

А что за частица, сели не секрет?

вот точнее

обьяснение : http://e-maxx.ru/forum/viewtopic.php?id=189

вот вика-дерево отрезков : http://ru.wikipedia.org/wiki/Дерево_отрезков

http://e-maxx.ru/algo/segment_tree

Элементарная частица. Вообще говоря любая, но ускоряем мы только электроны фотоны и нейтроны, просто потому что их у нас больше всех. Эксперимент ATLAS, LHC. Где еще кроме как в науке дадут поразмышлять «а как бы еще это сделать получше да поэлегантнее?». В коммерции все проще: deadline и баста. Работает хоть как-то, и хорош.

Короче я понял, q-деревья наше всьо.
*ушел кочегарить гугла

Напиши свой класс ключа с двумя полями и своим собственным less, который сравнивает по выражению, которое требуется минимизировать.

Алгоритм сравнения для таких ключей реализующий метрику ТС-а можете привести?

Нет. Более того, я повторил ошибку анонимуса, который отписался самым первым.

Признаю =)

Мне кажется или в реальности быстрее это написать чем искать существующие решения (такой на первый взгляд примитивной задачи)

ускоряем мы только электроны фотоны и нейтроны

Я не в теме, но как ускоряют фотоны?

Данные статичны? или имеют место частые операции вставки/удаления?

В первом случае – упорядоченный (сортированный) по условию вектор:

int myLess (Point const& lhs, Point const& rhs) {
  if ( lhs.x < rhs.x ) return 1;
  return lhs.y < rhs.y;
}

Эксперимент ATLAS, LHC.

У нас в соседней лаборатории тоже для него что-то крутят. Но я не в курсе, я там не работаю. Что-то прямо на vhdl клепают.

ускоряем

фотоны

ты ничего не путаешь?

quasimoto:

Я не в теме, но как ускоряют фотоны?

nanoolinux:

ты ничего не путаешь?

morse:

А требуются они для ускорения симуляции

Нет, я ничего не путаю

И как по Вашему это поможет ТС-у?

lower_bound обычный пару раз использует.

Да-да, использует. Но какое это отношение имеет непосредственно к задаче ТС? Алгоритм целиком написать можете?

как-то так:

iter = lower_bound ( sorted.begin(), sorted.end(), EqualsX(X0) );
// проверка на корректность iter ...

// advance iter to left and right
last = iter;
while ( last != sorted.end() && last->X < X0+b ) ++last;

first = iter;
while ( first >= sorted.begin() && first->X > X0-b ) --first;

min_element (first, last, CompareByY(Y0))

lower_bound подразумевает упорядоченную последовательность, так что ТС нужно позаботиться о выдумывании порядка для своих данных, либо забить это и использовать вложенный partition.

1) хранить библиотечные значения отсортированными по расстоянию (в указанной метрике) до начала координат заданной фазовой плоскости (X,Y) — одномерная map'а;

2) при поиске ближайшей библиотечной точки к текущей найти центр поиска — расстояние текущей точки до начала координат — M;

3) от этого центра взять ближайшую библиотечную точку в map'е, расчитать реальное расстояние от нее до текущей точки — M0;

4) от центра поиска отложить в обе стороны M0 — это задаст отрезок, в котором находятся претенденты на минимум расстояния до текущей точки;

5) при проверке перебором библиотечных точек из отрезка [M-M0; M+M0] нужно проверять сначала ближайшие к M точки и в случае нахождения более близкой точки с M1 < M0 тем самым автоматически сужается и диапазон поиска: [M-M1; M+M1];

6) т.о. два встречных процесса однажды сойдутся и это будет критерием окончания поиска;

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

Упорядочить как то библиотечные точки лехко. Вот только это упорядочивание никак не помогает решить задачу - ближайшая к заданной библиотечная точка по метрике ТС-а может не быть ближайшей по критерию упорядочения а лежать вообще черти где. Придумать же критерий упорядочения, который будет выдавать ближайшую точку по метрике ТС-а невозможно. Да даже по метрике ТС-а упорядочить для rb_tree точки невозможно, там же модуль разности координат двух точек стоит стоит.

Трудоемкость алгоритма зашкаливает. У меня там не двадцать объектов, а сто тысяч как минимум. Сначала уныло отсчитывать несколько тысяч элементов по одному в каждую сторону, а потом искать самый близкий в массиве, отсортированном по другому ключу. Как-то невесело.

Гм, любопытно. А откуда следует:

4) от центра поиска отложить в обе стороны M0 — это задаст отрезок, в котором находятся претенденты на минимум расстояния до текущей точки

То есть алгоритм-то все равно, конечно, не подходит, ибо присутствует перебор, но ради общего образования, почему минимум невозможен снаружи от отрезка?

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

Но все равно это будет хуже, чем поворот координат на 45% (сразу переходим к прямоугольникам -> расщепление по координатам) и дальше квадрупольное дерево. Только вот одной точке может соответствовать несколько листьев дерева, и вот как его набивать - это отдельная задача;-)

То есть алгоритм-то все равно, конечно, не подходит, ибо присутствует перебор, но ради общего образования, почему минимум невозможен снаружи от отрезка?

Такое ограничение задает кольцо (ромб) с шириной 2*M0... и на самом деле да, искомая точка может в нем и не лежать;-) Т.е. упорядочивать лучше по одной из координат. Ну или сетку по одной из координат, по другой координате map-ы в каждой ячейке сетки для областей влияния точек.

Я решал чем то похожую задачу, есть набор D-параллелепипедов в D-мерном пр-ве, надо найти параллелепипед которому принадлежит точка. Сделал в итоге через map::lower_bound - упорядочиваем последовательно по всем координатам нижние левые углы параллелепипедов, ищем нижнюю границу, затем идем к началу и перебором проверяем. Это условно ускоряет поиск в разы по сравнению с полным перебором...

Если используется второй вариант метрики - сделать индекс по X. Сложность lower_bound логарифмическая, так что всё зависит от распределения ваших данных, если они «размазаны» по X значительно более «размазанности» по Y то сложность будет небольшой.

Опять же, лобовой подход - partition.

А ничего, что ближайшая по Х точка может быть самой дальней по целевой метрике? Скажем вот есть точки

100 0
99 2
...
0 200

да, фэйл.

А откуда следует:

из неравенства треугольника: имеем два треугольника с единой стороной, вторая же сторона одного треугольника должна быть больше суммы оставшихся строн другого;

То есть алгоритм-то все равно, конечно, не подходит, ибо присутствует перебор

ну, перебор в любом случае будет, даже если он спрятан в std::map::find() и имеет сложность O(lnN) — это все равно перебор, просто оптимизированный как-то; здесь весь вопрос в сравнении сложностей для конкретных значений, т.е. алгоритм O(N) может оказаться быстрее алгоритма O(lnN) и даже O(1) для каких-то частных случаев реализаций, входных данных, значения самого N

КОнтрпример - все точки лежат на оси ОХ. Есть точки с х -4, -6, 7. Ищем точку ближайшую к х=5 - по Вашему алгоритму по метрике от начала координат ищемся между -4 и -6, 7 не попадает.

из неравенства треугольника: имеем два треугольника с единой стороной, вторая же сторона одного треугольника должна быть больше суммы оставшихся строн другого;

БОЛЬШЕ??? Вообще то она может быть как больше, так и меньше, треугольники то разные.

Алгоритм хороший, только упорядочивать не обязательно метрике, можно по любой из координат

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

Но все равно это будет хуже, чем поворот координат на 45%...

в это не врубился :)

после маштабирования Y ( для устранения X)

эквиудалёные точки образуют квадрат относительное даной со сторонами диагональными осям.

поэтому если повернуть осьи и отмаштобировать сетку что бы данная точка была в центре клетки то клетка образует ячейку .

а вообще топис стартеру дали наилучшее пo O(nlogn) решение чё он не пишет :)

Нарисовал на бумажке, и все стало понятно.
Да, это будет работать. Вот только изначальный M0 нам не очень-то и нужен. Финальный алгоритм будет выглядеть так:
метрика M1 - расстояние от (0,0), метрика M2 - требуемая. Массив отсортирован по M1
1) Находим точку ближайшую к искомой по метрике M1
2) Начинаем от этой точки отходить по одному в каждую сторону, сохраняя на каждом этапе минимально найденное значение по метрике M2 и максимальное (последнее) по метрике M1
3) Как только расстояние по метрике M1 превысит минимальное по M2 - поиск прекращаем, дальше искать бесполезно. Искомое значение - то у которого было минимальное расстояние по M2

КОнтрпример - все точки лежат на оси ОХ. Есть точки с х -4, -6, 7. Ищем точку ближайшую к х=5 - по Вашему алгоритму по метрике от начала координат ищемся между -4 и -6, 7 не попадает.

M=5

M0=|-4-5| +|0-0|=9

ищем в отрезке [-4; 13] — 7 сюда попадает, все нормально! :)

БОЛЬШЕ???

«вторая же сторона одного треугольника должна быть больше суммы оставшихся строн другого» — это следствие условия, что претендующая точка находится за пределами отрезка, полученного на первом шаге

поэтому если повернуть осьи и отмаштобировать сетку что бы данная точка была в центре клетки то клетка образует ячейку .

Все увы сложнее. Построим в области прямоугольники, так что бы в центре каждого была библиотечная точка, и прямоугольники не пересекались. Между ними увы будут пустоты, которые тоже придется как то делить между точками... т.е. в итоге вся область будет покрыта прямоугольниками, но одной точке будет соответствовать неск прямоугольников (область относящаяся к одной точке невыпуклый многоугольник со сторонами параллельными осям координат), ну и разбиение области и построение соотв. квадро-дерева это зада куда более сложная чем перебор и всякие упорядочения.

ищем в отрезке [-4; 13] — 7 сюда попадает, все нормально! :)

Да, работает, это я туплю...

эквиудалёные точки образуют квадрат относительное даной со сторонами диагональными осям.

понял!

но это все хорошо, когда табличные точки заданы в узлах сетки, тогда, путем поворота координат на 45%, можно получить ровную квадратную сетку областей притяжения и попадание в конкретный квадрат находится легко, поскольку все квадраты равны, не пересекаются и плотно ровно уложены;

а как быть если табличные точки заданы хаотично? границы областей притяжения в этом случае будут сложные ломаные, а при повороте, наверно, получится стена из прямоугольников разных размеров, хоть и плотно уложенных и без пересечений :) как в ней искать?

Да, это будет работать. Вот только изначальный M0 нам не очень-то и нужен.

ну, просто мой M0 — это твой M2 на первом шаге твоего п.2; а мой M1 — это твой M2 на втором твоем шаге п.2 :)

Финальный алгоритм будет выглядеть так:

ну переписал алгоритм по-своему, да

суть то — один в один :)

как в ней искать?

Квадро-дерево же.

Вот еще один алгоритм, на основе преобразования Радона. Вводим неск направлений, упорядочиваем все точки по каждому направлению. Находим ближайшую точку к искомой по каждому из направлений, потом перебором ищем среди них уже по целевой метрике. Наверное учитывая симметрию задачи, хватит 4х направлений - оси координат и диагонали?

Суть-то еще и уметь передать надо :) Мне почему-то «мой» вариант более логичным кажется. Может это просто болезнь молодого программиста «чужой код», я от нее еще не до конца вылечился.