高效计算两个向量公共元素的索引

Compute indices of two vectors' common elements efficiently

我有两个共享一组整数的向量(每个向量都只有唯一的元素)。我想尽可能高效地计算一个向量中也存在于另一个向量中的元素的索引。你能胜过我拙劣的低效实施吗?

编辑: 向量未排序,我们需要未排序向量的索引。此外,解题时禁止修改初始向量(random_vec_1random_vec_2

#include <chrono>
#include <iostream>
#include <random>
#include <set>
#include <unordered_set>
#include <vector>

using namespace std::chrono;

int main() {

    // Setup 1: Construct two vectors with random integers.
    constexpr size_t num = 1000;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, num);

    std::vector<int> random_vec_1;
    std::vector<int> random_vec_2;
    random_vec_1.reserve(num);
    random_vec_2.reserve(num);
    for (size_t i = 0u; i < num; ++i) {
        random_vec_1.push_back(dis(gen));
        random_vec_2.push_back(dis(gen));
    }
    // Setup 2: Make elements unique and shuffle them.
    std::set<int> s1(random_vec_1.begin(), random_vec_1.end());
    std::set<int> s2(random_vec_2.begin(), random_vec_2.end());
    random_vec_1.assign(s1.begin(), s1.end());
    random_vec_2.assign(s2.begin(), s2.end());
    std::random_shuffle(random_vec_1.begin(), random_vec_1.end());
    std::random_shuffle(random_vec_2.begin(), random_vec_2.end());


    std::cout << "size random_vec_1: " << random_vec_1.size() << "\n";
    std::cout << "size random_vec_2: " << random_vec_2.size() << "\n";

    auto begin1 = high_resolution_clock::now();

    // Solve problem -------------------------------------------
    std::vector<size_t> match_index_2;
    std::unordered_set<int> my_set(random_vec_1.begin(), random_vec_1.end());
    for (size_t i = 0u; i < random_vec_2.size(); ++i) {
        if (my_set.count(random_vec_2[i]) == 1u)
            match_index_2.push_back(i);
    }
    // ---------------------------------------------------------

    auto end1 = high_resolution_clock::now();
    auto ticks1 = duration_cast<microseconds>(end1-begin1);
    std::cout << "Set approach took " << ticks1.count() << " microseconds.\n";
    std::cout << "Number of common indices: " << match_index_2.size() << "\n";

}

vector 现在太快了,我不会用 set:

  1. 将第一个矢量复制到例如new_vector_1;
  2. 排序new_vector_1;
  3. 使用 binary_searchnew_vector_1 中查找值。

代码:

std::vector<int> new_vec_1(random_vec_1);
std::sort(std::begin(new_vec_1), std::end(new_vec_1));
std::vector<size_t> match_index_2;
match_index_2.reserve(random_vec_2.size());

for (size_t i = 0; i < random_vec_2.size(); ++i) {
    if (std::binary_search(std::begin(new_vec_1), 
                           std::end(new_vec_1),
                           random_vec_2[i])) {
        match_index_2.push_back(i);
    }
}

查看 ideone 上的代码 - 代码速度是 set 版本的两倍,我认为它可能会进一步优化。

请注意,此代码在算法上与您的代码相同,但 std::vector 速度如此之快,您可以获得更好的性能。


这是另一种对两个向量进行排序的方法(但速度更快):

std::vector<int> new_vec_1(random_vec_1);
std::vector<int> new_vec_2(random_vec_2);
std::sort(std::begin(new_vec_1), std::end(new_vec_1));
std::sort(std::begin(new_vec_2), std::end(new_vec_2));
std::vector<size_t> match_index_2;
match_index_2.reserve(random_vec_2.size());

for (auto it1 = new_vec_1.begin(), it2 = new_vec_2.begin();
     it1 != new_vec_1.end() && it2 != new_vec_2.end();
     ++it2) {
    while (it1 != new_vec_1.end() && *it1 < *it2) ++it1;
    if (it1 != new_vec_1.end() && *it1 == *it2) {
        match_index_2.push_back(it2 - new_vec_2.begin());
    }
}

实际上,我希望对向量进行排序,从而大大优于 std::set 的创建,因为 STL 集是一棵树,vectorint 可以是使用计数排序在线性时间内排序,如果你不计算超过一个,就会给你一个集合。对于成本 log n 的 n 次插入,创建集合的复杂度为 O(n log n),而排序为 O(n),如前所述。

在排序后的向量上,您可以 运行 std::set_difference,这也应该 运行 在时间上与两个输入中较大的一个成线性关系。

因此您应该能够在线性时间内完成此操作。

如果您无法修改向量,您可以使用哈希映射 (std::unordered_map) 将值映射到原始向量中的索引。请注意,由于您没有提到数字是唯一的,您会发现两个集合中都包含值 x_1、...、x_n 等结果,然后您将使用地图来使用哈希图将其投影回原始向量中的索引。

新答案

新的要求是在计算解时不能修改原始向量。由于索引混淆,排序交集解决方案不再有效。

这是我的建议:使用 unordered_map 将第一个向量值映射到相应的索引,然后 运行 通过第二个向量值。

// Not necessary, might increase performance
match_index_2.reserve(std::min(random_vec_1.size(), random_vec_2.size()));

std::unordered_map<int, int> index_map;
// random_vec_2 is the one from which we want the indices.
index_map.reserve(random_vec_2.size());
for (std::size_t i = 0; i < random_vec_2.size(); ++i) {
    index_map.emplace(random_vec_2[i], i);
}

for (auto& it : random_vec_1) {
    auto found_it = index_map.find(it);
    if (found_it != index_map.end()) {
        match_index_2.push_back(found_it->second);
    }
}

此外,如果向量中的值在相对较小的范围内(这是 user2079303 问你的),你可以用向量替换地图,这可能会进一步提高性能。在下文中,我假设这些值在 [0, num].

范围内
match_index_2.reserve(std::min(random_vec_1.size(), random_vec_2.size()));

constexpr std::size_t unmapped = -1; // -1 or another unused index
// Since std::size_t is an unsigned type, -1 will actually be the maximum value it can hold.

std::vector<std::size_t> index_map(num, unmapped);
for (std::size_t i = 0; i < random_vec_2.size(); ++i) {
    index_map[random_vec_2[i]] = i;
}

for (auto& it : random_vec_1) {
    auto index = index_map[it];
    if (index != unmapped) {
        match_index_2.push_back(index);
    }
}

上一个回答

因为你的向量已经排序(在使用 std::set 来保持唯一元素之后),你可以使用这个算法:

auto first1 = random_vec_1.begin();
auto last1 = random_vec_1.end();
auto first2 = random_vec_2.begin();
auto last2 = random_vec_2.end();
auto index_offset = first1; // Put first2 if you want the indices of the second vector instead

while (first1 != last1 && first2 != last2)
    if (*first1 < *first2)
        ++first1;
    else if (*first2 < *first1)
        ++first2;
    else {
        match_index_2.push_back(std::distance(index_offset, first1));
        ++first1;
        ++first2;
    }
}

改编自the gcc libstdc++ source code for std::set_intersection

这是另一个版本,改编自 cppreference :

auto first1 = random_vec_1.begin();
auto last1 = random_vec_1.end();
auto first2 = random_vec_2.begin();
auto last2 = random_vec_2.end();
auto index_offset = first1; // Put first2 if you want the indices of the second vector instead

while (first1 != last1 && first2 != last2) {
    if (*first1 < *first2) {
        ++first1;
    } else  {
        if (!(*first2 < *first1)) {
            match_index_2.push_back(std::distance(index_offset, first1++));
        }
        ++first2;
    }
}

如果您想提高效率,请在 match_index_2 之前调用 reserve。此外,您可以使用 std::sortstd::unique 来摆脱集合。

// Setup 2: Make elements unique.
auto first1 = random_vec_1.begin();
auto last1 = random_vec_1.end();
std::sort(first1, last1);
last1 = std::unique(first1, last1);
random_vec_1.erase(last1, random_vec_1.end());

auto first2 = random_vec_2.begin();
auto last2 = random_vec_2.end();
std::sort(first2, last2);
last2 = std::unique(first2, last2);
random_vec_2.erase(last2, random_vec_2.end());

您可以在值集中创建索引并对这些值进行操作:

#include <algorithm>
#include <vector>

inline std::vector<std::size_t>  make_unique_sorted_index(const std::vector<int>& v) {
    std::vector<std::size_t> result(v.size());
    std::iota(result.begin(), result.end(), 0);
    std::sort(result.begin(), result.end(),
        [&v] (std::size_t a, std::size_t b) {
            return v[a] < v[b];
    });
    auto obsolete = std::unique(result.begin(), result.end(),
        [&v] (std::size_t a, std::size_t b) {
            return v[a] == v[b];
    });
    result.erase(obsolete, result.end());
    return result;
}

// Constructs an unordered range of indices [i0, i1, i2, ...iN) into the first set
// for elements that are found uniquely in both sets.
// Note: The sequence [set1[i0], set1[i1], set1[i2], ... set1[iN]) will be sorted.
std::vector<std::size_t>  unordered_set_intersection(
    const std::vector<int>& set1,
    const std::vector<int>& set2)
{
    std::vector<std::size_t> result;
    result.reserve(std::min(set1.size(), set2.size()));
    std::vector<std::size_t> index1 = make_unique_sorted_index(set1);
    std::vector<std::size_t> index2 = make_unique_sorted_index(set2);

    auto i1 = index1.begin();
    auto i2 = index2.begin();
    while(i1 != index1.end() && i2 != index2.end()) {
        if(set1[*i1] < set2[*i2]) ++i1;
        else if(set2[*i2] < set1[*i1]) ++i2;
        else {
            result.push_back(*i1);
            ++i1;
            ++i2;
        }
    }
    result.shrink_to_fit();
    return result;
}

注意:跳过第二个索引并在第二个集合的副本上操作可能会提高性能。

或者,make_unique_sorted_index 可以替换为:

inline std::vector<std::size_t>  make_sorted_index(const std::vector<int>& v) {
    std::vector<std::size_t> result(v.size());
    std::iota(result.begin(), result.end(), 0);
    std::sort(result.begin(), result.end(),
        [&v] (std::size_t a, std::size_t b) {
            return v[a] < v[b];
    });
    return result;
}

无论索引是否唯一,该算法都会产生稳定的结果:

  • 元素排序(结果索引指向)和std::sort一样稳定。
  • 如果索引不唯一,相同元素的个数(结果索引指向)分别是第一组或第二组中相同元素的最小数量。