Russian Qt Forum

Добрый вечер

Хочу предложить задачу которая в моей практике встречается очень часто. Есть массив (вектор, контейнер). Нужно удалить "повторяющиеся" элементы, template реализация неизбежна. При этом необходимо учитывать:

- слишком дорого месить (сортировать) сам массив (часто гигабайты). Надо обойтись указателями

- в общем случае нет оператора == (хотя можно рассчитывать на оператор < при сортировке). Пример: если 2 точки (x. y) или (x, y, z) отстоят друг от друга на расстояние меньше заданного (напр 1.0e-5) то их надо слить. Здесь возникают подлянки: напр. если есть "цепочка" точек, то легко удалить все кроме первой, но это будет неверно

- индексы исходных данных используются другими данными. Надо сделать пере-индексацию. Пример: было 100 точек. В результате упаковки осталось напр 50. Но есть др массив(ы) который хранит индексы исходных точек. Поэтому "просто упаковать" недостаточно. Нужно как-то сказать ссылающемуся массиву что, напр. точка которая была 65 (до упвковки) - теперь 40 и.т.д

Есть мысли (паттерн  :))?
Спасибо

P.S. Виноват, забыл об одной важной детали: порядок следования точек не должен быть изменен упаковкой

Вернее индексы.
Имеем исходный список объектов. Строим нужный список индексов.



Для сортировки всегда достаточно иметь определенным одно отношение "<=" (или ">="). Иметь определенным "=" не обязательно.
Но!, множество должно быть линейно упорядоченно.

Здесь же какая-то мешанина. Судя по описанию не определено именно отношение "<", но возможно определено "=". Выделил противоречие.
Это сножество не является линейно упорядоченным. Возможно можно выделить частичный порядок. Так что о стандартной сортировке можно забыть.

Можно почитать здесь:
http://ru.wikipedia.org/
Упорядоченное множество



Опять же, строим вторичный индекс и нет проблем.

Дело вкуса указатели или индексы.

Какое противоречие? Пусть элемент QPoint2D(x, y). Любые операторы < и др. для сортировки прекрасно  определены. Оператор == да, тоже определен, но мы не можем его использовать для слияния близлежащих точек.

Хммм... то що це менi дало?  :) Можно как-то попроще пояснить? Спасибо

а можно спросить?  а(5,15) < б(0,17) это верно или нет? Что вообще означает < или > в контексте данного множества?

Ну чего ж нельзя?  :)
Это так "верно" как задан ключ сортировки. Напр

C++ (Qt)
bool Point2D::operator < ( const Point2D & p ) const
{
 if (x < p.x) return true; 
 if (x > p.x) return false;
 return y < p.y; 
}
 

Можно поменять < на > для прореживания это значения не имеет. Но ключ должен быть однозначным, напр так

C++ (Qt)
bool Point2D::operator < ( const Point2D & p ) const
{
 return (x < p.x) || (y < p.y);
}
 

неверно

Важно не то, что определен оператор "<=". Важно выполнение следующего условия.
Для любых X, Y, Z из данного множества должно выполняться: если X<=Y и Y <= Z, то X <= Z

А в данном случае это не так.

Ну если такое упорядочивание устраивает, то OK.
Но на мой взгляд от него мало толку. Поскольку кординаты X и Y независимы и имеют одинаковый приоритет, а в данном случае вы искуственно выделяете X.

Извиняйте, но это вообще бредовая идея определять оператор неравенства для такого объекта, как Point2D

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

Безусловно, иначе сортировка неоднозначна
Именно так, иначе прошу привести пример где первый оператор поста #4 не срабатывает

Это впечатление всегда возникает  :) Казалось бы - есть 2(3) ключа, но увы, нет способа задействовать все (эффективно)
 
Придется если хотим использовать std::sort

В пространстве такая сетка называется lattice и использовать ее - очень дорогое удовольствие  :) А в данном случае не видно - зачем? С простой сортировкой проблем нет

Если все устраивает, не понятно в чем собственно проблема?
Строим индекс. Сортируем. Что еще? Все примитивно.

На первый взгляд да  :) Но вот почему-то хорошей реализации на template я написать не смог. Сильно жмет ограничение "нельзя менять порядок"

"нельзя менять порядок" ???

Да. Упакованный массив может иметь меньше элементов, но они должны следовать в том же порядке что и в начальном. Обычно это вызывается тем что несколько упакованных массивов должны "сбиваться" по индексам (напр. для морфа).

Делаем индекс который сортируем и чистим как надо итд.
Если нужен исходный массив, то оставляем его как есть, если нет, то чистим (то что не вошло в наш индекс).

Все так, вот только проблемы с "и.т.д"  :) Мне тоже все понятно (может лучше было даже запостить в раздел С/С++). Но почему-то когда я начинаю "реализовывать" - не очень красиво получается, и трудности/проблемы наползают одна на другую  :'(

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

Ну если все просто, то никто не мешает написать ф-цию

C++ (Qt)
template <class T1, class T2>
void PackContainer( T1 & vec, T2 & remapIndex )
{
 ...
}
 

Все что надо описано в посте #1, не требуется знания доп. деталей, др. классов и. т.п. Вот только ф-ция не очень получается  :)

Естественно что ничего не получится. Раз не определен оператор "==" то нечего фильтровать!


С другой строны вполне возможно определить оператор "==" как написано выше, т.е точки равны если расстояние между ними не перевышает delta. Но даже если сбросит со счетов проблему с "цепочками"(которая решается кластерным анализом итп.; считаем что точки равны если они в одном кластере), мы имеем другую, примитивную проблему!

При введении оператора "==" для двумерного случая вы нарушите требование к линейной упорядоченности(которая была определена в #4), пример:
Пусть delta = 2, тогда для точек A(0, 0), B(3, 0), , С(0, 1) мы получаем:
1) для операции "<=": A<=B<=C
2) для операции "==": A!=B и A==C
3) поскольку A<=B и A!=B => A<B
4) поскольку A==C => C<B.
5) Но из (1) и (4) получаем противоречие B<=C и B>C

Так что для данной модели данных описанный(желаемый) вами способ фильтрации не подойдет.

Ну такой стремный оператор == определять никак не хочется - это ж "Агент" в тылу  :) Но ведь никто не мешает обойтись без него. Почему напр не так

C++ (Qt)
#define XY_TOLERANCE  1.0e-5f
inline bool CanMerge( const Point2D & p0, const Point2D & p1 )
{
  return (p1 - p0).length() < XY_TOLERANCE;
}
 

Да, придется выписать CanMerge для каждого типа, но это нормально, template требует жертв  :)

1) Прежде чем пытаться сделать template, не понятно кому и для чего нужный, необходимо разобраться с самой системой данных и алгоритмами!
2) Ваш CanMerge в плане проблемы отсутствия линейной упорядоченности  равносилен приведенному мной "==". Даже более строго - оба варианта системы изоморфны
3) 2D систему можно сделать линейно упорядоченной по оперции "<=", но введение операции "==" (CanMerge, кластеров, итп.) основанной на расстоянии между точеками всегда приведет к нарушению линейной упорядоченности
4) Не получится отсортировать имеющиеся у вас данные(описанная система) таким образом, чтобы объединить(отфильтровать) их за линейное время O(n) (n кол-во элементов).

1) Я никогда не стал бы городить template "ради спортивного интереса". Но здесь деваться некуда - реально надо. Ограничимся лишь 1 примером: есть 2D точки (x, y) и 3D (x, y, z). Для обоих задача та же самая (пост #1). Так что мне 2 ф-ции писать? Или "конвертировать 2D в 3D а потом обратно"?  :)  А всего типов данных с десяток наберется, так что, с каждым "извиваться"? Ну расскажу я откуда они берутся, а что это изменит? Я должен обработать данные что мне дали а не те что "мне хочется".

2) и 3) Но ведь никто не предлагал использовать CanMerge для упорядочивания. Там все хорошо со скромным оператором <

4) За линейное или как - задача отфильтровать за разумное время (понятно квадратичный перебор умрет).

ОК


ОК

======================
Теперь вопросы.

1) Вам известен устраивающий вас алгоритм для обработки каждого типа данных?
2) Если положительный (1)!
  Этот алгоритм один для всех типов которые вы используете?

Да, алгоритм один - иначе разговор о template беспочвенен/некорректен. Начало очевидно - сортируем указатели (или индексы). Дальше надо "прореживать" - вот тут дело хитрое. Сортировка поставит указатели "как хочет" а нам надо сохранить порядок следования при удалении. И это не все.
Если test = true, все ясно, i-й и j-й элемент слить можно. Но если test = false, это совсем НЕ значит что с i-м элементом "уже разобрались". Он может сливаться напр с j+1 элементом (ключу сортировки это не противоречит)

А на первый взгляд - простая задачка  :)

Я не даром написал: "2) Если положительный (1)!"
И написал "обработки", а не сортировки или другой предварительной подготовке! Разговор шел об алгоритме решения задачи от и до!
Вам не известен алгоритм для решения вашей задачи. Какой может быть разговор о templates.
Templates - это не расширение алгоритмических возможностей. Это удобство.
И как это ни странно, templates применять надо с осторожностью и не часто! Как бы не кричали любители templates.


А про это я писал! Так не получиться.
Вы можете спокойно унифицированно прореживать одномерные массивы разных типов.
Но, нельзя свести в общем n-мерный к (n-1)-мерному случаю.

Возможно, стоит начать сначала, забыть пока про templates, и разобраться с алгоритмом. А когда он будет определен, тогда и можно будет вернуться к templates.

Ну может не стоит "агитировать большевика за революцию"? Мое мнение о template такое же  :)

Известен (ведь как-то же я живу  :))

- "встали" на элемент (base)

- идем по сортированному массиву вперед пока не останется элементов для слияния c base. Конкретно для 2D (3D) точки (ключа) условие конца

vec[i].x - vec[base].x > TOLERANCE; // i > base
 

- после этого "диапазон слияния" определен. Разбирается с ним, сортируя диапазон (ну здесь очевидно, надо только не забыть про порядок и пере-индексацию)

А вот с template не ложится - а хотелось бы!

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

Если уже есть реализация для некоторого типа, то проще всего отталкаваться от нее, просто сделать ее шаблонной. Подставляем вместо конкретных типов T1, T2, ... Определяям необходимые общие методы, реализовываем их для каждого типа(у кого они не реализованы). Далее, при необходимости, можно занимать оптимизациями алгоритма и интерфейса.

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

Видимо да, надо подучиться. Книжка не "Александреску" случайно? (много слышал но не читал). Буду признателен за ссылочку.

FYI: эта задача называется "weld vertices"

Смотри сообщение в личке.

а мне?:)

Кому еще, пишите в личку.