针对循环C++的优化

Question

我有一个小函数，循环遍历一个向量，找到一个给定的动物并返回它的栖息地。我需要优化它，但我正在做的事情却陷入了死胡同。我突然想到的三件事是size_t，i++，以及我在向量中循环的事实。我读到size_t对于索引较大的数组非常有用。我知道pre-increment比post-increment更好，因为它改变了原始值，而不是创建临时和递增。但是无论如何，编译器通常会优化这个微小的差异。最后，我想的最后一件事是这个向量可能是不排序的，因此性能会下降。我在考虑根据动物的物种变量对向量进行排序，然后可能将其移植到BST中进行搜索，因为时间复杂度将是O(log(n))。下面是我正在使用的代码：

string GetAnimalHabitat(vector<Animal> animals, string species)
{
    for (size_t i = 0; i < animals.size(); i++)
    {
        if (animals[i].species == species)

        {
            return animals[i].habitat;
        }
    }
    return "Animal not within records.";
}

有没有什么我可能遗漏的东西可以改进这个功能？任何建议都是很棒的。谢谢!

Answer 1

在这里，std::map肯定比遍历向量更好：

string GetAnimalHabitat(const map<string, string>& animals, const string& species)
{
    auto search = animals.find(species);
    if (search != animals.end())
        return search->second;
    return string("Animal not within records.");
}

然而，它需要首先构建一个地图。但构建一次就足够了，您只需向其中添加新的密钥对：

map<string, string> build_map(const vector<Animal>& animals)
{
    map<string, string> ret;
    for (const auto& x : animals)
        ret[x.species] = x.habitat;
    return ret;
}

Answer 2

您可以做的一件事是减少调用.size()方法的次数，方法如下：

size_t vectorSize = animals.size();
for (size_t i = 0; i < vectorSize; i++)
{
    if (animals[i].species == species)

    {
        return animals[i].habitat;
    }
}

另一个小问题是将i++更改为++i。这样做的目的是避免每次i递增时都将其值存储在寄存器中。

Answer 3

在较高的级别上，您希望在每次调用此函数时停止制作向量及其所有元素的完整副本。如果需要优化，我假设向量很大，那么为什么不将引用传递给常量向量呢？

其次，另一个问题是向量中有多少元素将与您的输入字符串匹配？如果只有几个，那么扫描整个向量就会加载大量内存，只是为了查看它来确定您不需要它。由于您在第一次匹配后返回，因此可以合理地认为每个物种最多只能有一个，在这种情况下，关联容器更好。

一些对延迟敏感的将数据划分到不同的组中，因此没有必要进行“过滤”。只要看一看你关心的一组东西，然后只处理它们。

另一件需要考虑的事情是，字符串比较比整数比较要慢得多。您可以将物种预先散列到类中，在循环之前散列物种参数，然后比较散列。如果它们相等，则比较字符串以确保它是真正的匹配。

但我猜你的大部分时间都花在复制输入和输出上了。