sco*_*doo 5 c++ arrays algorithm loops matching
我目前有一个解决方案,但我觉得它不像这个问题那样有效,所以我想看看是否有更快的方法.
我有两个数组(例如std :: vectors).两个数组只包含排序但值稀疏的唯一整数值,即:1,4,12,13 ......我想问的是有什么快速的方法可以找到INDEX到其中一个值的数组是相同的.例如,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
}
结果将是array1 = [1,3]和array2 = [2,3]的匹配索引
我使用一种算法编写了该函数的实现，该算法在稀疏分布上比简单的线性合并表现更好。
\n\n对于发行版，类似于\xe2\x80\xa0的分布，它具有 O(n) 复杂度，但在分布差异很大的范围内，它的性能应低于线性，在最佳情况下接近 O(log n)。然而，我无法证明最坏情况并不比 O(n log n) 更好。另一方面，我也未能找到最坏的情况。
\n\n我对其进行了模板化，以便可以使用任何类型的范围，例如子范围或原始数组。从技术上讲，它也适用于非随机访问迭代器，但复杂性要高得多，因此不推荐。我认为在这种情况下应该可以修改算法以回退到线性搜索，但我没有打扰。
\n\n\xe2\x80\xa0通过类似的分布，我的意思是这对数组有很多交叉点。通过穿越，我的意思是如果您要将两个数组按排序顺序合并在一起，您将从一个数组切换到另一个数组。
\n\n#include <algorithm>\n#include <iterator>\n#include <utility>\n\n// helper structure for the search\ntemplate<class Range, class Out>\nstruct search_data {\n // is any there clearer way to get iterator that might be either\n // a Range::const_iterator or const T*?\n using iterator = decltype(std::cbegin(std::declval<Range&>()));\n iterator curr;\n const iterator begin, end;\n Out out;\n};\n\ntemplate<class Range, class Out>\nauto init_search_data(const Range& range, Out out) {\n return search_data<Range, Out>{\n std::begin(range),\n std::begin(range),\n std::end(range),\n out,\n };\n}\n\ntemplate<class Range, class Out1, class Out2>\nvoid match_indices(const Range& in1, const Range& in2, Out1 out1, Out2 out2) {\n auto search_data1 = init_search_data(in1, out1);\n auto search_data2 = init_search_data(in2, out2);\n\n // initial order is arbitrary\n auto lesser = &search_data1;\n auto greater = &search_data2;\n\n // if either range is exhausted, we are finished\n while(lesser->curr != lesser->end\n && greater->curr != greater->end) {\n // difference of first values in each range\n auto delta = *greater->curr - *lesser->curr;\n\n if(!delta) { // matching value was found\n // store both results and increment the iterators\n *lesser->out++ = std::distance(lesser->begin, lesser->curr++);\n *greater->out++ = std::distance(greater->begin, greater->curr++);\n continue; // then start a new iteraton\n }\n\n if(delta < 0) { // set the order of ranges by their first value\n std::swap(lesser, greater);\n delta = -delta; // delta is always positive after this\n }\n\n // next crossing cannot be farther than the delta\n // this assumption has following pre-requisites: \n // range is sorted, values are integers, values in the range are unique\n auto range_left = std::distance(lesser->curr, lesser->end);\n auto upper_limit =\n std::min(range_left, static_cast<decltype(range_left)>(delta));\n\n // exponential search for a sub range where the value at upper bound\n // is greater than target, and value at lower bound is lesser\n auto target = *greater->curr;\n auto lower = lesser->curr;\n auto upper = std::next(lower, upper_limit);\n for(int i = 1; i < upper_limit; i *= 2) {\n auto guess = std::next(lower, i);\n if(*guess >= target) {\n upper = guess;\n break;\n }\n lower = guess;\n }\n\n // skip all values in lesser,\n // that are less than the least value in greater\n lesser->curr = std::lower_bound(lower, upper, target);\n }\n}\n\n#include <iostream>\n#include <vector>\n\nint main() {\n std::vector<int> array1 = {4,6,12,34};\n std::vector<int> array2 = {1,3,6,34};\n\n std::vector<std::size_t> indices1;\n std::vector<std::size_t> indices2;\n\n match_indices(array1, array2,\n std::back_inserter(indices1),\n std::back_inserter(indices2));\n\n std::cout << "indices in array1: ";\n for(std::vector<int>::size_type i : indices1)\n std::cout << i << \' \';\n\n std::cout << "\\nindices in array2: ";\n for(std::vector<int>::size_type i : indices2)\n std::cout << i << \' \';\n std::cout << std::endl;\n}\n