Решение на Search от Георги Ангелов
Резултати
- 15 точки от тестове
- 1 бонус точка
- 16 точки общо
- 5 успешни тест(а)
- 0 неуспешни тест(а)
Код
Лог от изпълнението
Compiling solution v0.1.0 (file:///tmp/d20180105-6053-lbq0f5/solution)
Finished dev [unoptimized + debuginfo] target(s) in 5.63 secs
Running target/debug/deps/solution-3f98bfa5c86a5dd9
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Running target/debug/deps/solution_test-3d9e4ea2eafbbc82
running 5 tests
test solution_test::test_extract_words_basic ... ok
test solution_test::test_extract_words_extra ... ok
test solution_test::test_search_multiple_words ... ok
test solution_test::test_search_special_cases ... ok
test solution_test::test_search_word ... ok
test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Doc-tests solution
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
История (3 версии и 10 коментара)
Георги качи решение на 23.12.2017 14:23 (преди над 7 години)
use std::collections::HashSet;
use std::collections::HashMap;
use std::rc::Rc;
use std::borrow::Borrow;
pub fn extract_words(text: &str) -> Vec<String> {
- text.split( |c: char| !c.is_alphabetic() ).into_iter()
+ text.split( |c: char| !c.is_alphabetic() )
.filter( |s| !s.is_empty() )
.map(String::from)
.collect()
}
pub struct TextIndex {
word_map: HashMap<String, HashSet<Rc<String>>>
}
impl TextIndex {
pub fn new() -> Self {
Self { word_map: HashMap::new() }
}
pub fn push(&mut self, text: &str) {
let words = extract_words(text);
let string = Rc::new(String::from(text));
for word in words {
let word_strings = self.word_map.entry(word).or_insert_with( || HashSet::new() );
word_strings.insert(Rc::clone(&string));
}
}
pub fn search(&self, query: &str) -> HashSet<&str> {
extract_words(query).into_iter()
.filter_map( |word| self.word_map.get(&word) )
.flat_map( |strings| strings )
.map( |string| Rc::borrow(string) )
.map(String::as_str)
.collect()
}
}
Георги качи решение на 23.12.2017 14:41 (преди над 7 години)
use std::collections::HashSet;
use std::collections::HashMap;
use std::rc::Rc;
use std::borrow::Borrow;
+// pub struct WordIterator<'a> {
+// iter: ???
Опитах да направя итератор, който просто композира два други - Split и Filter. Ударих на камък при дефинирането на типа тук.
Има ли лесен начин да се случи това?
+// }
+//
+// impl<'a> WordIterator<'a> {
+// pub fn new(text: &'a str) -> Self {
+// let iter = text
+// .split( |c: char| !c.is_alphabetic() )
+// .filter( |s| !s.is_empty() );
+//
+// WordIterator { iter: iter }
+// }
Хитро решение, но малко пипкаво откъм типове. Един вариант, който докарах, има следната сигнатура:
pub struct WordIterator<'a> {
iter: Filter<Split<'a, fn(char) -> bool>, fn(&&str) -> bool>,
}
Останалата част от кода, разбира се, не работи съвсем с тази типова сигнатура -- разгледай лекциите за callbacks, за да видиш каква е разликата между fn и Fn. След края на срока за домашното, може да обсъдим проблемите, които изникват, ако се мъчим да го имплементираме с closures.
Изненадан съм, че няма удобно решение за композиране на итератори. Мислех си да го излъжа с типови параметри, но не намерих начин от CompositeIterator<T> да стигна до нещо без T-то без да го специфицирам експлицитно, някак да си го infer-не. Май няма как да стане.
Има някакви неща, върху които се работи в nightly, мисля, че случая е добър за impl Iterator: https://github.com/rust-lang/rfcs/blob/master/text/1951-expand-impl-trait.md#motivation. Но дори и в този случай, това се използва за "тип, който се връща от функция", и не работи за полета на структури. Пипкаво е.
+// }
+//
+// impl<'a> Iterator for WordIterator<'a> {
+// type Item = &'a str;
+//
+// fn next(&mut self) -> Option<Self::Item> {
+// self.iter.next()
+// }
+// }
+//
+// trait WordIter {
+// fn words(&self) -> WordIterator;
+// }
+//
+// impl<'a> WordIter for &'a str {
+// fn words(&self) -> WordIterator<'a> {
+// WordIterator::new(self)
+// }
+// }
+
pub fn extract_words(text: &str) -> Vec<String> {
text.split( |c: char| !c.is_alphabetic() )
.filter( |s| !s.is_empty() )
.map(String::from)
.collect()
}
pub struct TextIndex {
word_map: HashMap<String, HashSet<Rc<String>>>
}
impl TextIndex {
pub fn new() -> Self {
Self { word_map: HashMap::new() }
}
pub fn push(&mut self, text: &str) {
let words = extract_words(text);
let string = Rc::new(String::from(text));
for word in words {
let word_strings = self.word_map.entry(word).or_insert_with( || HashSet::new() );
word_strings.insert(Rc::clone(&string));
}
}
pub fn search(&self, query: &str) -> HashSet<&str> {
extract_words(query).into_iter()
.filter_map( |word| self.word_map.get(&word) )
.flat_map( |strings| strings )
.map( |string| Rc::borrow(string) )
Този borrow може ли на теория да вземе референция, която да стане невалидна докато е жива? Ако има метод clear_index, Rc-тата би трябвало да изтрият низа. Какво ще стане тогава ако нещо друго държи референцията?
Ако има метод clear_index, той трябва да вземе mutable reference. Това обаче ще е само възможно, ако няма живи immutable references към структурата или част от нея. Т.е. такъв метод може само да се викне извън scope-а, в който се използват резултатите от search.
Ако все пак ни трябва ownership над резултата от search, винаги може да index.search(...).into_iter().map(String::from).collect()-нем (или нещо подобно), и да получим структура с алокирани копия на низовете. Тогава няма да държим immutable reference към нищо, и спокойно може на следващия ред да трием.
Ах, да. Мерси :)
.map(String::as_str)
.collect()
}
}
Хм, чудя се дали да ти дам 3 точки, заради итератора, но технически погледнато, този итератор не е reusable, така че не мисля, че е това, което търся. Т.е. няма как просто да извикам една функция върху низ, и да получа итериране по думи.
Получаваш 1 бонус точка за ефективното индексиране. Още 2 ще получиш, ако успееш да довършиш енкапсулиран итератор по думи. Hint-а, който ти дадох горе, би трябвало да ти е достатъчен, ако си поиграеш с функциите.
Не съм тук за точките, а и итераторът е закоментиран, така че - не ми ги давай :)
Знам, че мога да го направя с една булева променлива, &str и цикъл, but where's the fun in that.
Damn, fair point, тебе няма да мога да те зарибя с точки. Oh, well :).
Опитах да направя итератор, който просто композира два други -
SplitиFilter. Ударих на камък при дефинирането на типа тук.Има ли лесен начин да се случи това?
Хитро решение, но малко пипкаво откъм типове. Един вариант, който докарах, има следната сигнатура:
Останалата част от кода, разбира се, не работи съвсем с тази типова сигнатура -- разгледай лекциите за callbacks, за да видиш каква е разликата между
fnиFn. След края на срока за домашното, може да обсъдим проблемите, които изникват, ако се мъчим да го имплементираме с closures.Изненадан съм, че няма удобно решение за композиране на итератори. Мислех си да го излъжа с типови параметри, но не намерих начин от
CompositeIterator<T>да стигна до нещо безT-то без да го специфицирам експлицитно, някак да си го infer-не. Май няма как да стане.Има някакви неща, върху които се работи в nightly, мисля, че случая е добър за
impl Iterator: https://github.com/rust-lang/rfcs/blob/master/text/1951-expand-impl-trait.md#motivation. Но дори и в този случай, това се използва за "тип, който се връща от функция", и не работи за полета на структури. Пипкаво е.Този
borrowможе ли на теория да вземе референция, която да стане невалидна докато е жива? Ако има методclear_index, Rc-тата би трябвало да изтрият низа. Какво ще стане тогава ако нещо друго държи референцията?Ако има метод
clear_index, той трябва да вземе mutable reference. Това обаче ще е само възможно, ако няма живи immutable references към структурата или част от нея. Т.е. такъв метод може само да се викне извън scope-а, в който се използват резултатите отsearch.Ако все пак ни трябва ownership над резултата от search, винаги може да
index.search(...).into_iter().map(String::from).collect()-нем (или нещо подобно), и да получим структура с алокирани копия на низовете. Тогава няма да държим immutable reference към нищо, и спокойно може на следващия ред да трием.Ах, да. Мерси :)