Упаковка массива

[Igors]

Добрый вечер

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

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

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

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

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

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

[spectre71]

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

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

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

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

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

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

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

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

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

[Igors]

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

Вернее индексы.

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

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

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

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

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

[ufna]

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

[Igors]

а можно спросить? 

Ну чего ж нельзя? 

а(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);
}
 

неверно

[spectre71]

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

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

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

[spectre71]

а можно спросить? 

Ну чего ж нельзя? 

а(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);
}
 

неверно

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

[m_ax]

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

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

[Igors]

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

Безусловно, иначе сортировка неоднозначна

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

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

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

Это впечатление всегда возникает  Казалось бы - есть 2(3) ключа, но увы, нет способа задействовать все (эффективно)
 

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

Придется если хотим использовать std::sort

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

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

[spectre71]

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

[Igors]

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

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

[spectre71]

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

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

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

[Igors]

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

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

[spectre71]

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

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

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

[Igors]

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

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