我正在從 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 倍，盡管我使用的是相同的演算法（或者至少我是這么認為的）。直覺上，我會假設在哈希圖中進行查找應該比搜索字串的字符快得多，但結果恰恰相反。
Can someone explain why the HashMap is so much slower? (or point out what I am doing wrong).
uj5u.com熱心網友回復：
在性能方面，一項測驗總是比 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 秒。如果我更換DefaultHasher有SipHasher一些意見認為，它需要17S。
現在，帶有字串的變體：
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....，它會比HashSet選項快約 6 倍。
當然，這個分析非常簡單，可能還有許多其他因素在起作用（例如編譯器優化和 Hash 和 Find 字串的特定實作），但它給出了一個想法，為什么在某些情況下HashSet可能會更慢string.find()。
旁注：在您的代碼中使用HashMap而不是HashSet，這會增加更多的開銷并且在您的情況下不需要......
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/314073.html