Блог

Представьте, что у вас есть std::list с набором значений в нем. Ради демонстрации мы скажем, что это просто std::list<int> , но в моем случае это фактически 2D точки. В любом случае, я хочу удалить один из пары int s (или точек), которые удовлетворяют какому-то критерию расстояния. Мой вопрос в том, как подойти к этому как к итерации, которая выполняет не более O (N ^ 2) операций.

Пример

Источником является список int , содержащий:

{ 16, 2, 5, 10, 15, 1, 20 }

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

{ 16, 2, 5, 10, 20 } если бы я повторил вперед или

{ 20, 1, 15, 10, 5 } если бы я повторил итерацию в обратном направлении

Я чувствую, что должен быть какой-то потрясающий способ сделать это, но я застрял с этим двойным циклом итераторов и пытаюсь стереть элементы во время итерации по списку.

Создайте карту «регионов», по сути, std::map<coordinates/len, std::vector<point>> . Добавьте каждую точку в свою область и каждую из 8 соседних областей O(N*logN) . Запустите алгоритм «nieve» для каждого из этих меньших списков (технически, O(N^2) если не существует максимальной плотности, тогда она становится O(N*density) ). Наконец: В вашем исходном списке выполните итерацию по каждому point , и если он был удален из любого из 8 мини-списков, в которые он был помещен, удалите его из списка. O(n)

Без ограничения плотности это O(N^2) и медленно. Но это становится все быстрее и быстрее, чем больше разбросаны точки. Если точки несколько равномерно распределены по известной границе, вы можете переключиться на двумерный массив, что делает это значительно быстрее, и если существует постоянный предел плотности, это технически делает этот O(N) алгоритм.

Кстати, именно так вы сортируете список из двух переменных. Проблема с сеткой / картой / 2dvector.

[ПРАВИТЬ] Вы упомянули, что у вас тоже возникли проблемы с методом «nieve», так что вот это:

 template<class iterator, class criterion>
iterator RemoveCriterion(iterator begin, iterator end, criterion criter) {
    iterator actend = end;
    for(iterator L=begin; L != actend;   L) {
        iterator R(L);
        for(  R; R != actend;) {
            if (criter(*L, *R) {
                iterator N(R); 
                std::rotate(R,   N, actend);
                --actend;
            } else
                  R;
        }
    }
    return actend;
}
  

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

У Cubbi был лучший ответ, хотя он удалил его по какой-то причине:

Похоже, что это отсортированный список, и в этом случае std::unique выполнит работу по удалению второго элемента каждой пары:

 #include <list>
#include <algorithm>
#include <iostream>
#include <iterator>
int main()
{
    std::list<int> data = {1,2,5,10,15,16,20};
    std::unique_copy(data.begin(), data.end(),
                    std::ostream_iterator<int>(std::cout, " "),
                    [](int n, int m){return abs(n-m)<=1;});
    std::cout << 'n';
}
  

демонстрация:https://ideone.com/OnGxk

Это тривиально распространяется на другие типы — либо путем изменения int на что-то другое, либо путем определения шаблона:

 template<typename T> void remove_close(std::list<T> amp;data, int distance)
{
    std::unique_copy(data.begin(), data.end(),
                    std::ostream_iterator<int>(std::cout, " "),
                    [distance](T n, T m){return abs(n-m)<=distance;});
    return data;
}
  

Который будет работать для любого типа, который определяет operator - и abs , позволяющий находить расстояние между двумя объектами.

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

Возможно, вы могли бы поддерживать набор битов на основе критерия. Например. предположим, что abs (n-m)<1) является критерием. Предположим, что первый элемент имеет размер 5. Это переносится в новый список. Итак, измените bitset[5] на 1. Затем, когда вы сталкиваетесь с элементом размера, скажем, 6, вам нужно только проверить

 !( bitset[5] | bitset[6] | bitset[7])
  

Это гарантировало бы, что ни один элемент не находится в пределах величины 1 результирующего списка. Однако эту идею может быть трудно распространить на более сложные (недискретные) критерии.

Как насчет:

 struct IsNeighbour : public std::binary_function<int,int,bool>
{
    IsNeighbour(int dist)
        : distance(dist) {}
    bool operator()(int a, int b) const
        { return abs(a-b) <= distance; }
    int distance;
};

std::list<int>::iterator iter = lst.begin();
while(iter != lst.end())
{
    iter = std::adjacent_find(iter, lst.end(), IsNeighbour(some_distance)));
    if(iter != lst.end())
        iter = lst.erase(iter);
}
  

У этого должно быть O (n). Выполняется поиск первой пары соседей (которые находятся на максимальном some_distance расстоянии друг от друга) и удаляет первый из этой пары. Это повторяется (начиная с найденного элемента, а не с начала, конечно) до тех пор, пока пары больше не будут найдены.

РЕДАКТИРОВАТЬ: О, извините, вы сказали любой другой, а не только его следующий элемент. В этом случае приведенный выше алгоритм работает только для отсортированного списка. Поэтому вы должны сначала отсортировать его, если это необходимо.

Вы также можете использовать std::unique вместо этого пользовательского цикла выше:

 lst.erase(std::unique(lst.begin(), lst.end(), IsNeighbour(some_distance), lst.end());
  

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

Для 2D точек вместо целых чисел (одномерных точек) это не так просто, поскольку вы не можете просто отсортировать их по евклидову расстоянию. Итак, если ваша реальная проблема заключается в том, чтобы сделать это в 2D точках, вы могли бы перефразировать вопрос, чтобы указать на это более четко, и удалить упрощенный пример int.

Я думаю, это сработает, если вы не возражаете против создания копий данных, но если это всего лишь пара целых чисел / чисел с плавающей запятой, это должно быть довольно недорогим. Вы проводите n ^ 2 сравнения, но используете std::algorithm и можете объявить входной вектор const .

 //calculates the distance between two points and returns true if said distance is 
//under its threshold
bool isTooClose(const Pointamp; lhs, const Pointamp; rhs, int threshold = 1);     
vector<Point>amp; vec; //the original vector, passed in
vector<Point>amp; out; //the output vector, returned however you like

for(b = vec.begin(), e = vec.end(); b != e; b  ) {
    Pointamp; candidate = *b;

    if(find_if(out.begin(),
               out.end(),
               bind1st(isTooClose, candidate)) == out.end())
    {//we didn't find anyone too close to us in the output vector. Let's add!
        out.push_back(candidate);
    }
}
  

std::list<>.erase(remove_if(…)) с использованием функторов

http://en.wikipedia.org/wiki/Erase-remove_idiom

Обновление (добавлен код):

 struct IsNeighbour : public std::unary_function<int,bool>
{
  IsNeighbour(int dist)
    : m_distance(dist), m_old_value(0){}
  bool operator()(int a)
    { 
      bool result = abs(a-m_old_value) <= m_distance; 
      m_old_value = a; 
      return resu<
    }
  int m_distance;
  int m_old_value;
};

main function...
std::list<int> data = {1,2,5,10,15,16,20};
data.erase(std::remove_if(data.begin(), data.end(),  IsNeighbour(1)), data.end());