如何在没有分配的情况下将循环缓冲区转换为O(n)中的向量？

Question

我有一个Vec循环缓冲区的分配.假设缓冲区已满,因此分配中没有元素不在循环缓冲区中.我现在想把那个循环缓冲区变成一个Vec循环缓冲区的第一个元素也是第一个元素的地方Vec.作为一个例子,我有这个(分配)功能:

fn normalize(tail: usize, buf: Vec<usize>) -> Vec<usize> {
    let n = buf.len();
    buf[tail..n]
        .iter()
        .chain(buf[0..tail].iter())
        .cloned()
        .collect()
}

操场

显然,这也可以在不分配任何东西的情况下完成,因为我们已经有足够大的分配,并且我们有一个swap操作来交换分配的任意元素.

fn normalize(tail: usize, mut buf: Vec<usize>) -> Vec<usize> {
    for _ in 0..tail {
        for i in 0..(buf.len() - 1) {
            buf.swap(i, i + 1);
        }
    }
    buf
}

操场

遗憾的是,这需要buf.len() * tail交换操作.我很确定它可以在buf.len() + tail交换操作中完成.对于具体的价值tail和buf.len()我已经能够找出解决方案,但我不知道如何在一般情况下这样做.

我的递归部分解决方案可以在行动中看到.

Answer 1

最简单的解决方案是使用3次反转,实际上这是在算法中推荐的线性时间旋转数组.

//  rotate to the left by "k".
fn rotate<T>(array: &mut [T], k: usize) {
    if array.is_empty() { return; }

    let k = k % array.len();

    array[..k].reverse();
    array[k..].reverse();
    array.reverse();
}

虽然这是线性的,但这需要最多读取和写入每个元素两次(使用奇数个元素反转一个范围不需要触摸中间元素).另一方面,反转的非常可预测的访问模式对于预取YMMV非常有用.

Answer 2

此操作通常称为向量的"旋转",例如C++标准库必须std::rotate执行此操作.有一些已知的算法可以进行操作,虽然你在移植时可能需要非常小心,如果你一直尝试使用非Copy类型,那么swaps变成关键,因为人们通常不能直接读取一些内容.向量.

也就是说,人们很可能能够使用/ 为此unsafe编写代码,因为数据只是被移动,因此不需要执行调用者定义的代码或对异常安全的非常复杂的担忧.std::ptr::readstd::ptr::write

上面链接中的C代码的一个端口(由@ker):

fn rotate(k: usize, a: &mut [i32]) {
    if k == 0 { return }

    let mut c = 0;
    let n = a.len();
    let mut v = 0;
    while c < n {
        let mut t = v;
        let mut tp = v + k;
        let tmp = a[v];
        c += 1;
        while tp != v {
            a[t] = a[tp];
            t = tp;
            tp += k;
            if tp >= n { tp -= n; }
            c += 1;
        }
        a[t] = tmp;
        v += 1;
    }
}