我有一个包含 vector vector 的数据结构,每个 vector 由大约 ~16000000 个 double 值组成。
我现在想对这些 vector 进行中值组合,也就是说,我在第 i 个位置取值的每个原始 vector ,计算这些 vector 的中值,然后将它们存储在第 i 个位置的结果 vector 中。
我已经有了直接的解决方案,但速度太慢了:
vector< vector<double> > vectors; //vectors contains the datavectors
vector<double> tmp;
vector<double> result;
vector<double> tmpmedian;
double pixels = 0.0;
double matrixcount = vectors.size();
tmp = vectors.at(0);
pixels = tmp.size();
for (int i = 0; i < pixels; i++) {
for (int j = 0; j < matrixcount; j++) {
tmp = vectors.at(j);
tmpmedian.push_back(tmp.at(i));
}
result.push_back(medianOfVector(tmpmedian));
tmpmedian.clear();
}
return result;
medianOfVector 看起来像这样:
double result = 0;
if ((vec.size() % 2) != 0) {
vector<double>::iterator i = vec.begin();
vector<double>::size_type m = (vec.size() / 2);
nth_element(i, i + m, vec.end());
result = vec.at(m);
} else {
vector<double>::iterator i = vec.begin();
vector<double>::size_type m = (vec.size() / 2) - 1;
nth_element(i, i + m, vec.end());
result = (vec.at(m) + vec.at(m + 1)) / 2;
}
return result;
我有一种算法或方法可以更快地完成此操作,但几乎要花很长时间才能完成。
编辑:感谢您的回复,以防万一有人对这里的固定版本感兴趣,它现在需要大约 9 秒才能将三个 vector 与约 16000000 个元素组合在一起,平均组合需要大约 3 秒:
vector< vector<double> > vectors; //vectors contains the datavectors
vector<double> *tmp;
vector<double> result;
vector<double> tmpmedian;
tmp = &vectors.at(0);
int size = tmp->size();
int vectorsize = vectors.size();
for (int i = 0; i < size; i++) {
for (int j = 0; j < vectorsize; j++) {
tmp = &vectors.at(j);
tmpmedian.push_back(tmp->at(i));
}
result.push_back(medianOfVector(tmpmedian));
tmpmedian.clear();
}
return result;
和 medianOfVector:
double result = 0;
if ((vec.size() % 2) != 0) {
vector<double>::iterator i = vec.begin();
vector<double>::size_type m = (vec.size() / 2);
nth_element(i, i + m, vec.end());
result = vec.at(m);
} else {
vector<double>::iterator i = vec.begin();
vector<double>::size_type m = (int) (((vec.size() - 1) / 2));
nth_element(i, i + m, vec.end());
double min = vec.at(m);
double max = *min_element(i + m + 1, vec.end());
result = (min + max) / 2;
}
return result;
}
最佳答案
有几点,都源于您定义了 tmp
。作为 vector 而不是(例如)引用。
vector<double> tmp;
tmp = vectors.at(0);
pixels = tmp.size();
在这里您复制了整个 vectors[0]
进入tmp
只是为了提取大小。通过避免复制,您几乎肯定会获得一些速度:
pixels = vectors.at(0).size();
这不是为了获取其大小而复制整个 vector ,而是获取第一个 vector 的引用,并获取该现有 vector 的大小。
for (int i = 0; i < pixels; i++) {
for (int j = 0; j < matrixcount; j++) {
tmp = vectors.at(j);
tmpmedian.push_back(tmp.at(i));
}
在这里您再次复制整个 vectors.at(j)
进入tmp
.但是(再次强调)您实际上并不需要所有数据的新拷贝——您只是从该拷贝中检索单个项目。您可以直接从原始 vector 中检索所需的数据,而无需复制整个内容:
tmpmedian.push_back(vectors.at(j).at(i));
下一步可能是不再使用 .at
至 operator[]
:
tmpmedian.push_back(vectors[j][i]);
虽然这更像是一种权衡——它不太可能获得那么多,并且在此过程中失去了一点安全性(范围检查)。为避免失去安全性,您可以考虑(例如)使用基于范围的 for
循环而不是计数 for
在您当前的代码中循环。
沿着相当不同的路线,您可以改为使用 vector<vector<double>>
在 vector 周围使用小包装器将 2D 寻址到单个 vector 中。将其与合适的按列迭代器一起使用,您可以避免创建 tmpmedian
基本上作为原始二维矩阵的一列的拷贝——相反,您将按列迭代器传递给 medianOfVector
, 并就地迭代原始数据的一列。
关于c++ - double的多个 vector 的中位数(c++, vector < vector<double>>),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26636455/