У меня есть Trie
структура, реализованная в Rust
, которую я взял у кого-то другого, и, кажется, она отлично работает:
pub struct Trie<K, V>
where
K: std::fmt::Debug + Eq + Hash + Clone,
V: std::fmt::Debug + Clone,
{
value: Option<V>,
children: HashMap<K, Trie<K, V>>,
}
impl<K, V> Trie<K, V>
where
K: std::fmt::Debug + Eq + Hash + Clone,
V: std::fmt::Debug + Clone,
{
pub fn new() -> Trie<K, V> {
Trie {
value: None,
children: HashMap::new(),
}
}
pub fn insert(&mut self, path: Vec<K>, v: V) {
if path.is_empty() {
match self.value {
Some(_) => panic!("key exists"),
None => {
self.value = Some(v);
}
}
return;
}
self.children
.entry(path[0].clone())
.or_insert(Trie::new())
.insert(path[1..].to_vec(), v)
}
pub fn fetch_or_default(&self, path: Vec<K>, default: V) -> V {
let value = self.value.clone().unwrap_or(default);
match path.len() {
0 => value,
_ => match self.children.get(&path[0]) {
Some(child) => child.fetch_or_default(path[1..].to_vec(), value),
None => value,
},
}
}
}
У меня есть специальный файл, в котором я инициализирую экземпляр Trieна основе словаря, содержащего 150 тыс. слов, каждому из которых я присваиваю число от 0 до 150.
Данные были сгенерированы с помощью JavaScript, поэтому они не настолько огромны, но по какой-то причине компиляция Rust не может их обработатьи вылетает из памяти, несмотря на то, что у моего компьютера 16 ГБ памяти + 2 ГБ подкачки (которую он полностью использует перед сбоем).
use crate::data::*;
/*
a.reduce((str,ai,i) => { return str + ai.map((w,i) => ` //${w}\n words_trie.insert(vec![' ',${w.split('').reverse().map(c => `'${c==`'`?`\\`:''}${c}'`).join(',')}], ${i});`).join('\n') + '\n' }, '');
*/
pub fn into(words_trie: &mut Trie<char, usize>) {
// SPECIAL LINE, DO NO REPLACE BY ABOVE FORMULA
words_trie.insert(vec![], 150);
// ================================================
//'n
words_trie.insert(vec![' ', 'n', '\''], 0);
...
//(150 000 times a comment followed by an insertion line)
...
}
Я получаю следующее сообщение об ошибке, но это просто убийца OOMна работе:
process didn't exit successfully: `rustc --edition=2018 --crate-name postag_nl_v1 src/main.rs --color always --crate-type bin --emit=dep-info,link -C debuginfo=2 -C metadata=f33cf4c96979227f -C extra-filename=-f33cf4c96979227f --out-dir /home/fremy/Documents/postag_nl_v1/target/debug/deps -C incremental=/home/fremy/Documents/postag_nl_v1/target/debug/incremental -L dependency=/home/fremy/Documents/postag_nl_v1/target/debug/deps` (signal: 9, SIGKILL: kill)
Как я могу инициализировать мой Trie на основе словаря без сбоя компилятора?
[EDIT] Вот минимальное повторение,с фиктивными данными:
https://gist.github.com/FremyCompany/1f6132441338f8b219d961c7254bd8ac#file-main-rs
https://1drv.ms/u/s!AhVrPgyThAkTgQ8v2U99Ffzug7rJ [1Mb zip]