如何洗牌 VecDeque？

Question

我可以像这样非常简单地打乱常规向量：

extern crate rand;
use rand::Rng;

fn shuffle(coll: &mut Vec<i32>) {
    rand::thread_rng().shuffle(coll);
}

问题是，我的代码现在需要使用 std::collections::VecDeque，这导致此代码无法编译。

解决这个问题的最简单方法是什么？

Answer 1

不幸的是，rand::Rng::shuffle method 被定义为洗牌切片。由于其自身的复杂性限制，VecDeque 无法将其元素存储在切片中，因此永远无法在 VecDeque.

上直接调用 shuffle

shuffle 算法的 values 参数的真正要求是有限序列长度、O(1) 元素访问和交换元素的能力，所有这些 VecDeque满足。如果有一个特征包含这些，那就太好了，这样 values 就可以通用了，但是没有。

对于当前的库，您有两个选择：

使用Vec::from(deque)将VecDeque复制到一个临时的Vec，打乱向量，return将内容返回到[=12] =].这种操作的复杂性将保持为 O(n)，但它可能需要临时向量的大量且昂贵的堆分配。
自己对 VecDeque 进行随机播放。 Fisher-Yates shuffle used by rand::Rng is well understood and easy to implement, in its modern form it boils down to only about 5 lines of code。虽然理论上标准库可以切换到不同的洗牌算法，但这在实践中不太可能发生。

第二个选项的通用形式，使用特征来表达 len-and-swap 要求，并采用 rand::Rng::shuffle 的代码，可能如下所示：

extern crate rand;

use std::collections::VecDeque;

// Real requirement for shuffle
trait LenAndSwap {
    fn len(&self) -> usize;
    fn swap(&mut self, i: usize, j: usize);
}

// An exact copy of rand::Rng::shuffle, with the signature modified to
// accept any type that implements LenAndSwap
fn shuffle<T, R>(values: &mut T, mut rng: R)
    where T: LenAndSwap,
          R: rand::Rng {
    let mut i = values.len();
    while i >= 2 {
        // invariant: elements with index >= i have been locked in place.
        i -= 1;
        // lock element i in place.
        values.swap(i, rng.gen_range(0, i + 1));
    }
}

// VecDeque trivially fulfills the LenAndSwap requirement, but
// we have to spell it out.
impl<T> LenAndSwap for VecDeque<T> {
    fn len(&self) -> usize {
        self.len()
    }
    fn swap(&mut self, i: usize, j: usize) {
        self.swap(i, j)
    }
}

fn main() {
    let mut v: VecDeque<u64> = [1, 2, 3, 4].iter().cloned().collect();
    shuffle(&mut v, rand::thread_rng());
    println!("{:?}", v);
}

Answer 2

分别打乱 VecDeque 的组件，从 VecDeque.html::as_mut_slices:

开始

use rand::seq::SliceRandom; // 0.6.5;
use std::collections::VecDeque; 

fn shuffle(coll: &mut VecDeque<i32>) {
    let mut rng = rand::thread_rng();
    let (a, b) = coll.as_mut_slices();
    a.shuffle(&mut rng);
    b.shuffle(&mut rng);
}

与一样，此解决方案从不在两个切片之间交换元素，因此不会发生一定程度的随机化。根据您对随机化的需要，这可能不会引起注意或破坏交易。

Answer 3

您可以使用 make_contiguous (documentation) 创建一个可变切片，然后您可以对其进行随机播放：

use rand::prelude::*;
use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    for p in 0..10 {
        deque.push_back(p);
    }
    deque.make_contiguous().shuffle(&mut rand::thread_rng());
    println!("Random deque: {:?}", deque)
}

Playground Link 如果您想在线试用。

如何洗牌 VecDeque？

How do I shuffle a VecDeque?

shuffle

deque

rust