Проверка, находится ли элемент в наборе C ++, очень медленная

Question

Я реализую алгоритм, который подразумевает много проверок, находятся ли элементы в наборе / списке. Я использовал std::vector контейнеры, но время росло экспоненциально по мере роста вектора.

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

bool in_set(set<Node> node_set){
  return node_set.find(*this) != node_set.end();
}

Однако эта функция занимает около 2 с для очень маленьких наборов (1-3 элемента), что делает весь мой алгоритм непригодным для использования.

Пользовательский класс, который я использую, выглядит следующим образом:

class Node{
    public:
      int d;
      int h_score;
      int coordinates [3];
      Node* parent_address;
};

Оператор сравнения, который я реализовал, выглядит следующим образом:

bool operator<(Node other) const{
  return concatenate(concatenate(this->coordinates[0], this->coordinates[1]), this->coordinates[2]) < 
  concatenate(concatenate(other.coordinates[0], other.coordinates[1]), other.coordinates[2]);
}

Edit: функция сцепления, кажется, не занимает много времени при выполнении, она выглядит так:

int concatenate(int i, int j) {
    int result = 0;
    for (int x = i; x <= j; x++) {
       result = result * 10 + x;
    }
    return result;
}

Знаете ли вы, почему это занимает так много времени и, что более важно, как сделать это быстрее?

Answer 1

Прежде всего, вы можете попробовать передать Set как const &, а не в operator <также как const &. </p>

bool in_set(const set<Node>& node_set){
  return node_set.find(*this) != node_set.end();
}

А

bool operator<(const Node& other) const

Он будет использовать ref вместо копии вашего набора и объектов Node.

Answer 2

Знаете ли вы, почему это занимает так много времени

concatenate(1, 100000000) занимает 1,3 секунды на моем Raspberry Pi, этот способ слишком медленный и фактически бесполезный

Также обратите внимание, что из-за возможных переполнений сцепление может дать одинаковый результат для разных узлов, это несовместимо для оператора <</em>

как сделать это быстрее?

вам нужно найти что-то еще, кроме этих вызовов сцепления, чтобы реализовать ваш оператор <</em>

Что тебе нужно? важен порядок в наборе или его можно заменить другим?

Не обязательно создавать уникальный идентификатор для сравнения двух узлов, сравнивать их напрямую, например:

bool operator<(const Node & other) const{
  if (coordinates[0] < other.coordinates[0]) 
    return true;
  if (coordinates[0] >= other.coordinates[0]) 
    return false;

  if (coordinates[1] < other.coordinates[1])
    return true;
  if (coordinates[1] >= other.coordinates[1])
    return false;

  return (coordinates[2] < other.coordinates[2]);
}

Чтобы понять, что оператор <</em> работает, вы можете рассмотреть node.coordinates поддерживает большое число, в 3 раза превышающее int , поэтому я сравниваю старшие биты, то если равны средним битам, то если равны младшим битам, используемым для набора

Answer 3

Ваш operator< получает копию Узла. Также нет необходимости создавать строки для сравнения, встроенный класс tuple может сделать это:

Как насчет:

bool operator<(const Node& other) const {
    return std::make_tuple(coordinates[0], coordinates[1], coordinates[2]) < 
           std::make_tuple(other.coordinates[0], other.coordinates[1], other.coordinates[2]);
}