这个瓶颈会给我带来什么影响？

Question

我刚刚找到了一种优化我的代码算法的方法，将运行时间从50分钟缩短到了15分钟，但是其中有一个部分需要14分钟。这将成为一个更大的模型系统的一部分，所以我不能让它运行太长时间。由于我必须比较我的向量中的所有值，该向量大约有100,000个值（10亿次比较），我想知道是否有一种优化代码的方法。

struct Coor 
{ 
    double x1; double y1; //Coordinate of Node 1
    double x2; double y2; //Coordinate of Node 2
    std::vector<int> C1; //Index of the edges connected to Node 1
    std::vector<int> C2; //Index of the edges connected to Node 2
};

std::vector<Coor> Connection_S(std::vector<Coor> Nodes)
{
    N = Nodes.size();

    for (i = 0; i < N; ++i)
    {
        for (j = 0; j < N; ++j)
        {
            if (i == j)
            { 
                continue; 
            }
            if ( ( Nodes[i].x1 == Nodes[j].x1 && Nodes[i].y1 == Nodes[j].y1 ) ||
                 ( Nodes[i].x1 == Nodes[j].x2 && Nodes[i].y1 == Nodes[j].y2 ) )
            {
                Nodes[i].C1.push_back(j);
            }
            if ( ( Nodes[i].x2 == Nodes[j].x1 && Nodes[i].y2 == Nodes[j].y1 ) ||
                 ( Nodes[i].x2 == Nodes[j].x2 && Nodes[i].y2 == Nodes[j].y2 ) )
            {
                Nodes[i].C2.push_back(j);
            }
        }
    }
    return Nodes;
}

我对C++还比较新，所以不习惯语言能提供的所有可能性和使函数比其他函数更快的区别。

- Dom C.

---

如果已经比较了B:A，那么可以立即通过不再比较A:B来将其减少一半。请注意，您以几何方式遍历整个空间，O(N^2)，需要计算整个平方，但实际上只需要计算其中一半。第二个循环可以使用j<i的条件，这也会去掉i==j的情况。 - tadman

你也可以在x1和x2上索引你的条目到一个std::map中，然后只比较共享同一桶的条目。你的算法非常低效。值得注意的是，你的编译器可能会或可能不会内联删除重复的Noeuds[i]类型调用的代码。每个这样的查找都可能很痛苦。相反，将每个作为变量捕获并引用它们，或检查你的编译器优化标志是否设置正确。 - tadman

@tadman 给出了很好的建议。在我的情况下，我必须像这样设置第二个循环才能正常工作 for (j=(i+1);j<N;++j)。目前我只尝试了一个较小的向量，但是我得到的时间是5.78秒，而不是10.23秒。 - Dom C.

@LightnessRacesinOrbit 我觉得这里没有足够的内容来回答问题，只能给一些提示。 - tadman

我在回答中添加了一个使用排序的示例代码。这将处理 100,000 个元素所需的时间从 55 秒减少到 3 秒。 - astraujums

Answer 1

在下面的示例代码中，函数Connection_S_optimized可以在3秒内处理100000个Coor的数组，而原始代码需要55秒。

以下代码的主要思想是对端点进行排序并将其放入multimap中。节点1坐标和节点2坐标都放在同一个map中，注意它是哪个端点。

然后，通过对相同组的端点进行单次遍历，我们填充每个Coor的C1和C2数组。

请注意，优化版本与x1、y1为同一点的向量的原始版本的工作方式不同。

正如有人指出的那样，比较双精度浮点数是否相等可能会很危险，因此，您可以调整函数is_same_coordinate以进行近似比较。

这段代码似乎可以工作，但当然要自己承担风险。

#include <vector>
#include <map>
#include <algorithm>
#include <time.h>
#include <iostream>

struct Coor
{
    double x1; double y1; //Coordinate of Node 1
    double x2; double y2; //Coordinate of Node 2
    std::vector<int> C1; //Index of the edge connected to Node 1
    std::vector<int> C2; //Index of the edge connected to Node 2
};

bool is_same_coordinate(std::pair<double, double> e1, std::pair<double, double> e2)
{
    return (e1.first == e2.first) && (e1.second == e2.second);
}

std::vector<Coor> Connection_S(std::vector<Coor> Noeuds)
{
    size_t N = Noeuds.size();

    for (size_t i = 0; i < N; ++i)
    {
        for (size_t j = 0; j < N; ++j)
        {
            if (i == j)
            {
                continue;
            }
            if ((Noeuds[i].x1 == Noeuds[j].x1 && Noeuds[i].y1 == Noeuds[j].y1) || (Noeuds[i].x1 == Noeuds[j].x2 && Noeuds[i].y1 == Noeuds[j].y2))
            {
                Noeuds[i].C1.push_back(j);
            }
            if ((Noeuds[i].x2 == Noeuds[j].x1 && Noeuds[i].y2 == Noeuds[j].y1) || (Noeuds[i].x2 == Noeuds[j].x2 && Noeuds[i].y2 == Noeuds[j].y2))
            {
                Noeuds[i].C2.push_back(j);
            }
        }
    }
    return Noeuds;
}


void Connection_S_optimized(std::vector<Coor>& Noeuds)
{
    // A map of an endpoint coordinates to the information about this enpoint <is it the Node 1 (x1, y1), index in Noeuds>
    std::multimap<std::pair<double, double>, std::pair<bool, size_t>> node_index;

    for (size_t i = 0; i < Noeuds.size(); i++)
    {
        Coor& c = Noeuds[i];
        node_index.insert(std::make_pair(std::pair<double, double>(c.x1, c.y1), std::pair<bool, size_t>(true, i)));
        node_index.insert(std::make_pair(std::pair<double, double>(c.x2, c.y2), std::pair<bool, size_t>(false, i)));
    }
    auto s_representative_it = node_index.begin();
    for (auto s_it = node_index.begin();; s_it++)
    {
        if (s_it == node_index.end() || !is_same_coordinate(s_representative_it->first, s_it->first))
        {
            auto start = s_representative_it;
            auto end = s_it;
            auto current = s_representative_it;
            while (current != end)
            {
                bool is_node_1 = current->second.first;
                Coor& current_coor = Noeuds[current->second.second];
                auto it = start;
                while (it != end)
                {
                    if (it != current)
                    {
                        if (is_node_1)
                        {
                            current_coor.C1.push_back(it->second.second);
                        }
                        else
                        {
                            current_coor.C2.push_back(it->second.second);
                        }
                    }
                    it++;
                }
                current++;
            }
            if (s_it == node_index.end())
            {
                break;
            }
            s_representative_it = s_it;
        }
    }
}

const size_t NUM_COORS = 100000;

void generate_sample_set(std::vector<Coor>& Noeuds)
{
    Coor c;
    size_t degenerated = 0;
    for (size_t i = 0; i < NUM_COORS + degenerated; i++)
    {
        c.x1 = i % 23;
        c.x2 = i % 13;
        c.y1 = i % 5;
        c.y2 = i % 17;
        if (is_same_coordinate(std::make_pair(c.x1, c.y1), std::make_pair(c.x2, c.y2)))
        {
            degenerated++;
            continue;
        }
        Noeuds.push_back(Coor(c));
    }
}

int main(int argc, char** argv)
{
    std::vector<Coor> Noeuds_input;

    generate_sample_set(Noeuds_input);

    std::vector<Coor> Noeuds_original = Noeuds_input;
    std::vector<Coor> Noeuds_optimized = Noeuds_input;

    double time_original = clock();
    Noeuds_original = Connection_S(Noeuds_original);
    time_original = (clock() - time_original) / CLOCKS_PER_SEC;

    double time_optimized = clock();
    Connection_S_optimized(Noeuds_optimized);
    time_optimized = (clock() - time_optimized) / CLOCKS_PER_SEC;

    for (size_t i = 0; i < std::min(Noeuds_input.size(), 100u); i++)
    {
        std::cout << i << ": " << Noeuds_original[i].C1.size() << "," << Noeuds_original[i].C2.size()
            << " vs " << Noeuds_optimized[i].C1.size() << "," << Noeuds_optimized[i].C2.size() << std::endl;
    }

    std::cout << "Processing time for " << NUM_COORS << " items (in seconds):" << std::endl;
    std::cout << "  original: " << time_original << std::endl;
    std::cout << " optimized: " << time_optimized << std::endl;

    return 0;
}

- astraujums

---

另一个节省内存的优化方法是不为每个向量都创建C1和C2数组，而是引入一种新类型的对象——顶点——由每个坐标指向，然后指向开始或结束的坐标。目前，根据在一个点相遇的Coors数量，C1和C2数组中存储了大量冗余信息。 - astraujums

Answer 2

编译器优化设置

首先打印出汇编语言列表。
接下来，将优化级别设置为高速；重新编译。
比较优化后的汇编代码和未优化的汇编代码。

预加载变量

通过预加载要比较的值，您可能能够获得一些节省。 （注意：编译器可能已经执行此操作，请检查本地汇编语言以获取真相。）
例如：

const double ni_x1(Nodes[i].x1);
const double ni_x2(Nodes[i].x2);
const double nj_y1(Nodes[i].y1);
const double nj_y2(Nodes[i].y2);

if (((ni_x1 == nj_x1) && (ni_y1 == nj_y1))
// ...

这里的优化技术是允许处理器将数据预取到其数据缓存中。

减少分支指令

分支指令比数据指令需要更长的时间来执行。因此，如果可能的话，请消除它们。 （某些处理器具有足够的缓存，可以将循环加载到指令缓存中而无需重新加载。在任何情况下，处理器仍需要执行一些额外的逻辑，这需要比处理数据指令更长的时间。）

您可以使用布尔代数。再次查看汇编语言，以查看是否获得了任何速度提升。 例如：

bool is_equal = false;
is_equal = (ni_x1 == nj_x1);
is_equal = is_equal && (ni_y1 == nj_y1);

上述内容可能允许编译器生成条件汇编指令，如果您的处理器具有该功能。希望编译器能够生成连续数据指令。

定点算术

另一个选择是使用定点算术。这将允许整数算术运算，通常比浮点运算更快。

例如，给定升数，可能会有3.141升的容积。如果将值表示为毫升，则值将是整数：3141。

优点：更好的准确性和相等性。例如，在32位处理器上，您可以拥有32位的“尾数”，而浮点数可能只有24位的“尾数”，因为某些位用于符号和指数。

- Thomas Matthews

---

这些是不错的建议，但只能做到这一步。无论你如何优化，当数据量增加时，你都无法让冒泡排序胜过堆排序。 - astraujums

Answer 3

你可以在循环之前调整Noeuds[i]向量的大小。这将改善内存管理和性能。通过引用传递结构体 Noeuds。现在正在复制它，这需要时间。 将Connection_S(std::vector<Coor> Noeuds)更改为Connection_S(std::vector<Coor> &Noeuds)。当您通过引用传递时，您不必返回它。原始数据将直接更新。

另外注意：使用==比较double类型的数值并不能总是得到相同的结果，因此这是危险的。

- Satish Chalasani

---

当我尝试通过引用传递我的向量时，它需要多一分钟才能完成。也许我做错了 std::vector<Coor> Connection_B(std::vector<Coor> &Noeuds)？ - Dom C.

你不需要返回相同的内容，可以将返回值更改为void。void Connection_B(std::vector<Coor> &Noeuds)。 - Satish Chalasani

更可能被移动而不是复制。 - Lightness Races in Orbit

Answer 4

你可以做以下几件事情：

1. 预先对整个向量进行排序，这个操作的时间复杂度为O(nlogn)，相比你现在所做的O(N*N)更加高效。然后你可以找到一种更有效的方法来填充C1/C2。
2. 你也可以尝试一次比较多个元素；j会增加2、4等等。这将改善你的缓存局部性，并应该生成更紧凑的代码。

- Pandrei

Answer 5

侧面说明：“Node”的复数形式是“Nodes”;-)

std::vector 内部使用动态分配的数组，这意味着push_back操作，正如这里所解释的那样，可能需要重新分配内存，然后复制向量中已有的所有数据。根据您的向量大小，这可能是一个相当昂贵的操作。

相反，考虑使用其他一些容器。std::list 在添加元素到末尾方面相当高效，但不支持随机访问。或者，您可能想使用std::deque，它不能保证所有元素都在连续的存储器中（像向量一样），但仍然允许相当高效的随机访问。

- Wouter Verhelst

---

我记得以前有一个 std::vector.reserve() 或者类似的东西可能会很有用（但是过去十年里我没有做过太多的 C++，所以我可能错了）。 - Axel

然而，使用std::vector的问题在于您需要事先知道向量的大小。这是不太可能的，当您错误时，您将不得不移动内存。 std :: list和std :: deque不会移动元素，因此这个问题不存在。 - Wouter Verhelst

这是一个很好的建议，但在我的情况下，我很难想象会有超过3个值需要push_back，所以我认为这不会有任何影响。 - Dom C.