I have a distance matrix
D
of sizen
byn
and a constantL
as input. I need to create a vectorv
contains all entries inD
such that its value is at mostL
. Herev
must be in a specific orderv = [v1 v2 .. vn]
wherevi
contains entries ini
th row ofD
with value at mostL
. The order of entries in eachvi
is not important.
我想知道是否有一种使用 vector 、数组或任何数据结构 + 并行化来创建 v
的快速方法。我所做的是使用 for 循环,它对于大的 n
非常慢。
vector<int> v;
for (int i=0; i < n; ++i){
for (int j=0; j < n; ++j){
if (D(i,j) <= L) v.push_back(j);
}
}
最佳答案
最好的方法主要取决于上下文。如果您正在寻求 GPU 并行化,您应该看看 OpenCL。
对于基于 CPU 的并行化,C++ 标准 #include <thread>
图书馆可能是你最好的选择,但你需要小心:
- 创建线程需要时间,所以如果 n 相对较小(<1000 左右)它会减慢你的速度
- D(i,j) 必须同时被多个线程读取
- v 必须可由多个线程写入,标准 vector 不会削减它
v 可能是一个二维 vector ,vi 作为它的子 vector ,但是这些必须在并行化之前初始化:
std::vector<std::vector<int>> v;
v.reserve(n);
for(size_t i = 0; i < n; i++)
{
v.push_back(std::vector<int>());
}
您需要决定要使用多少个线程。如果这仅适用于一台机器,硬编码是一个有效的选项。线程库中有一个函数可以获取支持的线程数量,但它更多的是提示而不是可信。
size_t threadAmount = std::thread::hardware_concurrency(); //How many threads should run hardware_concurrency() gives you a hint, but its not optimal
std::vector<std::thread> t; //to store the threads in
t.reserve(threadAmount-1); //you need threadAmount-1 extra threads (we already have the main-thread)
要启动一个线程,您需要一个它可以执行的函数。在这种情况下,这是读取矩阵的一部分。
void CheckPart(size_t start, size_t amount, int L, std::vector<std::vector<int>>& vec)
{
for(size_t i = start; i < amount+start; i++)
{
for(size_t j = 0; j < n; j++)
{
if(D(i,j) <= L)
{
vec[i].push_back(j);
}
}
}
}
现在您需要将矩阵分成大约 n/threadAmount 行的部分并启动线程。线程构造函数需要一个函数及其参数,但它总是会尝试复制参数,即使函数需要一个引用。为防止这种情况,您需要强制使用 std::ref()
的引用
int i = 0;
int rows;
for(size_t a = 0; a < threadAmount-1; a++)
{
rows = n/threadAmount + ((n%threadAmount>a)?1:0);
t.push_back(std::thread(CheckPart, i, rows, L, std::ref(v)));
i += rows;
}
线程现在正在运行,所有要做的就是运行主函数的最后一个 block :
SortPart(i, n/threadAmount, L, v);
之后您需要等待线程完成并清理它们:
for(unsigned int a = 0; a < threadAmount-1; a++)
{
if(t[a].joinable())
{
t[a].join();
}
}
请注意,这只是一个简单粗暴的示例。不同的问题可能需要不同的实现,而且由于我无法猜测上下文,我能提供的帮助是相当有限的。
关于c++ - 在 C++ 中从距离矩阵创建索引 vector 的最快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58332193/