Как проверить, имеет ли вектор значение по определенному индексу
В ситуации «случайного блуждания» я имею двухмерный вектор с конфигурацией координат шага. Я хочу иметь возможность проверить, был ли занят определенный сайт, но проблема в том, что ось может быть нулевой, поэтому проверяем, fabs() координаты true (или что это имеет значение), не будет работать. Поэтому я рассмотрел циклическое выполнение шагов и проверку, равна ли моя координата другой координате на всех осях, и, если это так, повторение шага и повторная попытка (так называемый подход в глубину).
Есть ли более эффективный способ сделать это? Я видел, как кто-то использовал логический массив со всеми возможными координатами, например так:
bool occupied[nMax][nMax]; // true if lattice site is occupied
for (int y = -rMax; y <= rMax; y++)
for (int x = -rMax; x <= rMax; x++)
occupied[index(y)][index(x)] = false;
Но в моей программе число измерений неизвестно, так же как и такой подход:
typedef std::vector<std::vector<long int>> WalkVec;
WalkVec walk(1, std::vector<long int>(dof,0));
siteVisited = false; counter = 0;
while (counter < (walkVec.back().size()-1))
{
tdof = 1;
while (tdof <= dimensions)
{
if (walkHist.back().at(tdof-1) == walkHist.at(counter).at(tdof-1) || walkHist.back().at(tdof-1) == 0)
{
siteVisited = true;
}
else
{
siteVisited = false;
break;
}
tdof++;
}
работать где dof, если количество измерений. (проверка на ноль проверяет, является ли позиция источником. Три нулевые координаты или три посещенные координаты на одном шаге — единственный способ сделать это истинным)
Есть ли более эффективный способ сделать это?
Решение
Вы можете сделать эту проверку за O (log n) или O (1), используя набор STL или unordered_set соответственно. Контейнер unordered_set требует, чтобы вы написали пользовательскую хеш-функцию для ваших координат, в то время как контейнеру set нужно только, чтобы вы предоставили функцию сравнения. Реализация набора особенно проста, и логарифмическое время должно быть достаточно быстрым:
#include <iostream>
#include <set>
#include <vector>
#include <cassert>
class Position {
public:
Position(const std::vector<long int> &c)
: m_coords(c) { }
size_t dim() const { return m_coords.size(); }
bool operator <(const Position &b) const {
assert(b.dim() == dim());
for (size_t i = 0; i < dim(); ++i) {
if (m_coords[i] < b.m_coords[i])
return true;
if (m_coords[i] > b.m_coords[i])
return false;
}
return false;
}
private:
std::vector<long int> m_coords;
};
int main(int argc, const char *argv[])
{
std::set<Position> visited;
std::vector<long int> coords(3, 0);
visited.insert(Position(coords));
while (true) {
std::cout << "x, y, z: ";
std::cin >> coords[0] >> coords[1] >> coords[2];
Position candidate(coords);
if (visited.find(candidate) != visited.end())
std::cout << "Aready visited!" << std::endl;
else
visited.insert(candidate);
}
return 0;
}
Конечно, как упоминает iavr, любой из этих подходов потребует O (n) памяти.
Изменить: основная идея здесь очень проста. Цель состоит в том, чтобы сохранить все посещенные местоположения таким образом, чтобы вы могли быстро проверить, посещалось ли определенное местоположение. Ваше решение должно было сканировать все посещенные местоположения, чтобы выполнить эту проверку, что делает его O (n), где n — количество посещенных местоположений. Чтобы сделать это быстрее, вам нужен способ исключить большинство посещенных мест, чтобы вам не пришлось сравнивать их вообще.
Вы можете понять мое решение на основе множеств, подумав о бинарном поиске по отсортированному массиву. Сначала вы найдете способ сравнить (отсортировать) D-мерные местоположения. Это то, что класс Позиция » < оператор делает. Как отметил в комментариях iavr, это просто лексикографическое сравнение. Затем, когда все посещенные местоположения отсортированы в этом порядке, вы можете запустить бинарный поиск, чтобы проверить, была ли посещена точка кандидата: вы рекурсивно проверяете, найден ли кандидат в верхней или нижней половине списка, удаляя половину оставшегося списка из сравнения на каждом этапе. Эта половина поискового домена на каждом шаге дает вам логарифмическую сложность O (log n).
Контейнер набора STL — это просто хорошая структура данных, которая сохраняет ваши элементы в отсортированном порядке по мере их вставки и удаления, обеспечивая быстрое выполнение вставки, удаления и запросов. Если вам интересно, то реализация STL, которую я использую, использует красно-черное дерево для реализации этой структуры данных, но с вашей точки зрения это не имеет значения; все, что имеет значение, это то, что, как только вы дадите ему возможность сравнить элементы ( < оператор), вставляя элементы в коллекцию (set :: insert) и спрашивая, есть ли элемент в коллекции (set :: find) O (log n). Я проверяю на предмет происхождения, просто добавляя его в посещаемый набор — нет никаких причин относиться к нему специально.
Unordered_set — это хеш-таблица, асимптотически более эффективная структура данных (O (1)), но сложнее в использовании, потому что вы должны написать хорошую хеш-функцию. Кроме того, для вашего приложения достаточно перейти от O (n) к O (log n).
Другие решения
Ваш вопрос касается алгоритма, а не использования языка (C ++), поэтому вот общий ответ.
Что вам нужно, это структура данных для хранения набора (координат точек) с эффективной операцией для запроса, находится ли новая точка в наборе или нет.
Явное хранение набора в виде логического массива обеспечивает запрос с постоянным временем (самый быстрый), но в пространстве, которое экспоненциально по количеству измерений.
Исчерпывающий поиск (ваш второй вариант) предоставляет запросы, которые являются линейными по заданному размеру (длине шага), в пространстве, которое также является линейным по заданному размеру и не зависит от размерности.
Двумя другими распространенными опциями являются древовидные структуры и хеш-таблицы, например доступно как std::set (обычно с использованием красно-черного дерева) и std::unordered_set (последняя только в C ++ 11). Древовидная структура обычно имеет запрос логарифмического времени, в то время как на практике запрос к хеш-таблице может быть постоянным, что почти возвращает вас к сложности логического массива. Но в обоих случаях необходимое пространство снова линейно по заданному размеру и не зависит от размерности.