Rust で queue を作ってみる

pub fn pop(&mut self) -> Option<T>
Removes the last element from a vector and returns it, or None if it is empty. If you’d like to pop the first element, consider using VecDeque::pop_front instead.
Vec in std::vec - Rust
vectorから最後の要素を削除し，それを返します．空ならばNone を返します．最初の要素を取り出したい場合は，VecDeque::pop_front の使用を検討してください． (拙訳: みー)

Rust でスタック (LIFO) を利用するには，Vec<T> を使います．キュー (FIFO) を利用するには，VecDeque<T> を使います．ところで，キューはどうやって実装するのだろうと疑問に思い，調べてみたところ，スタックを2個使えば実現できることが分かりました．

lib.rs

use std::mem::swap;

struct Queue<T> {
    older: Vec<T>,
    younger: Vec<T>,
}

impl<T> Queue<T> {
    fn new() -> Queue<T> {
        Queue {
            older: Vec::new(),
            younger: Vec::new(),
        }
    }
    fn push(&mut self, c: T) {
        self.younger.push(c);
    }
    fn pop(&mut self) -> Option<T> {
        if self.older.is_empty() {
            if self.younger.is_empty() {
                return None;
            }
            swap(&mut self.older, &mut self.younger);
            self.older.reverse();
        }
        self.older.pop()
    }
}

*1

2個の Vec<T> older, younger を用意して，struct Queue<T> を定義します．要素を追加する場合は， younger に追加すればよいです．最初の要素を取り出す (pop) 場合は，older に要素があればそれを返します． older に要素がなくて younger に要素がある場合は，older と入れ替えて並び替えます．

• older: (empty)
• younger: 1,2,3

　　　↓

• older: 3,2,1
• younger: (empty)

このようにすれば，Vec<T>.pop() のみを使用して，FIFOを実現できるわけです． ユニットテストを実行して動作確認をします．

#[test]
fn test_push_pop() {
    let mut q = Queue::<char>::new();
    assert_eq!(q.pop(), None);
    q.push('A');
    q.push('B');
    assert_eq!(q.pop(), Some('A'));
    assert_eq!(q.pop(), Some('B'));
    q.push('C');
    q.push('D');
    q.push('E');
    q.push('F');
    assert_eq!(q.pop(), Some('C'));
    q.push('G');
    assert_eq!(q.pop(), Some('D'));
    assert_eq!(q.pop(), Some('E'));
    assert_eq!(q.pop(), Some('F'));
    q.push('H');
    assert_eq!(q.pop(), Some('G'));
    assert_eq!(q.pop(), Some('H'));
    assert_eq!(q.pop(), None);
    assert_eq!(q.pop(), None);
}

期待した通りに動作しました．工夫した結果，最初の要素を取り出す操作がどれぐらい早くなったのかをベンチマークします．Vec<T>, Queue<T>, VecDeque<T> に対して，1000個の要素を追加してからそれらを最初から順に取り出す処理の速度を測定し，比較します．

#![feature(test)]
extern crate test;

const COUNT: usize = 1000;

#[bench]
fn bench_queue_push_pop(b: &mut test::Bencher) {
    let mut q = Queue::new();
    b.iter(|| {
        (0..COUNT).for_each(|_| {
            q.push('A');
        });
        (0..COUNT).for_each(|_| {
            q.pop();
        });
    })
}

#[bench]
fn bench_vec_push_pop(b: &mut test::Bencher) {
    let mut v = Vec::<char>::new();
    b.iter(|| {
        (0..COUNT).for_each(|_| {
            v.push('A');
        });
        (0..COUNT).for_each(|_| {
            v.remove(0);
        });
    })
}

#[bench]
fn bench_vecdequeue_push_pop(b: &mut test::Bencher) {
    let mut q = VecDeque::<char>::new();
    b.iter(|| {
        (0..COUNT).for_each(|_| {
            q.push_back('A');
        });
        (0..COUNT).for_each(|_| {
            q.pop_front();
        });
    })
}

$ cargo +nightly bench
    Finished bench [optimized] target(s) in 0.00s
     Running unittests src/lib.rs (target/release/deps/queue-b2a289f32b3025f5)

running 4 tests
test test_push_pop ... ignored
test bench_queue_push_pop    ... bench:         729 ns/iter (+/- 8)
test bench_vec_push_pop      ... bench:      15,452 ns/iter (+/- 171)
test bench_vecqueue_push_pop ... bench:         957 ns/iter (+/- 853)

test result: ok. 0 passed; 0 failed; 1 ignored; 3 measured; 0 filtered out; finished in 0.69s

要素が1000個の場合，Queue<T> は Vec<T> よりも約20倍速いという結果でした．Queue<T>, VecDeque<T> の速度差はあまりないものの，少し Queue<T> が速そうです．

期待した処理が期待した速度で実行できたので，満足しました．

*1:https://github.com/ProgrammingRust/examples/blob/master/queue/src/lib.rs を参考に作成．