Поиск вхождения векторной записи в другом векторе без вложенных циклов
У меня есть фрагмент кода, который я перевожу с Fortran на C ++, и я хотел бы избежать некоторых вложенных структур циклов, которые мне пришлось создавать в исходном коде F77.
Проблема заключается в следующем: у меня есть вектор объектов, называемых узлами, каждый из которых включает в себя вектор, содержащий (среди другой важной информации) индексы других узловых объектов, с которыми каждый связан (граф соединений). Как это
struct Node {
vector<int> conNode;
};
vector<Node> listOfNodes;
vector<int> nodeListA; // a subset of nodes of interest stored as their vector indices
Мне нужно искать узлы, к которым подключены узлы в nodeListA, но только если эти узлы также находятся в nodeListA. Прямо сейчас мой код выглядит примерно так:
// Loop over the subset of node indices
for (int i=0; i<nodeListA.size(); i++) {
// Loop over the nodes connected to the node i
for (int j=0; j<listOfNodes[nodeListA[i]].conNode.size(); j++) {
// Loop over the subset of node indices again
for (int k=0; k<nodeListA.size(); k++) {
// and determine if any of node i's connections are in the subset list
if (nodeListA[k] == listOfNodes[nodeListA[i]].conNode[j]) {
// do stuff here
}
}
}
}
Должен быть намного более простой способ сделать это. Кажется, я делаю этот путь слишком сложным. Как я могу упростить этот код, возможно, используя стандартную библиотеку алгоритмов?
Решение
Если ваша переменная должна выражать набор значений, используйте std::set вместо std::vector, Тогда у вас будет
typedef std::set<int> SetOfIndices;
SetOfIndices setOfIndices; // instead of nodeListA
for(SetOfIndices::const_iterator iter = setOfIndices.begin(); iter != setOfIndices.end(); ++iter)
{
Node const & node = listOfNodes[*iter];
for (int j = 0; j < node.conNode.size(); ++j)
{
if (setOfIndices.find(node.conNode[j]) != setOfIndices.end())
{
// do stuff here
}
}
}
РЕДАКТИРОВАТЬ
Как предполагает Джерри Коффин, std::set_intersection можно использовать во внешнем цикле:
struct Node {
SetOfIndices conNode;
}
typedef std::set<int> SetOfIndices;
SetOfIndices setOfIndices; // instead of nodeListA
for(SetOfIndices::const_iterator iter = setOfIndices.begin(); iter != setOfIndices.end(); ++iter)
{
Node const & node = listOfNodes[*iter];
std::vector<int> interestingNodes;
std::set_intersection(setOfIndices.begin(), setOfIndices.end(),
node.conNode.begin(), node.conNode.end(),
std::back_inserter(interestingNodes));
for (int j = 0; j < interestingNodes.size(); ++j)
{
// do stuff here
}
}
ДРУГОЕ РЕДАКТИРОВАНИЕ
Об эффективности — это зависит от того, что является доминирующей операцией. Количество исполнений части, описанной как «делать вещи здесь», не будет меняться. Разница во времени обхода ваших коллекций:
- Ваш оригинальный код — nodeListA.size () ^ 2 * [средний размер conNode]
- Мое первое решение — nodeListA.size () * log (nodeListA.size ()) * [средний размер conNode]
- После предложения Джерри Гроба — nodeListA.size () ^ 2 * [среднее количество интересных элементов conNode]
Так что кажется, что set_intersection использование не помогает в этом случае.
Другие решения
Я бы предложил использовать словарь (O (log n), например std::setили лучше на хэш std::unordered_set из C ++ 11) для nodeListA, Ниже приведен пример кода C ++ 11.
#include <unordered_set>
#include <vector>
struct Node {
std::vector<int> conNode;
};
int main()
{
std::vector<Node> listOfNodes;
std::unordered_set<int> nodeListA;
for (int node_id : nodeListA)
for (int connected_id : listOfNodes[node_id].conNode)
if (nodeListA.find(connected_id) != end(nodeListA))
/* Do stuff here.. */
;
return 0;
}
Преимущество использования std::unordered_set в том, что поиск (то есть поиск заданного идентификатора узла) чрезвычайно быстр. Однако реализация, включенная в стандартную библиотеку, может быть не очень быстрой. Реализация разреженного и плотного хеширования Google является альтернативой, которая обеспечивает такой же интерфейс и, как известно, очень хороша для большинства целей: http://code.google.com/p/sparsehash/
В зависимости от того, что вы хотите сделать с результирующими узлами, может оказаться возможным заменить внутренний цикл вышеприведенного кода алгоритмом STL. Например, если вы хотите поместить все узлы, идентифицированные алгоритмом, в вектор, вы можете кодировать его следующим образом (используйте это как замену для обоих циклов вместе):
std::vector<int> results;
for (int node_id : nodeListA)
std::copy_if(begin(listOfNodes[node_id].conNode),
end(listOfNodes[node_id].conNode),
back_inserter(results),
[&nodeListA](int id){return nodeListA.find(id) != end(nodeListA);});
Опять же, это синтаксис C ++ 11; он использует лямбду в качестве аргумента функции.