C++中使用zip range对并行向量排序：实际效率究竟如何？Rust能否实现类似操作？

嘿，这个问题我太有共鸣了！之前处理并行向量排序时，也特别烦Rust里默认用元组向量的路子——明明只是想按一个key向量排个序，顺带把其他关联向量的顺序同步调对，平白无故要分配一堆元组内存，想想都觉得浪费内存带宽！

先说说C这边的zip range吧，C20引入的std::ranges::zip_view简直是为这个场景量身定做的！它根本不分配任何额外内存，只是把多个向量“打包”成一个视图，排序的时候直接操作原向量里的元素交换，完全是原地操作。比如写出来的代码是这样的：

#include <vector>
#include <ranges>
#include <algorithm>

int main() {
    std::vector<int> keys = {3, 1, 4, 1, 5};
    std::vector<std::string> values = {"c", "a", "d", "b", "e"};
    
    // 把keys和values打包成视图，直接按key排序
    auto zipped = std::views::zip(keys, values);
    std::ranges::sort(zipped, [](const auto& a, const auto& b) {
        return std::get<0>(a) < std::get<0>(b);
    });
}

至于效率？真的没话说！因为zip_view只是个视图，没有任何数据拷贝，排序时的额外开销就只是每次访问元素时的tuple解包，但在O2及以上优化等级下，编译器基本能把这部分开销优化得一干二净，跑起来和你手动写循环同步交换两个向量的速度几乎一模一样——完全不用担心效率打折扣。

那Rust这边能不能实现类似的操作呢？可惜标准库目前还没有直接提供这种“零分配zip排序”的工具，但咱们可以自己搞出类似的效果呀！最常用的路子就是用索引向量当中间层：先把索引按key排序，再根据排序后的索引把原向量的元素挪到正确位置。

比如先整个简单版本：

fn main() {
    let mut keys = vec![3, 1, 4, 1, 5];
    let mut values = vec!["c", "a", "d", "b", "e"];
    
    // 生成0到len-1的索引向量
    let mut indices: Vec<usize> = (0..keys.len()).collect();
    // 按keys对应的值排序索引
    indices.sort_by_key(|&i| keys[i]);
    
    // 根据排序后的索引重新生成两个向量（这里其实还是有分配，不过是小开销）
    let sorted_keys: Vec<_> = indices.iter().map(|&i| keys[i]).collect();
    let sorted_values: Vec<_> = indices.iter().map(|&i| values[i]).collect();
    
    keys = sorted_keys;
    values = sorted_values;
}

如果你连这点小分配都不想有，那可以搞个完全原地交换的版本，用一个visited数组记录哪些位置已经处理过，避免重复操作：

fn sort_parallel<T, U, F>(keys: &mut [T], values: &mut [U], mut compare: F)
where
    F: FnMut(&T, &T) -> bool,
{
    let len = keys.len();
    let mut indices: Vec<usize> = (0..len).collect();
    // 按自定义规则排序索引
    indices.sort_by(|&a, &b| compare(&keys[a], &keys[b]));
    
    let mut visited = vec![false; len];
    for i in 0..len {
        if visited[i] {
            continue;
        }
        let mut current = i;
        // 循环处理当前环里的所有元素
        while !visited[current] {
            visited[current] = true;
            let target = indices[current];
            if current != target {
                // 直接交换原向量的元素
                keys.swap(current, target);
                values.swap(current, target);
            }
            current = target;
        }
    }
}

fn main() {
    let mut keys = vec![3, 1, 4, 1, 5];
    let mut values = vec!["c", "a", "d", "b", "e"];
    
    // 按key升序排序两个并行向量
    sort_parallel(&mut keys, &mut values, |a, b| a < b);
}

这个版本除了索引和visited两个小向量（内存开销远小于元组向量），完全是在原向量上操作，和C++的zip range的内存效率已经很接近了。当然如果能接受用第三方库，itertools里的izip!宏也能帮你简化代码，但如果想纯靠标准库，上面的方法就足够用了。

至于Rust这个方法的效率？比起C++的zip_view会稍微慢一丢丢，因为多了索引排序和循环交换的步骤，但如果你的元素是大对象（比如字符串、自定义结构体），这种方法比分配元组向量要高效得多——毕竟元组向量需要复制所有元素，而这里只是交换原向量的元素，内存压力小很多；如果是小元素，那元组向量的方法可能反而更快，因为缓存局部性更好，具体还是得看你的业务场景。

总的来说，C++的zip range确实是这个场景下的最优解，零额外分配+拉满的效率；Rust虽然标准库没直接给，但咱们手动用索引也能达到差不多的内存友好效果，完全能满足不想额外大分配的需求！

备注：内容来源于stack exchange，提问作者Sun of A beach