c++ - 如何优化我的 C++ 键值程序以获得更快的运行时间？

Question

这是a2.hpp，是可以编辑的程序，据我所知代码是正确的，就是太慢了。老实说，我在这里迷路了，我知道我的 for 循环可能会减慢我的速度，也许使用迭代器？

// <algorithm>, <list>, <vector>
// YOU CAN CHANGE/EDIT ANY CODE IN THIS FILE AS LONG AS SEMANTICS IS UNCHANGED

#include <algorithm>
#include <list>
#include <vector>

class key_value_sequences {

private:
  std::list<std::vector<int>> seq;
  std::vector<std::vector<int>> keyref;

public:
    // YOU SHOULD USE C++ CONTAINERS TO AVOID RAW POINTERS
    // IF YOU DECIDE TO USE POINTERS, MAKE SURE THAT YOU MANAGE MEMORY PROPERLY
    // IMPLEMENT ME: SHOULD RETURN SIZE OF A SEQUENCE FOR GIVEN KEY
    // IF NO SEQUENCE EXISTS FOR A GIVEN KEY RETURN 0
    int size(int key) const;

    // IMPLEMENT ME: SHOULD RETURN POINTER TO A SEQUENCE FOR GIVEN KEY
    // IF NO SEQUENCE EXISTS FOR A GIVEN KEY RETURN nullptr
    const int* data(int key) const;

    // IMPLEMENT ME: INSERT VALUE INTO A SEQUENCE IDENTIFIED BY GIVEN KEY
    void insert(int key, int value);
}; // class key_value_sequences


int key_value_sequences::size(int key) const {
    //checks if the key is invalid or the count vector is empty.
  if(key<0 || keyref[key].empty()) return 0;
    // sub tract 1 because the first element is the key to access the count
  return keyref[key].size() -1;
}

const int* key_value_sequences::data(int key) const {
      //checks if key index or ref vector is invalid
    if(key<0 || keyref.size() < static_cast<unsigned int>(key+1)) {
      return nullptr;
    }
      // ->at(1) accesses the count (skipping the key) with a pointer
    return &keyref[key].at(1);
}

void key_value_sequences::insert(int key, int value) {
      //checks if key is valid and if the count vector needs to be resized
    if(key>=0 && keyref.size() < static_cast<unsigned int>(key+1)) {
      keyref.resize(key+1);
      std::vector<int> val;
      seq.push_back(val);
      seq.back().push_back(key);
      seq.back().push_back(value);
      keyref[key] = seq.back();
    }
      //the index is already valid
    else if(key >=0) keyref[key].push_back(value);
}

#endif // A2_HPP

这是a2.cpp，只是测试a2.hpp的功能，这段代码不能改

// DO NOT EDIT THIS FILE !!!
// YOUR CODE MUST BE CONTAINED IN a2.hpp ONLY

#include <iostream>
#include "a2.hpp"


int main(int argc, char* argv[]) {
    key_value_sequences A;

    {
        key_value_sequences T;
        // k will be our key
        for (int k = 0; k < 10; ++k) {  //the actual tests will have way more than 10 sequences.
            // v is our value
            // here we are creating 10 sequences:
            // key = 0, sequence = (0)
            // key = 1, sequence = (0 1)
            // key = 2, sequence = (0 1 2)
            // ...
            // key = 9, sequence = (0 1 2 3 4 5 6 7 8 9)
            for (int v = 0; v < k + 1; ++v) T.insert(k, v);
        }

        T = T;
        key_value_sequences V = T;
        A = V;
    }
    std::vector<int> ref;

    if (A.size(-1) != 0) {
        std::cout << "fail" << std::endl;
        return -1;
    }

    for (int k = 0; k < 10; ++k) {
        if (A.size(k) != k + 1) {
            std::cout << "fail";
            return -1;
        } else {
            ref.clear();
            for (int v = 0; v < k + 1; ++v) ref.push_back(v);
            if (!std::equal(ref.begin(), ref.end(), A.data(k))) {
                std::cout << "fail 3 " << A.data(k) << " " << ref[k];
                return -1;
            }
        }
    }

    std::cout << "pass" << std::endl;

    return 0;
} // main

如果有人能帮助我提高代码效率，我将不胜感激，谢谢。

Answer 1

首先，我不相信您的代码是正确的。在插入中，如果它们的键有效，则创建一个新 vector 并将其插入到序列中。听起来不对，因为只有在您拥有新 key 时才会发生这种情况，但如果您的测试通过，则可能没问题。

性能方面:

• 避免使用 std::list。链表在当今的硬件上性能很差，因为它们破坏了流水线、缓存和预取。始终使用 std::vector 代替。如果有效负载真的很大并且您担心拷贝使用 std::vector<std::unique_ptr<T>>
• 尽量避免复制载体。在你的代码中你有 keyref[key] = seq.back()它复制 vector ，但应该没问题，因为它只有一个元素。

否则没有明显的性能问题。尝试对您的程序进行基准测试和分析，看看慢的部分在哪里。通常有一个或两个地方需要优化并获得出色的性能。如果仍然太慢，请提出另一个问题，将结果发布到哪里，以便我们更好地理解问题。