切片数组或使用 Iterator::skip 效率更高吗？

Question

我想为切片 [0+k .. n] 中的每个元素调用一个函数，其中 k 是偏移量，n 是向量中的元素数。重要的是，我想要原始切片中元素的索引。

我找到了两种方法：

使用enumerate和skip开始的项目

vec.iter().enumerate().skip(k).map(|(i, v)| (f(v), i)).min()

取一个子切片并将偏移量添加到 `enumerate

的索引

vec[k..].iter().enumerate().map(|(i, v)| (f(v), i + k)).min()

在这两种情况下，vec 是字符串向量，f returns 是字符串中的特定字符 (v.chars().nth(offset))。以下哪种解决方案最有效？

Answer 1

让我们以这段代码为例。它与您的示例类似，但更简单一些：

fn main() {
    let items = ["a", "bb", "ccc", "dddd", "eeeee"];
    let k = 3;

    let one = items.iter().enumerate().skip(k).map(|(i, v)| (v.len(), i));
    let two = items[k..].iter().enumerate().map(|(i, v)| (v.len(), i + k));

    // Sanity check that the results are the same
    let items1: Vec<_> = one.collect();
    let items2: Vec<_> = two.collect();

    println!("{}", items1 == items2);
}

哪个性能更好是一个棘手的话题。 Rust 和 LLVM 有很好的优化，可以使代码非常快。

纯粹根据我的直觉，如果我知道我要跳过 "a few" 个项目，我可能会使用第一个，然后第二个，如果我不知道有多少或者很多。

在第一种情况下，从概念上讲，您必须遍历要跳过的所有项目。优化器可能会减少它，但是与 enumerate 和 map 的交互使它变得复杂，所以如果不检查程序集我不会指望它。

第二个 (items[k..]) 使用子切片，这将是一个 O(1) 操作，因为它只是索引到一块内存中。然后你做加法，这也很简单。

但是，唯一真正的测试是进行一些分析。我们将创建一个大型输入数组并开始部分方式：

fn main() {
    let items = ["a", "bb", "ccc", "dddd", "eeeee"];
    let items: Vec<_> = items.iter().cycle().take(10_000_000).collect();

    let k = 371_223;

    // let one = items.iter().enumerate().skip(k).map(|(i, v)| (v.len(), i));
    let two = items[k..].iter().enumerate().map(|(i, v)| (v.len(), i + k));

    // let items1: Vec<_> = one.collect();
    let items2: Vec<_> = two.collect();

    // println!("{}", items1.len());
    println!("{}", items2.len());
}

运行该代码经过优化编译，在 10 次运行中的平均时间如下：

153.6 毫秒
160.1 毫秒

所以，与我的直觉相反，第一个版本更快。我的基准测试完全有可能不正确，但这就是为什么你应该对你的真实代码进行基准测试。

另外，请注意，无论哪种方式，这都是非常快。每项大约需要 15 或 16 纳秒。朋友之间的一纳秒是多少？

切片数组或使用 Iterator::skip 效率更高吗？

Is it more efficient to slice an array or use Iterator::skip?

arrays

monads

vector

slice

rust