条件求和 vs. 先排序后条件求和

给定一个比较长的随机整数数组，比较两种数组条件求和方式消耗的 CPU 时间：

1. 不排序，直接对其中所有大于 ::threshold 的整数求和；
2. 生序排序，然后再对同样的元素做整数求和操作。

#include <algorithm>
#include <iostream>
#include <ctime>
#include <random>

constexpr int count = 85600;
constexpr int threshold = 255;
constexpr int nRow = 200;
constexpr int nCol = 80000;

/** 获取随机数 */
void getNums(int (&nums)[count]) {
    std::random_device r;
    std::default_random_engine e(r());
    std::uniform_int_distribution<int> dist(0, 500);
    for (auto &ele : nums)
        ele = dist(e);
}

/** 打印时间 */
template <typename T>
void printElapsed(const T& start, const T& end) {
    std::cout << "Elapsed: " << end - start << " clocks\\n";
}

/** 对数组大于特定对数求和 */
void sumThreshold(int (&nums)[count]) {
    int sum = 0;
    auto start = std::clock();
    for (auto &ele : nums)
        if (ele > threshold)
            sum += ele;
    auto end = std::clock();
    printElapsed(start, end);
}

/** 复制数组内容 */
template <typename T, size_t lenDst>
void copyArray(T (&dst)[lenDst], const T (&src)[lenDst]) {
    int i = 0;
    while (i < lenDst) {
        dst[i] = src[i];
        ++i;
    }
}

/** 计算一个随机整数数组中所有大于 threshold 的整数的和 */
void compute() {
    // 栈上分配数组空间
    int randomNums[count];

    // 用随机数初始化数组
    getNums(randomNums);

    // 排序然后再执行求和，从排序结束后开始计时：
    {
        int nums[std::size(randomNums)];
        copyArray(nums, randomNums);
        std::sort(std::begin(nums), std::end(nums));
        sumThreshold(nums);
    }

    // 不排序直接执行求和，计时(CPU Time)看操作系统总共调度了多少个 CPU clock 给这段程序：
    {
        int nums[std::size(randomNums)];
        copyArray(nums, randomNums);
        sumThreshold(nums);
    }
}

int main() {
    compute();
    return 0;
}

在 CMakeList.txt 的恰当位置插入：set(CMAKE_CXX_FLAGS "-O0") 然后编译、运行：

第一次输出：

Elapsed: 199 clocks
Elapsed: 689 clocks

第二次输出：

Elapsed: 198 clocks
Elapsed: 751 clocks

第三次输出：

Elapsed: 199 clocks
Elapsed: 678 clocks

观察发现第二次打印的 Elapsed clocks 值总是大于第一次的，换言之，第一种求和方式更快，为什么呢？

按行遍历 vs. 按列遍历

给定一个 nRow x nCol 的二维 int 数组 nums[nRow][nCol], 比较下列这两种求和方式：

1. 一行一行地求和，即，先对第一行求和，然后从剩下的所有行的开始的第一行开始继续求和；
2. 一列一列地求和，即，先对第一列求和，然后从剩下的所有列的开始的第一列开始继续求和；

#include <algorithm>
#include <iostream>
#include <ctime>
#include <random>

constexpr int nRow = 200;
constexpr int nCol = 80000;

/** 获取随机数（一般用在数组或者高阶数组上，比如矩阵） */
void getNums(int *nums, size_t size) {
    std::random_device r;
    std::default_random_engine e(r());
    std::uniform_int_distribution<int> dist(0, 500);
    for (size_t i = 0; i < size; ++i)
        nums[i] = dist(e);
}

/** 打印时间 */
template <typename T>
void printElapsed(const T& start, const T& end) {
    std::cout << "Elapsed: " << end - start << " clocks\\n";
}

void compute() {
    auto nums = new int[nRow][nCol];
    getNums(&nums[0][0], nRow*nCol);

    for (int count = 0; count < 10; ++count) {
        std::cout << "==== " << "iter: " << count << " ====" << std::endl;
        // 第一种方式求和
        {
            int sum = 0;
            auto start = std::clock();
            for (int i = 0; i < nRow; ++i)
                for (int j = 0; j < nCol; ++j)
                    sum += nums[i][j];
            auto end = std::clock();
            printElapsed(start, end);
        }

        // 第二种方式求和
        {
            int sum = 0;
            auto start = std::clock();
            for (int j = 0; j < nCol; ++j)
                for (int i = 0; i < nRow; ++i)
                    sum += nums[i][j];
            auto end = std::clock();
            printElapsed(start, end);
        }
    }

    delete[] nums;
}

int main() {
    compute();
    return 0;
}

在 CMakeList.txt 的恰当位置插入：set(CMAKE_CXX_FLAGS "-O0") 然后编译、运行：