哈希集比Rust中的蛮力慢

Question

我正在做一些Rust的编码练习。 我发现测试结果有些奇怪。也许我误解了一些东西。

测试结果
在功能中经过的时间是：2.387µs
在功能上经过的时间标签是：24.413µS //为什么需要相对长的时间？
在功能生锈的功能中经过的时间为：1.13µs
测试阵列:: contains_common_item :: test_time_measure ...确定

use std::collections::HashSet;

// O(N^2) O(1)
fn contains_common_item_bruteforce(arr1: Vec<char>, arr2: Vec<char>) -> bool {
    for arr1_item in arr1.iter() {
        for arr2_item in arr2.iter() {
            if arr1_item == arr2_item {
                return true;
            }
        }
    }
    false
}

// O(2N) O(N)
fn contains_common_item_hashset(arr1: Vec<char>, arr2: Vec<char>) -> bool {
    let mut contained_items_map = HashSet::new();

    // iter() iterates over the items by reference
    // iter_mut() iterates over the items, giving a mutable reference to each item
    // into_iter() iterates over the items, moving them into the new scope
    for item in arr1.iter() {
        contained_items_map.insert(*item);
    }

    for item in arr2.iter() {
        if contained_items_map.contains(item) {
            return true;
        }
    }
    false
}

fn contains_common_item_rusty(arr1: Vec<char>, arr2: Vec<char>) -> bool {
    arr1.iter().any(|x| arr2.contains(x)) // contains O(n)
}

#[test]
fn test_time_measure() {
    let arr1 = vec!['a', 'b', 'c', 'x'];
    let arr2 = vec!['z', 'y', 'i'];
    let start = std::time::Instant::now();
    contains_common_item_bruteforce(arr1, arr2);
    let duration: std::time::Duration = start.elapsed();
    eprintln!("Time elapsed in function bruteforce is: {:?}", duration);

    let arr1 = vec!['a', 'b', 'c', 'x'];
    let arr2 = vec!['z', 'y', 'i'];
    let start = std::time::Instant::now();
    contains_common_item_hashset(arr1, arr2);
    let duration: std::time::Duration = start.elapsed();
    eprintln!("Time elapsed in function hashset is: {:?}", duration);

    let arr1 = vec!['a', 'b', 'c', 'x'];
    let arr2 = vec!['z', 'y', 'i'];
    let start = std::time::Instant::now();
    contains_common_item_rusty(arr1, arr2);
    let duration: std::time::Duration = start.elapsed();
    eprintln!("Time elapsed in function rusty is: {:?}", duration);
}

Answer 1

您的测试方法和期望都有一些问题。

首先：优化是可变的，CPU是可变的，缓存是可变的...在合并的测试中运行单个通过，固定值并不考虑这些变量。如果您需要实用的结果，则应使用适当的性能基准测试框架。查看使用 Criterion 。

另外，要么您的计算机很慢，要么您要在调试模式下进行测试。 Rust Playground分别给出210NS，4.25µs和170NS。在调试模式下进行基准测试是相当毫无用处的，因为该性能无法反映出在发行环境中的表现。

---

其次，Hashset声称o（1）访问时间，但是没有免费午餐之类的东西。一方面，这是一个可变大小的集合，必须在使用它之前构建。类似的原油测试表明，仅此步骤的成本与其他两个功能的全部成本高4倍。这将包括分配时间，哈希时间以及Hashset的任何其他记录保存。

您可能会惊讶于Big-O的复杂性，表明Hashset应该表现更好，但是您可能会缺少Big-O符号仅显示正在完成的工作的上限并表达如何表达该工作以n的增长而扩展。在这里，您有固定的4-5个项目集，因此Big-O符号遗漏的固定成本将更加主导（例如HashSet Creation）。而且Big-O符号还列出了每个n实际使用的工作量，它需要更多的工作来计算哈希，查找存储桶，可能处理碰撞并检查是否存在项目；比较两个char S所需要的。 Bruteforce方法的n o（n^2）在标签方法的o（n） 不直接可比。

---

总而言之，如果您的用法意味着对小数据集进行交叉检查检查，那么Bruteforce很有可能会更快。但是，您应该在适当的基准测试中使用现实数据进行验证。