Самый быстрый способ вычислить количество общих элементов между двумя векторами
Предположим, у меня есть два вектора одного размера vector< pair<float, NodeDataID> > v1, v2; Я хочу вычислить, сколько элементов из v1 и v2 имеют один и тот же NodeDataID. Например, если v1 = {<3.7, 22>, <2.22, 64>, <1.9, 29>, <0.8, 7>}, а также v2 = {<1.66, 7>, <0.03, 9>, <5.65, 64>, <4.9, 11>}тогда я хочу вернуться 2 потому что есть два элемента из v1 и v2, которые имеют одинаковые идентификаторы NodeDataID: 7 и 64.
Какой самый быстрый способ сделать это в C ++?
Просто для информации, обратите внимание, что тип NodeDataIDs определяется как я использую повышение как:
typedef adjacency_list<setS, setS, undirectedS, NodeData, EdgeData> myGraph;
typedef myGraph::vertex_descriptor NodeDataID;
Но это не важно, так как мы можем сравнить два NodeDataID с помощью оператора == (то есть можно сделать v1[i].second == v2[j].second)
Решение
Поместите элементы первого вектора в хеш-таблицу. Выполните итерацию по второму вектору, проверяя каждый элемент, находится ли он в хеш-таблице.
Хеш-таблица имеет то преимущество, что вставка и поиск могут выполняться за постоянное время. Это значит, что найти пересечение можно за линейное время. Это оптимально, потому что независимо от алгоритма, вы должны смотреть на каждый элемент вектора хотя бы один раз.
Boost имеет повышение :: навязчивый :: Hashtable, но это (как следует из названия), навязчиво.
Другие решения
Самое простое решение — просто поместить элементы первого вектора в набор, затем для второго вектора мы вставляем каждый элемент в этот набор (ret = myset.insert (an_id)), и если ret.second равен false, то элемент существует, таким образом мы увеличиваем счетчик.
set<NodeDataID> myset;
int counter = 0;
for(int i = 0; i < v1.size(); ++i)
myset.insert(v1[i].second);
for(int i = 0; i < v2.size(); ++i)
{
pair<set<NodeDataID>::iterator,bool> ret = myset.insert(v2[i].second);
if(ret.second == false)
++counter;
}