在我的程式中，我有一個巨大的字串串列（非重復），它們與一個單詞交叉。我想檢查這個詞是否有效——它的有效性基于它在串列中的存在。我正在對許多不同的單詞進行此檢查，所以速度是我最關心的問題，還有存盤串列的記憶體效率。
所以我的問題是，什么資料結構最適合對字串集合進行快速查找和記憶體效率？
我目前正在使用 BTreeSet，因為它是有序的，并且我認為它可以加快搜索速度。此外，由于這些詞可能非常相似（“apple”和“app”），我假設基于樹的資料結構在通過 Vec 存盤它們時記憶體效率更高。
uj5u.com熱心網友回復：
如果您需要完全匹配，那么您應該使用HashSet. 它應該比BTreeSet.
但是，如果您需要更復雜的搜索/匹配功能，例如按公共前綴搜索、區分大小寫和不區分大小寫的搜索、大量具有大公共前綴的單詞等，那么 hashmap 將不適合。
在這種情況下，您可以使用trie也稱為prefix tree. 它按字符存盤單詞，從而“壓縮”公共前綴，如果您搜索許多以公共前綴開頭的單詞，這也提供了顯著的加速。
一個非常基本的實作只是散列映射的包裝器：
struct Node {
ptr: HashMap<u8, Node>,
// you can also use a boolean to mark the end of word, but then you would need additional code to rebuild it from the bytes
word: Option<String>,
}
您可以通過遞回地將下一個單詞字符添加到樹中或使用性能更高的迭代方法來將單詞添加到樹中：
pub fn insert(&mut self, word: String) {
let w = word.as_bytes();
let mut node = self;
for ch in w.iter().copied() {
node = node.ptr.entry(ch).or_default()
}
// attach the word
node.word = Some(word);
}
基本的搜索也很簡單：
fn find(&self, word: String) -> Option<String> {
let word = word.as_bytes()
let mut node = self;
for ch in word.iter() {
match node.ptr.get(ch) {
Some(link) => node = link,
None => return None,
}
}
node.word.clone()
}
但是如果你想利用“同時”搜索任何帶前綴的單詞，你應該利用遞回結構，就像這個leetcode 問題
還有一些實作方面的考慮：
- 使用更快的散列函式，因為我們只散列單個位元組，而 rust 中的默認散列函式非常慢
- 您可以在找到節點后從 trie 中“軟洗掉”節點，以加快后續搜索。
您可以在提供的 github 鏈接中找到此類示例
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446402.html