performance - Hashmap 比 string.find 慢？

问题描述

我在 leetcode 中做练习，作为学习 Rust 的一种方式。一项练习涉及找到最长的子字符串，而字符串中没有任何字符重复。

我的第一个想法是将子字符串存储在字符串中并搜索字符串以查看字符是否已经在其中：

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let mut unique_str = String::from("");
        let mut schars: Vec<char> = s.chars().collect();   
        let mut longest = 0 as i32;
        for x in 0..schars.len()
        {
            unique_str = schars[x].to_string(); 
            for y in x+1..schars.len()
            {            
                if is_new_char(&unique_str, schars[y])
                {
                    unique_str.push(schars[y]);
                } else {
                    break;
                }
            }
            let cur_len = unique_str.len() as i32;
            if cur_len > longest {
                longest = cur_len;
            }
        }
        longest
    }
}

fn is_new_char ( unique_str: &str, c: char ) -> bool {
    if unique_str.find(c) == None
    {
        true
    } else {
        false
    }                
}

它工作正常，但性能偏低。希望在“查找”操作上减少几毫秒，我用 HashMap 替换了 unique_str：

use std::collections::HashMap;
impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let mut hash_str = HashMap::new();
        let mut schars: Vec<char> = s.chars().collect(); 
        let mut longest = 0 as i32;
        for x in 0..schars.len()
        {            
            hash_str.insert(schars[x], x);
            for y in x+1..schars.len()
            {            
                if hash_str.contains_key(&schars[y]){
                    break;
                } else {
                    hash_str.insert(schars[y], y); 
                }
            }
            let cur_len = hash_str.len() as i32; 
            if cur_len > longest {
                longest = cur_len;
            }
            hash_str.clear();
        }
        longest
    }
}

令人惊讶的String.find()是，尽管我使用的是相同的算法（或者至少我认为是这样），但在基准测试中，该版本比 HashMap 快 3 倍。直觉上，我会假设在 hashmap 中进行查找应该比搜索字符串的字符要快得多，但结果恰恰相反。

有人可以解释为什么 HashMap 这么慢吗？（或指出我做错了什么）。

标签： performancerusthashmap

解决方案

在性能方面，一项测试总是优于 10 个原因。

use std::hash::{Hash, Hasher};

fn main() {
    let start = std::time::SystemTime::now();
    let mut hasher = std::collections::hash_map::DefaultHasher::new();

    let s = "a";
    let string = "ab";
    for i in 0..100000000 {
         s.hash(&mut hasher);
         let hash = hasher.finish();
    }

    eprintln!("{}", start.elapsed().unwrap().as_millis());
}

我使用调试构建，这样编译器就不会优化我的大部分代码。

在我的机器上，上面的 100M 哈希需要 14 秒。如果我按照一些评论的建议替换为，则需要 17 秒DefaultHasher。SipHasher

现在，带有字符串的变体：

use std::hash::{Hash, Hasher};

fn main() {
    let start = std::time::SystemTime::now();

    let string = "abcde";
    for i in 0..100000000 {
        for c in string.chars() {
            // do nothing
        }
    }

    eprintln!("{}", start.elapsed().unwrap().as_millis());
}

使用字符串中的 5 个字符执行此代码需要 24 秒。如果有 2 个字符，则需要 12 秒。

现在，它如何回答你的问题？...

要将值插入哈希集中，必须计算哈希。那么每次要检查一个字符是否在hashset中，都需要重新计算一个hash。此外，与仅计算哈希相比，检查值是否在哈希集中也有一些小的开销。

从测试中我们可以看出，计算单个字符串的一个哈希值与迭代 3 个符号字符串所花费的时间大致相同。因此，假设您有一个unique_strwith value abcde，然后检查其中是否有x字符。只需使用进行检查会更快HashSet，但是您还需要添加x到集合中，这使得它需要 2 个哈希值来对抗迭代 5 符号字符串。

因此，只要您平均unique_str少于 5 个符号，就可以保证字符串实现更快。在输入字符串的情况下aaaaaaaaa....，它会快约 6 倍，然后是HashSet选项。

当然，这个分析非常简单，可能还有许多其他因素在起作用（如编译器优化和字符串的 Hash 和 Find 的具体实现），但它给出了一个想法，为什么在某些情况下HashSet可能会更慢string.find()。

旁注：在您的代码中，您使用HashMap而不是HashSet，这会增加更多开销，并且在您的情况下不需要...

performance - Hashmap 比 string.find 慢？

问题描述

解决方案

推荐阅读