Nvidia C++ 矩阵转置：索引、缓存局部性与分块取舍

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版输入是 row-major 的连续 int64 数组，形状 R×C；输出是新的 row-major C×R 数组。题目未规定容器、数值类型或是否原地。
• R 或 C 为零时，元素数必须为零，返回空数组；R×C 溢出、元素数不匹配和零分块大小抛 invalid_argument。
• 分块边长是训练参数，默认 32；真实最佳值取决于元素宽度、缓存、编译器及目标机器，需要基准测试。

解题路线

1. 先确定坐标映射：原矩阵 (r,c) 的线性下标为 r×C+c；转置后坐标 (c,r)，线性下标为 c×R+r。非方阵也适用。
2. 朴素双循环若按输入行扫描，读是连续的，写入输出则跨 R 个元素；交换循环顺序会让写连续但输入跨 C 个元素。大矩阵可能因此反复装载缓存行。
3. 把输入划成 B×B 小块，块内按行扫描并写到对应输出位置。块让一段输入和输出在较短时间内反复使用；边缘块以实际剩余行列截断。分块只改善访问局部性，不改变复杂度。
4. 先量测朴素版与分块版在目标硬件上的表现；对于很小的矩阵，额外循环控制可能抵消缓存收益。

手动走一遍

输入 2×3 的 [[1,2,3],[4,5,6]]，线性数组为 [1,2,3,4,5,6]。元素 (1,2)=6 写到输出 (2,1)，即下标 2×2+1=5；完整输出 3×2 为 [[1,4],[2,5],[3,6]]。当 B=2，最右侧一列成为宽度为 1 的边缘块。

C++ 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <stdexcept>
#include <vector>

// Input and output use row-major storage. Output shape is cols x rows.
std::vector<std::int64_t> transpose_blocked(
    const std::vector<std::int64_t>& input,
    std::size_t rows,
    std::size_t cols,
    std::size_t block_size = 32) {
    if (block_size == 0 || (cols != 0 && rows > SIZE_MAX / cols) ||
        input.size() != rows * cols) {
        throw std::invalid_argument("invalid shape or block size");
    }
    std::vector<std::int64_t> output(input.size());
    for (std::size_t row0 = 0; row0 < rows;) {
        const std::size_t row_end = row0 + std::min(block_size, rows - row0);
        for (std::size_t col0 = 0; col0 < cols;) {
            const std::size_t col_end = col0 + std::min(block_size, cols - col0);
            for (std::size_t row = row0; row < row_end; ++row) {
                for (std::size_t col = col0; col < col_end; ++col) {
                    output[col * rows + row] = input[row * cols + col];
                }
            }
            col0 = col_end;
        }
        row0 = row_end;
    }
    return output;
}

复杂度

N=R×C：时间 O(N)，新输出 O(N)。分块只增加常数级索引和循环开销；缓存缺失数和真实耗时随矩阵形状、块大小、缓存层级而变化，不能仅凭渐近复杂度断言加速。

易错点与追问

容易失分的边界

• 把输出下标误写为 c×C+r：方阵测试可能蒙混过关，非方阵会出错甚至越界。
• 声称行优先和列优先只是术语：循环顺序直接决定哪一端的读写更连续。
• 只测试尺寸恰好为块大小倍数的矩阵，漏掉右边和下边的残余块。
• 把原地转置直接用于非方阵连续数组，却不处理置换环和元素重排；训练版明确分配新数组。

继续深挖

• 若必须原地转置，方阵可以沿对角线交换；非方阵需要置换环或额外存储，接口与复杂度另议。
• 若输入是 vector<vector<T>>，要先确认每行是否等长；其内存布局不等价于连续 row-major 数组。
• 如果元素很大、矩阵在 GPU 或跨 NUMA 节点，块大小与并行划分应根据带宽、合并访问和同步成本重新选。