如何在没有分配的情况下将循环缓冲区转换为 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()
}

Playground

显然这也可以在不分配任何东西的情况下完成，因为我们已经有一个足够大的分配，并且我们有一个 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
}

Playground

遗憾的是，这需要 buf.len() * tail 交换操作。我相当确定它可以在 buf.len() + tail 交换操作中完成。对于 tail 和 buf.len() 的具体值，我已经能够找出解决方案，但我不确定在一般情况下该怎么做。

我的递归部分解决方案can be seen in action。

Answer 1

此操作通常称为向量的 "rotation"，例如C++ 标准库有 std::rotate to do this. There are known algorithms 用于执行操作，但如果您尝试移植时可能必须非常小心 generically/with 非 Copy 类型，其中 swaps 成为关键，因为通常不能直接从向量中读取某些内容。

也就是说，人们可能能够为此使用 unsafe 代码和 std::ptr::read/std::ptr::write，因为数据只是四处移动，因此不需要执行调用者定义的代码或对异常安全性的非常复杂的担忧。

上面link中的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;
    }
}

Answer 2

最简单的解决方案是使用 3 个反转，这确实是 Algorithm to rotate an array in linear time 中推荐的方法。

//  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。

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

How do I turn a circular buffer into a vector in O(n) without an allocation?

algorithm

circular-buffer

rust