我开始对一个板条箱进行性能优化，将
我期望这个第二个操作会更快：我可以将集合的前半部分复制出来，然后简单地旋转并缩短原始（现在是第二个）集合的长度。然而，当我运行我的
“Vec”实现需要69.2k ns/iter，而“VecDeque”实现需要91.8k。我已经重复并验证了这些结果 - 为什么使用这种更灵活的数据结构会导致性能下降呢？这些结果是通过运行“cargo bench”获得的。
Vec替换为VecDeque。容器以排序的方式维护元素（它应该相当小，所以我还没有尝试堆），偶尔被分成两个独立的容器（这是我还没有尝试堆的另一个原因），使用drain方法。我期望这个第二个操作会更快：我可以将集合的前半部分复制出来，然后简单地旋转并缩短原始（现在是第二个）集合的长度。然而，当我运行我的
#[bench]测试时，在执行上述操作多次后（以下显示每百万次的纳秒数/迭代次数），我观察到了VecDeque的性能下降：
| 测试a | 测试b | 测试c | 测试d | |
|---|---|---|---|---|
| Vec | 12.6 | 5.9 | 5.9 | 3.8 |
| VecDeque | 13.6 | 8.9 | 7.3 | 5.8 |
一个可重现的示例（gist）：
#![feature(test)]
extern crate test;
use std::collections::VecDeque;
fn insert_in_sorted_order_vec<E: Ord + Eq>(t: &mut Vec<E>, k: E) {
match t.binary_search(&k) {
Ok(i) => t[i] = k,
Err(i) => t.insert(i, k),
}
}
fn insert_in_sorted_order_vecdeque<E: Ord + Eq>(t: &mut VecDeque<E>, k: E) {
match t.binary_search(&k) {
Ok(i) => t[i] = k,
Err(i) => t.insert(i, k),
}
}
fn split_vec<T>(mut t: Vec<T>) -> (Vec<T>, Vec<T>) {
let a = t.drain(0..(t.len() / 2)).collect();
(a, t)
}
fn split_vecdeque<T>(mut t: VecDeque<T>) -> (VecDeque<T>, VecDeque<T>) {
let a = t.drain(0..(t.len() / 2)).collect();
(a, t)
}
#[cfg(test)]
mod tests {
use super::*;
use test::Bencher;
static ITERS_BEFORE_SPLIT: u32 = 50;
static ITERS_TIME: u32 = 10_000;
#[bench]
fn vec_manip(b: &mut Bencher) {
b.iter(|| {
let mut v = Vec::new();
for i in 0..(ITERS_TIME / ITERS_BEFORE_SPLIT) {
for j in 1..(ITERS_BEFORE_SPLIT + 1) {
insert_in_sorted_order_vec(&mut v, i * j / (i + j)); // 'random'-ish illustrative number
}
v = split_vec(v).1;
}
});
}
#[bench]
fn vecdeque_manip(b: &mut Bencher) {
b.iter(|| {
let mut v = VecDeque::new();
for i in 0..(ITERS_TIME / ITERS_BEFORE_SPLIT) {
for j in 1..(ITERS_BEFORE_SPLIT + 1) {
insert_in_sorted_order_vecdeque(&mut v, i * j / (i + j)); // 'random'-ish illustrative number
}
v = split_vecdeque(v).1;
}
});
}
}
“Vec”实现需要69.2k ns/iter，而“VecDeque”实现需要91.8k。我已经重复并验证了这些结果 - 为什么使用这种更灵活的数据结构会导致性能下降呢？这些结果是通过运行“cargo bench”获得的。
- Linux 5.11
- 3900X（12核，3.8-4.6 GHz）
- 32GB 3200 MHz RAM
- rustc 1.55.0-nightly
- 默认的选项（优化，没有调试符号等）
编辑
我将split_vecdeque方法更改为使用split_off而不是drain().collect()（见下文）。看起来这种方法保证不会重新分配或移动任何内容，而只是移动head和tail指针; 请参阅文档和实现。然而，它的性能甚至比原始的VecDeque还要差，为98.2k ns/iter。对于更大的值（ITERS_BEFORE_SPLIT = 50_000，ITERS_TIME = 5_000_000），尽管性能（21.8m ns/iter）优于drain（23.1 ns/iter），但劣于Vec（19.1 ns/iter）。fn split_vecdeque<T>(mut t: VecDeque<T>) -> (VecDeque<T>, VecDeque<T>) {
let a = t.split_off(t.len() / 2);
(t, a)
}
Vec和VecDeque之间的差异，并使其对后者更有利，例如弹出元素从前面开始。由于您似乎没有做任何这方面的工作，并且将VecDeque用作Vec，因此您正在承受使用更复杂类型而不获得其好处的代价。 - user4815162342VecDeque显示出优势吗？ - user4815162342VecDeque相对于Vec而言更加复杂，其索引更难实现。在进行边界检查后，Vec只需要一个单一指针间接访问，而VecDeque需要额外的尾部包装算术运算。因此，我预计二分搜索在Vec上比在VecDeque上更快。但在详细分析您的代码之前，我不想写出确切的答案，而我可能没有时间（和可能也没有足够的知识）进行分析。 - user4815162342VecDeque在支持Vec的每个操作时表现相同，那么拥有这两种数据结构就没有意义了。按需付费：如果您不使用VecDeque的双端性，则使用Vec。 - Peter Hall