C++根据参考计算中位数
C++ calculate median with reference
我尝试计算一个名为 median
:
的向量的中位数
std::nth_element(median.begin(), median.begin() + median.size() / 2, median.end());
medianVal = median[median.size() / 2];
cout << "The median is " << medianVal << endl;
这很好用。但我需要得到中值在其原始向量中的位置。我怎样才能非常快地做到这一点?
根据文档 (http://en.cppreference.com/w/cpp/algorithm/nth_element),您使用的函数实际上将对数组进行部分重新排序。
您需要保留原件的副本并逐一检查它以找到与中位数匹配的元素。
完成它的另一种方法是拥有一个元组向量,其中索引简单地存储为元组的第二个成员。当然,如果您在某个时候仍然要单步执行向量。
我假设您不想重新订购原始容器。如果错了,还有更简单的方法。
nth_element
取一个比较器。
因此,首先在原始容器中创建一个迭代器向量,然后编写一个接受 2 个迭代器的比较器,引用它们,amd 比较结果。
template<class C>
auto median(C const& c){
using std::begin; using std::end;
auto start = begin(c);
auto finish = end(c);
using iterator = decltype(start);
std::vector<iterator> working;
for(auto it = start; it != finish; ++it)
working.push_back(it);
if (working.empty())
return start;
std::nth_element(
begin(working), begin(working) + working.size() / 2, end(working),
[](iterator lhs, iterator rhs){
return *lhs < *rhs;
}
);
return *(begin(working) + working.size() / 2);
}
这确实依赖于一些 C++14(自动 return 类型推导),但每个主要编译器(可能除了 icc?)现在都支持它。
它足够灵活,甚至可以在 C 风格的数组上工作,我认为它甚至可以与哨兵一起工作。
如果不知道问题的确切性质或涉及的数据系列中的元素数量,很难知道 "do this very fast" 是什么意思,但是您可能想看看 "heap median" 又名 "rolling median" 又名 "streaming median" 算法在 SO 站点中描述 here, here, here and here。
通过这种方法,可以存储当前候选中值的索引,而无需再次遍历原始数据数组来找到中位数的索引。您也不需要修改原始容器的顺序。
我尝试计算一个名为 median
:
std::nth_element(median.begin(), median.begin() + median.size() / 2, median.end());
medianVal = median[median.size() / 2];
cout << "The median is " << medianVal << endl;
这很好用。但我需要得到中值在其原始向量中的位置。我怎样才能非常快地做到这一点?
根据文档 (http://en.cppreference.com/w/cpp/algorithm/nth_element),您使用的函数实际上将对数组进行部分重新排序。
您需要保留原件的副本并逐一检查它以找到与中位数匹配的元素。
完成它的另一种方法是拥有一个元组向量,其中索引简单地存储为元组的第二个成员。当然,如果您在某个时候仍然要单步执行向量。
我假设您不想重新订购原始容器。如果错了,还有更简单的方法。
nth_element
取一个比较器。
因此,首先在原始容器中创建一个迭代器向量,然后编写一个接受 2 个迭代器的比较器,引用它们,amd 比较结果。
template<class C>
auto median(C const& c){
using std::begin; using std::end;
auto start = begin(c);
auto finish = end(c);
using iterator = decltype(start);
std::vector<iterator> working;
for(auto it = start; it != finish; ++it)
working.push_back(it);
if (working.empty())
return start;
std::nth_element(
begin(working), begin(working) + working.size() / 2, end(working),
[](iterator lhs, iterator rhs){
return *lhs < *rhs;
}
);
return *(begin(working) + working.size() / 2);
}
这确实依赖于一些 C++14(自动 return 类型推导),但每个主要编译器(可能除了 icc?)现在都支持它。
它足够灵活,甚至可以在 C 风格的数组上工作,我认为它甚至可以与哨兵一起工作。
如果不知道问题的确切性质或涉及的数据系列中的元素数量,很难知道 "do this very fast" 是什么意思,但是您可能想看看 "heap median" 又名 "rolling median" 又名 "streaming median" 算法在 SO 站点中描述 here, here, here and here。
通过这种方法,可以存储当前候选中值的索引,而无需再次遍历原始数据数组来找到中位数的索引。您也不需要修改原始容器的顺序。