如何使用STL以优化和快速的方式计算2D向量中变量(数字)的出现次数？

Question

我有一个整数的2D向量，想要计算某个值重复了多少次。例如：

我将myvector定义为：

std :: vector <std :: vector <int>> myVector {{{1, 2, 9, 4, 6},
                                       {8, 3, 5, 4, 8},
                                       {4, 1, 9, 1, 7},
                                       {5, 2, 7, 3, 4},
                                       {7, 4, 3, 5, 1};

例如，我的目标是计算x=4的元素的数量，结果返回5:我尝试：

int sum = 0;
for (auto i: myVector) {
     sum + = std :: count (i.begin (), i.end (), 4);

然而，我需要在实时应用程序中多次运行这种类型的方法，但for循环很耗时，我试图通过使用STL的函数来最小化执行时间，我已经尝试过了：

   std :: count (myVector.begin (), myVector.end (), 4);

但是，此语法不能直接在2D向量上工作。

有人有解决方案吗？

Answer 1

    #include <iostream> // std::cout & std::endl
    #include <algorithm>// std::count
    #include <vector>   // std::vector
    #include <numeric>  // std::accumulate
    #include <chrono>   
    
    using namespace std::chrono;

    int main() {

    int value_to_Count = 4;
    std::vector <std::vector <int>> myVector {{1, 2, 9, 4, 1, 2, 9, 4, 1},
                                              {8, 3, 5, 4, 1, 2, 9, 4, 8},
                                              {4, 1, 9, 1, 5, 4, 1, 2, 7},
                                              {5, 2, 7, 3, 2, 9, 4, 1, 4},
                                              {7, 4, 3, 5, 1, 2, 9, 4, 1},
                                              {1, 2, 9, 4, 1, 2, 9, 4, 1},
                                              {8, 3, 5, 4, 1, 2, 9, 4, 8},
                                              {4, 1, 9, 1, 5, 4, 1, 2, 7},
                                              {5, 2, 7, 3, 2, 9, 4, 1, 4},
                                              {7, 4, 3, 5, 1, 2, 9, 4, 1},
                                              {1, 2, 9, 4, 1, 2, 9, 4, 1},
                                              {8, 3, 5, 4, 1, 2, 9, 4, 8},
                                              {7, 4, 3, 5, 1, 2, 9, 4, 1}};
    /** Your Method **/
    int total_count = 0;
    auto start = high_resolution_clock::now();
    for (auto i: myVector)
         total_count += std::count( i.begin(), i.end(), 4);
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);

    std::cout << "compute total_count = " << total_count << "  in " << duration.count() << "milliseconds" << std::endl;

    /** Optimized Method 1 (prefer this) **/
    total_count = 0;
    start = high_resolution_clock::now();
    for (const auto &i: myVector)
         total_count += std::count( i.begin(), i.end(), 4);
    stop = high_resolution_clock::now();
    duration = duration_cast<microseconds>(stop - start);

    std::cout << "compute total_count = " << total_count << "  in " << duration.count() << "milliseconds" << std::endl;
                                      
    /** Optimized Method 2 *enter code here*/
    start = high_resolution_clock::now();
    total_count = std::accumulate(myVector.begin(), myVector.end(), 0,
                                    [&](int acc, const std::vector<int>& curr){
                                      return acc + std::count(curr.begin(), curr.end(), value_to_Count);
                                    }
                                   );
    stop = high_resolution_clock::now();
    duration = duration_cast<microseconds>(stop - start);

    std::cout << "compute total_count = " << total_count << "  in " << duration.count() << " milliseconds" << std::endl;
}

输出：

compute total_count = 26  in 6 milliseconds
compute total_count = 26  in 3 milliseconds
compute total_count = 26  in 3 milliseconds

QuickBench results

Answer 2

然而，我需要在实时应用程序中多次运行这种类型的方法，但是

循环很耗时，我试图通过使用STL的函数来最小化执行时间，我已经尝试过了：

如果您想要比最佳执行时间更长的执行时间，甚至不要首先使用2-D向量，您可以使用一个类，使用一些常用的数学运算在1-D向量上实现2-D视图。

#include <vector>
#include <utility>
// ...

template <typename T>
class vector_2d_view : public std::vector<T> {
    using size_type = typename std::vector<T>::size_type;
    size_type width_;
public:
    vector_2d_view(size_type const width) : width_(width) {};
    vector_2d_view(std::vector<T> vec, size_type const width) : std::vector<T>(std::move(vec)), width_(width) {}

    T& operator()(size_type const y, size_type const x) {
        auto const index = width_ * y + x;
        if (index >= this->size())
            this->resize(index + 1);
        return this->operator[](index);
    }
};

它在内部使用了一个1-D向量，但在上面用operator()提供了一个方便的2-D包装器。现在，您可以像这样访问元素：

vector_2d_view<int> vec ({
    1, 2,
    3, 4
}, 2);

vec(0, 0); // Gives 1
vec(0, 1); // Gives 2
vec(1, 0); // Gives 3
vec(1, 1); // Gives 4

要计算它的元素，可以这样做：

// ...
const auto sum = std::count(vec.begin(), vec.end(), 4);
// ...

现在，我已经执行了一个基准测试来证明上面的方法比使用传统的std::vector<std::vector<int>>快得多，您可以在here中查看它

Time taken by 1st method (std::vector<std::vector<int>): 0.00027ms
5
Time taken by 2nd method (vector_2d_view<int>): 0.000105ms
5

这清楚地表明，使用vector_2d_view<int>的第二种方法比第一种方法完成计数的速度更快。

P.S.:上述时间在每次迭代中可能不同，但即使在进行了多次迭代后，我仍然得到了类似的结果，即第二次所用的时间比第一次所用的时间要少。