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)は、一時的VecにVecDequeをコピーベクトルをシャッフルし、VecDequeに戻って内容を返すために：現在のライブラリと

  は、次の2つのオプションがあります。この操作の複雑さはO（n）のままですが、一時的なベクトルの潜在的に大規模で高価なヒープ割り当てが必要になります。

• 自分でVecDequeにシャッフルを実装します。 によって使用されるFisher-Yates shuffleは、よく理解され、実装が容易であり、現代的な形態では、それは約5 lines of codeまでしか沸騰しない。理論的には標準ライブラリは異なるシャッフルアルゴリズムに切り替えることができますが、それは実際には起こりそうにありません。

第二のオプションの一般的な形態は、このようになり、LENアンドスワップ要件を発現するように形質を用いて、及び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で始まる：Lukas Kalbertodt points outとして

extern crate rand; 

use std::collections::VecDeque; 
use rand::Rng; 

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

fn main() {} 

、この解決策は間の要素を入れ替えたことがありません2つのスライスので、一定量のランダム化は起こりません。あなたの無作為化のニーズに応じて、これは目立たないかもしれません。