败犬日报
败犬日报 2025-10-31

主题

败犬日报 2025-10-31 ​

1. 随笔：在C++中像Python一样传递keyword argument（文章） ​

https://zhuanlan.zhihu.com/p/1966608200796177222

看一乐。

2. 怎么给 T&& 参数一个回调函数默认参数 ​

cpp
template <typename T>
void run(T &&callback = [](auto &&arg) {}) {
    callback(1);
}

int main() {
    run();  // Candidate template ignored: couldn't infer template argument 'T'
    run([](auto &&arg) {});
}

要指定默认模板参数，因为默认参数不参与模板推导。

cpp
template <typename T = decltype([](auto &&) {})>
void run(T &&callback = {}) {
    callback(1);
}

int main() {
    run();
    run([](auto &&) {});
}

在 C++20 以前的写法是：

cpp
struct default_functor {
    template <typename T>
    void operator()(T &&) const {}
};

template <typename T = default_functor>
void run(T &&callback = {}) {
    callback(1);
}

int main() {
    run();
    run([](auto &&) {});
}

3. 面试题：1024 核，N 个数找最大值，不许用锁或原子操作 ​

这问题就很奇怪，线程同步的几个方式算不算用锁或原子变量？算就没法多线程了，那 1024 核的条件有什么用。

不考虑“不许用锁或原子操作”，就把 N 给分为 1024 个等长的块，每个线程处理一块，拿到每一块的最大值。最后单线程把每个块的最大值再求一遍最大值即可。

用 openmp 很容易就能实现：

cpp
#include <omp.h>

#include <algorithm>
#include <cstdio>
#include <limits>
#include <vector>

int get_max(int *a, int n, int n_threads) {
    std::vector<int> result(n_threads, 0);
#pragma omp parallel num_threads(n_threads)
    {
        int max = std::numeric_limits<int>::min();
#pragma omp for
        for (int i = 0; i < n; i++) {
            max = std::max(max, a[i]);
        }
        result[omp_get_thread_num()] = max;
    }
    return *std::max_element(result.begin(), result.end());
}

int main() {
    int arr[] = {1, 3, 2, 8, 4, 6};
    printf("%d\n", get_max(arr, std::size(arr), 4));
}

// g++ test.cpp -o test -O3 -fopenmp && ./test

这里有一点是最后一步为什么不用多线程？这是因为 1024 个数求最大值已经非常快了，而且数据在 L3 cache 上，粗略估计 100 ns。而线程同步开销本身就至少几百 ns，在我机器上 4 核同步 600 ns。

所以单线程就是最快的。

用下面的程序可以测一下线程同步开销：

cpp
#include <omp.h>

#include <chrono>
#include <iostream>

int main() {
    const int STEP = 1000000;
    const int n_threads = 4;
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < STEP; ++i) {
#pragma omp parallel num_threads(n_threads)
        {
            asm volatile("" ::: "memory");
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = end - start;
    std::cout << "time: " << elapsed.count() / STEP << " ns\n";
}

但是群友表示这个答案面试官认为还能再快，那就再把 simd，numa，分布式，gpu 这些答一遍，总该满意了。

4. 面试题：n 个数 x[i] 要求移动后 L <= x[i] <= R，x[i] + w < x[i + 1]，求最小移动距离之和 ​

这题作为面试题难度太大了，是保序回归（又叫单调回归）。首先令 y[i] = x[i] + (w + 1) * i，这样条件就简化为 L <= y[i] <= R + (w + 1) * (n - 1)，y[i] <= y[i + 1]。这个就是经典的保序回归了，套模板即可。

保序回归：给定实数序列 ai，求不下降实数序列 bi，使得 ∑i=1n|ai−bi|p 最小化。

p = 1 就是这题，需要单调栈 + 维护中位数（双堆或平衡树）。因为一堆点移动到一个点是中位数最优，保序回归就把数组分成多个块，每块求中位数即可。