Lib.rs

BucketQueue

一种优先队列，可以高效地存储和检索优先级为小整数的项。项存储在 '桶' 中，这些桶是其他数据结构，如 Vec 或 VecDeque。BucketQueue 设计用于与各种排队语义一起工作，如 先入先出、后入先出 和 双端队列，但你也可以根据自己的需要进行扩展。

此实现大致基于 维基百科上的描述。

基本用法

extern crate bucket_queue;

use bucket_queue::*;
use std::collections::VecDeque;

fn main() {
    // Initialize a queue with buckets that are VecDeque:
    let mut queue = BucketQueue::<VecDeque<&str>>::new();

    // Enqueue some items with associated priorities:
    queue.enqueue("refactor", 1);
    queue.enqueue("fix tests", 0);
    queue.enqueue("drink coffee", 1);
    queue.enqueue("documentation", 1);
    queue.enqueue("pull request", 2);

    // Dequeue items, ordered by minimum priority:
    assert_eq!(queue.dequeue_min(), Some("fix tests"));
    assert_eq!(queue.dequeue_min(), Some("refactor"));
    assert_eq!(queue.dequeue_min(), Some("drink coffee"));
    assert_eq!(queue.dequeue_min(), Some("documentation"));
    assert_eq!(queue.dequeue_min(), Some("pull request"));
    assert_eq!(queue.dequeue_min(), None);
}

注意事项

• 您需要使用 use bucket_queue::* 来引入所需的特质
• 如果您的优先级是相反的，您也可以使用 dequeue_max
• 此示例使用先入先出 (FIFO) 排队语义

后入先出

extern crate bucket_queue;

use bucket_queue::*;

fn main() {
    // Initialize a queue with buckets that are Vec:
    let mut queue = BucketQueue::<Vec<&str>>::new();

    // Push some items with associated priorities:
    queue.push("refactor", 1);
    queue.push("fix tests", 0);
    queue.push("drink coffee", 1);
    queue.push("documentation", 1);
    queue.push("pull request", 2);

    // Pop items, ordered by minimum priority:
    assert_eq!(queue.pop_min(), Some("fix tests"));
    assert_eq!(queue.pop_min(), Some("documentation")); //      ^
    assert_eq!(queue.pop_min(), Some("drink coffee"));  //      | reversed
    assert_eq!(queue.pop_min(), Some("refactor"));      //      v
    assert_eq!(queue.pop_min(), Some("pull request"));
    assert_eq!(queue.pop_min(), None);
}

注意事项

• Vec 提供后入先出 (LIFO) 排队语义
• 我们使用 push 和 pop_min 而不是 enqueue 和 dequeue_min
• 排队语义仅影响具有相同优先级的项的检索顺序

双端

extern crate bucket_queue;

use bucket_queue::*;
use std::collections::VecDeque;

fn main() {
    // Initialize a queue with buckets that are VecDeque:
    let mut queue = BucketQueue::<VecDeque<&str>>::new();

    // Push some items with associated priorities:
    queue.push_back("refactor", 1);
    queue.push_back("fix tests", 0);
    queue.push_front("drink coffee", 1);  // <-- pushed to the front
    queue.push_back("documentation", 1);
    queue.push_back("pull request", 2);

    // Pop items, ordered by minimum priority:
    assert_eq!(queue.pop_front_min(), Some("fix tests"));
    assert_eq!(queue.pop_front_min(), Some("drink coffee"));
    assert_eq!(queue.pop_back_min(), Some("documentation"));   // <-- popped from the back
    assert_eq!(queue.pop_front_min(), Some("refactor"));
    assert_eq!(queue.pop_front_min(), Some("pull request"));
    assert_eq!(queue.pop_front_min(), None);
}

注意事项

• VecDeque (也) 提供双端排队语义

• 我们可以从前后两端进行 push 和 pop

   Cargo.toml |104 // Pop items, ord- 再次，优先级仍然得到尊重，这仅影响桶中项的顺序

实用函数

extern crate bucket_queue;

use bucket_queue::*;
use std::collections::VecDeque;

fn main() {
    // Initialize a queue with buckets that are VecDeque:
    let mut queue = BucketQueue::<VecDeque<&str>>::new();

    // Enqueue some items with associated priorities:
    queue.enqueue("refactor", 1);
    queue.enqueue("fix tests", 0);
    queue.enqueue("drink coffee", 1);
    queue.enqueue("documentation", 1);
    queue.enqueue("pull request", 2);

    // Dequeue an item for a specific priority:
    assert_eq!(queue.dequeue(1), Some("refactor"));

    // Call some utility functions:
    assert_eq!(queue.len(), 4);
    assert_eq!(queue.is_empty(), false);
    assert_eq!(queue.min_priority(), Some(0));
    assert_eq!(queue.max_priority(), Some(2));

    // Remove all items from bucket 1:
    queue.replace(1, None);
    assert_eq!(queue.len(), 2);

    // Create a replacement for bucket 0:
    let new = VecDeque::from(vec!["fix lints"]);

    // Replace the contents of bucket 0:
    let old = queue.replace(0, Some(new));
    assert_eq!(old.unwrap(), &["fix tests"]);

    // Clear all items from the queue:
    queue.clear();

    assert_eq!(queue.len(), 0);
    assert_eq!(queue.is_empty(), true);
    assert_eq!(queue.min_priority(), None);
    assert_eq!(queue.max_priority(), None);
}

注意事项

• 您也可以为特定优先级的项目使用 pop / pop_front 和 pop_back
• 由于有太多不同的方式来检索项目，BucketQueue 没有实现 迭代器

嵌套队列

extern crate bucket_queue;

use bucket_queue::*;
use std::collections::VecDeque;

fn main() {
    // Initialize a queue with buckets that are themselves BucketQueue:
    let mut queue = BucketQueue::<BucketQueue<VecDeque<&str>>>::new();

    // Enqueue some items with two-dimensional priorities:
    queue.bucket(1).enqueue("refactor", 1);
    queue.bucket(0).enqueue("fix tests", 0);
    queue.bucket(1).enqueue("drink coffee", 0);
    queue.bucket(1).enqueue("documentation", 2);
    queue.bucket(2).enqueue("pull request", 0);

    // Dequeue items, ordered by minimum priority:
    assert_eq!(queue.min_bucket().dequeue_min(), Some("fix tests"));
    assert_eq!(queue.min_bucket().dequeue_min(), Some("drink coffee"));
    assert_eq!(queue.min_bucket().dequeue_min(), Some("refactor"));
    assert_eq!(queue.min_bucket().dequeue_min(), Some("documentation"));
    assert_eq!(queue.min_bucket().dequeue_min(), Some("pull request"));
    assert_eq!(queue.min_bucket().dequeue_min(), None);
}

注意事项

• BucketQueue 可以任意嵌套到任意级别的数量
• min_bucket 和 max_bucket 查找具有最低或最高优先级的桶
• 这些是等价的

queue.bucket(1).enqueue("documentation", 2);
queue.bucket(1).bucket(2).enqueue("documentation");

• 这些也是

queue.replace(0, None);
queue.bucket(0).clear();

测试

所有针对此包的测试都在这里：bucket_queue.rs。这也可以作为参考。

基准测试

test benchmark_100_items_into_4_buckets                  ... bench:       1,272 ns/iter (+/- 28)
test benchmark_1_000_items_into_8_buckets                ... bench:      12,103 ns/iter (+/- 1,157)
test benchmark_10_000_items_into_16_buckets              ... bench:     121,042 ns/iter (+/- 3,095)
test benchmark_100_000_items_into_32_buckets             ... bench:   1,214,780 ns/iter (+/- 24,987)
test benchmark_1_000_000_items_into_64_buckets           ... bench:  14,487,399 ns/iter (+/- 881,656)

test benchmark_100_items_into_4x4_nested_buckets         ... bench:       3,742 ns/iter (+/- 170)
test benchmark_1_000_items_into_8x8_nested_buckets       ... bench:      38,916 ns/iter (+/- 3,270)
test benchmark_10_000_items_into_16x16_nested_buckets    ... bench:     353,102 ns/iter (+/- 11,718)
test benchmark_100_000_items_into_32x32_nested_buckets   ... bench:   3,842,643 ns/iter (+/- 71,892)
test benchmark_1_000_000_items_into_64x64_nested_buckets ... bench:  47,129,660 ns/iter (+/- 726,701)

注意事项

• 这些基准测试在一个 Intel Core i5-4430 CPU 上运行
• 最慢的例子（将一百万个项放入64x64嵌套桶中）耗时47毫秒
• 可以使用 cargo bench 运行这些基准测试

添加新的队列语义

在这个例子中，我们将介绍一个 BiggestFirstQueue。这将从桶中检索项，从大到小。BucketQueue 的优先级仍然会被尊重，但如果项具有相同的优先级，则先返回较大的项。

需要很多样板代码（抱歉）。这主要是因为尝试使事物更灵活。我已经将其分解为步骤。

步骤1：定义一个新的 Bucket 类型

use std::collections::BinaryHeap;

struct Heap<T> {
    binary_heap: BinaryHeap<T>
}

impl<T: Ord> Bucket for Heap<T> {
    type Item = T;

    fn new_bucket() -> Self {
        Heap { binary_heap: BinaryHeap::new() }
    }

    fn len_bucket(&self) -> usize {
        self.binary_heap.len()
    }

    fn is_empty_bucket(&self) -> bool {
        self.binary_heap.is_empty()
    }

    fn clear(&mut self) {
        self.binary_heap.clear()
    }
}

注意事项

• 此示例使用 BinaryHeap 来存储项
• 由于 Rust 的 孤儿规则，需要将其包装在结构体中
• Ord 约束是由 BinaryHeap 而不是 BucketQueue 强制的
• 其中大部分是样板代码，它通过代理调用转发到 BinaryHeap

步骤2：定义桶如何与项协同工作

trait BiggestFirstBucket: Bucket {
    fn insert(&mut self, item: Self::Item);

    fn biggest(&mut self) -> Option<Self::Item>;
}

impl<T: Ord> BiggestFirstBucket for Heap<T> {
    fn insert(&mut self, item: Self::Item) {
        self.binary_heap.push(item)
    }

    fn biggest(&mut self) -> Option<Self::Item> {
        self.binary_heap.pop()
    }
}

注意事项

• BiggestFirstBucket 是 Bucket 的一个 超特性
• 使用 insert 将项添加到桶中，并使用 biggest 检索项
• 此特性为 Heap 实现，它调用 push 和 pop 在 BinaryHeap 上

步骤3：为我们的 Bucket 定义一个新的 Queue 类型

trait BiggestFirstQueue<B: BiggestFirstBucket>: Queue<B> {
    fn insert(&mut self, item: B::Item, priority: usize) {
        self.bucket_for_adding(priority).insert(item);
    }

    fn biggest(&mut self) -> Option<B::Item> {
        let priority = self.min_priority()?;
        self.bucket_for_removing(priority)?.biggest()
    }
}

impl<B: BiggestFirstBucket> BiggestFirstQueue<B> for BucketQueue<B> { }

注意事项

• bucket_for_adding 和 bucket_for_removing 是内部函数，用于保持 BucketQueue 的索引最新
• biggest 从最低优先级的桶中检索，但如果我们想，可以添加 biggest_min 和 biggest_max
• 最后一行将此队列语义添加到 BucketQueue 中

最后，我们可以使用它

fn main() {
    // Initialize a queue with buckets that are Heap:
    let mut queue = BucketQueue::<Heap<&str>>::new();

    // Insert some items with associated priorities:
    queue.insert("aardvark", 0);
    queue.insert("barn owl", 0);
    queue.insert("crocodile", 0);
    queue.insert("donkey", 1);

    // Retrieve the items reverse alphabetically, ordered by minimum priority:
    assert_eq!(queue.biggest(), Some("crocodile"));
    assert_eq!(queue.biggest(), Some("barn owl"));
    assert_eq!(queue.biggest(), Some("aardvark"));
    assert_eq!(queue.biggest(), Some("donkey"));
    assert_eq!(queue.biggest(), None);
}

注意事项

• BucketQueue 使用我们的自定义 Heap 类型
• 队列语义是从使用的 Bucket 类型推断出来的
• donkey 的优先级是 1，因此它出现在末尾
• 此示例的完整内容可以在这里找到：custom_queue.rs，并且可以使用 cargo run 运行

(可选) 步骤4：添加嵌套支持

为了让你的新队列类型在 BucketQueue 嵌套时工作，你需要额外的样板代码

impl<'a, Q, B, C> BiggestFirstQueue<C> for DeferredBucket<'a, Q, B>
    where Q: Queue<B>, B: Bucket + Queue<C>, C: BiggestFirstBucket { }

impl<'a, Q, B> BiggestFirstBucket for DeferredBucket<'a, Q, B>
    where Q: BiggestFirstQueue<B>, B: BiggestFirstBucket
{
    fn insert(&mut self, item: Self::Item) {
        self.adding().insert(item);
    }

    fn biggest(&mut self) -> Option<Self::Item> {
        self.removing()?.biggest()
    }
}

注意事项

• 这些都是样板代码，并调用已定义的函数
• adding 和 removing 是内部函数，用于保持 BucketQueue 的索引最新

带有嵌套的最终示例

fn main() {
    // Initialize a queue with buckets that are themselves BucketQueue:
    let mut queue = BucketQueue::<BucketQueue<Heap<&str>>>::new();

    // Insert some items into nested buckets:
    queue.bucket(0).insert("aardvark", 0);
    queue.bucket(0).insert("barn owl", 0);
    queue.bucket(1).bucket(1).insert("crocodile");
    queue.bucket(1).bucket(0).insert("donkey");

    // Retrieve the items from nested buckets:
    assert_eq!(queue.min_bucket().biggest(), Some("barn owl"));
    assert_eq!(queue.min_bucket().biggest(), Some("aardvark"));
    assert_eq!(queue.min_bucket().biggest(), Some("donkey"));
    assert_eq!(queue.min_bucket().biggest(), Some("crocodile"));
    assert_eq!(queue.min_bucket().biggest(), None);
}

注意事项

• 此示例使用两种等价的方式插入项（见上面：搜索 '等价'）

实现说明

如您所见，BucketQueue使用了大量特性以使其更加灵活。这虽然增加了样板代码，但意味着可以添加自定义的队列语义，或者在不同的数据结构上构建现有的语义。

还有一个名为Index的特质，目前只有一个实现，称为SimpleIndex。它实现了维基百科上描述的下限和上限优化。

理论上，可以扩展BucketQueue以使用更好的索引策略，例如使用BinaryHeap或HashMap。要使用自定义的Index，初始化BucketQueue的方式如下

let queue = BucketQueue::<SomeBucket<&str>,MyCustomIndex>::new();

例如

let queue = BucketQueue::<Vec<&str>,MyIndexThatUsesAHeap>::new();

我考虑过探索更好的索引策略，但决定放弃以保持这个项目的范围可控。

最后，有一点需要指出的是，尽管这些在功能上是等效的

queue.bucket(0).bucket(1).enqueue("something");
queue.bucket(0).enqueue("something", 1);

前者有轻微的性能开销。这是因为每次调用bucket时都会构造一个DeferredBucket。在最耗时的基准测试中，这个开销使速度降低了大约7%。对于时间敏感的使用场景，你可以这样做

queue.bucket_for_adding(0).enqueue("something", 1)

这绕过了DeferredBucket，但存在更大的风险，如果意外这样做，Index可能会变得不一致

queue.bucket_for_adding(0).dequeue_min(); // THIS IS WRONG

问题是，你已经通知队列你将添加一个项目，然后删除了一个，将Index置于一个不一致的状态。我考虑是否可以通过一致的方式授予相同的灵活性，而不产生开销，但没有找到这样做的方法。也许有更多经验的Rust泛型和特质的开发者可以做到。

贡献

欢迎所有贡献。截至写作时，我已经使用Rust大约六个月了，所以我相信还有许多改进的空间。请打开一个问题或创建一个拉取请求。如果我没有反应，请在我的Twitter上提醒我@chrispatuzzo。