c++ - 使用 C++ 在两个排序数组中查找匹配值索引的最有效方法

Question

我目前有一个解决方案，但我觉得它对这个问题的效率不高，所以我想看看是否有更快的方法。

我有两个数组(例如 std::vectors)。这两个数组只包含唯一的整数值，这些整数值已排序但值稀疏，即:1,4,12,13 ...我想问的是有没有快速的方法可以找到其中一个数组的索引是相同的。例如，array1 的值为 1、4、12、13，array2 的值​​为 2、12、14、16。第一个匹配值索引是 array2 中的 1。数组中的索引很重要，因为我有其他数组包含将使用“匹配”索引的数据。

我并不局限于使用数组，映射也是可以的。我只比较这两个数组一次。在第一次匹配通过后，它们将不会被再次使用。任一数组中的值数量可以从小到大(300,000+)，但不要总是具有相同数量的值(这会使事情变得容易得多)

最坏的情况是线性搜索 O(N^2)。使用 map 会使我的 O(log N) 更好，但我仍然会将数组转换为值、索引对的映射。

我目前必须不做任何容器类型转换的是这个。遍历两个数组中较小的一个。将小数组 (array1) 的当前元素与大数组 (array2) 的当前元素进行比较。如果 array1 元素值大于 array2 元素值，则增加 array2 的索引，直到它不再大于 array1 元素值(while 循环)。然后，如果 array1 元素值小于 array2 元素，则转到下一个循环迭代并重新开始。否则它们必须相等，并且我有匹配值数组的索引。

所以在这个循环中，如果所有值都匹配，我最多 O(N)，如果没有匹配，则更糟 O(2N)。所以我想知道那里是否有更快的东西？很难确定这两个数组匹配的频率，但我会更倾向于大多数数组大多匹配而不是不匹配。

我希望我已经足够好地解释了这个问题，我很感激任何关于改进这个问题的反馈或提示。

代码示例:

std::vector<int> array1 = {4,6,12,34};
std::vector<int> array2 = {1,3,6,34,40};

for(unsigned int i=0, z=0; i < array1.size(); i++) 
{
    int value1 = array1[i];
    while(value1 > array2[z] && z < array2.size())
        z++;

    if (z >= array2.size())
        break; // reached end of array2

    if (value1 < array2[z])
        continue;

    // we have a match, i and z indices have same value

}

结果将匹配数组 1 = [1,3] 和数组 2 = [2,3] 的索引

Answer 1

我使用一种算法编写了此函数的实现，该算法在稀疏分布下的表现优于平凡的线性合并。

对于相似的分布^†，它具有 O(n) 的复杂度，但在分布差异很大的范围内，它应该低于线性，在最佳情况下接近 O(log n)。但是，我无法证明最坏的情况并不比 O(n log n) 好。另一方面，我也没能找到最坏的情况。

我对其进行了模板化，以便可以使用任何类型的范围，例如子范围或原始数组。从技术上讲，它也适用于非随机访问迭代器，但复杂性要大得多，因此不推荐使用。我认为在这种情况下应该可以修改算法以回退到线性搜索，但我没有费心。

^† 相似 分布是指这对数组有很多交叉点。通过交叉，我的意思是如果您要按排序顺序将两个数组合并在一起，您会从一个数组切换到另一个数组。

#include <algorithm>
#include <iterator>
#include <utility>

// helper structure for the search
template<class Range, class Out>
struct search_data {
    // is any there clearer way to get iterator that might be either
    // a Range::const_iterator or const T*?
    using iterator = decltype(std::cbegin(std::declval<Range&>()));
    iterator curr;
    const iterator begin, end;
    Out out;
};

template<class Range, class Out>
auto init_search_data(const Range& range, Out out) {
    return search_data<Range, Out>{
        std::begin(range),
        std::begin(range),
        std::end(range),
        out,
    };
}

template<class Range, class Out1, class Out2>
void match_indices(const Range& in1, const Range& in2, Out1 out1, Out2 out2) {
    auto search_data1 = init_search_data(in1, out1);
    auto search_data2 = init_search_data(in2, out2);

    // initial order is arbitrary
    auto lesser = &search_data1;
    auto greater = &search_data2;

    // if either range is exhausted, we are finished
    while(lesser->curr != lesser->end
            && greater->curr != greater->end) {
        // difference of first values in each range
        auto delta = *greater->curr - *lesser->curr;

        if(!delta) { // matching value was found
            // store both results and increment the iterators
            *lesser->out++ = std::distance(lesser->begin, lesser->curr++);
            *greater->out++ = std::distance(greater->begin, greater->curr++);
            continue; // then start a new iteraton
        }

        if(delta < 0) { // set the order of ranges by their first value
            std::swap(lesser, greater);
            delta = -delta; // delta is always positive after this
        }

        // next crossing cannot be farther than the delta
        // this assumption has following pre-requisites: 
        // range is sorted, values are integers, values in the range are unique
        auto range_left = std::distance(lesser->curr, lesser->end);
        auto upper_limit =
            std::min(range_left, static_cast<decltype(range_left)>(delta));

        // exponential search for a sub range where the value at upper bound
        // is greater than target, and value at lower bound is lesser
        auto target = *greater->curr;
        auto lower = lesser->curr;
        auto upper = std::next(lower, upper_limit);
        for(int i = 1; i < upper_limit; i *= 2) {
            auto guess = std::next(lower, i);
            if(*guess >= target) {
                upper = guess;
                break;
            }
            lower = guess;
        }

        // skip all values in lesser,
        // that are less than the least value in greater
        lesser->curr = std::lower_bound(lower, upper, target);
    }
}

#include <iostream>
#include <vector>

int main() {
    std::vector<int> array1 = {4,6,12,34};
    std::vector<int> array2 = {1,3,6,34};

    std::vector<std::size_t> indices1;
    std::vector<std::size_t> indices2;

    match_indices(array1, array2,
                  std::back_inserter(indices1),
                  std::back_inserter(indices2));

    std::cout << "indices in array1: ";
    for(std::vector<int>::size_type i : indices1)
        std::cout << i << ' ';

    std::cout << "\nindices in array2: ";
    for(std::vector<int>::size_type i : indices2)
        std::cout << i << ' ';
    std::cout << std::endl;
}