Използване на Option като итератор

Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Решение на Search от Георги Божинов

Обратно към всички решения

Към профила на Георги Божинов

Резултати

  • 15 точки от тестове
  • 1 бонус точка
  • 16 точки общо
  • 5 успешни тест(а)
  • 0 неуспешни тест(а)

Код

use std::collections::{HashSet, HashMap};
use std::rc::Rc;
macro_rules! set {
($($item:expr),*) => {
{
let mut hash_set = ::std::collections::HashSet::new();
$( hash_set.insert($item); );*
hash_set
}
};
}
pub struct TextIndex {
pub strings: HashMap<String, HashSet<Rc<String>>>,
}
impl TextIndex {
pub fn new() -> Self {
Self { strings: HashMap::new() }
}
pub fn push(&mut self, text: &str) {
let words = extract_words(text);
for word in words {
self.strings
.entry(word)
.or_insert(set!{Rc::new(String::from(text))})
.insert(Rc::new(String::from(text)));
}
}
pub fn search(&self, query: &str) -> HashSet<&str> {
let mut res: HashSet<&str> = HashSet::new();
let words = extract_words(query);
for word in words {
match self.strings.get(&word) {
Some(v) => {
for text in v.iter() {
res.insert(&*text);
}
}
None => {}
}
}
res
}
}
struct WordIterator<'a> {
text: &'a str,
}
impl<'a> WordIterator<'a> {
fn new(text: &'a str) -> Self {
Self { text }
}
}
impl<'a> Iterator for WordIterator<'a> {
type Item = &'a str;
fn next(&mut self) -> Option<Self::Item> {
if self.text.is_empty() {
return None;
}
let mut idx = 0;
for c in self.text.chars() {
if !c.is_alphabetic() {
break;
} else {
idx += 1;
}
}
let mut new_word_idx = idx;
if idx < self.text.chars().count() {
for c in self.text[self.text.char_indices().nth(new_word_idx).unwrap().0..].chars() {
if !c.is_alphabetic() {
new_word_idx += 1;
} else {
break;
}
}
}
let word;
if idx == self.text.chars().count() {
word = self.text;
} else {
word = &self.text[..self.text.char_indices().nth(idx).unwrap().0];
}
if new_word_idx < self.text.chars().count() {
self.text = &self.text[self.text.char_indices().nth(new_word_idx).unwrap().0..];
} else {
self.text = "";
}
if idx == 0 {
return self.next();
}
Some(word)
}
}
pub fn extract_words(text: &str) -> Vec<String> {
WordIterator::new(text).map(String::from).collect()
}

Лог от изпълнението

Compiling solution v0.1.0 (file:///tmp/d20180105-6053-1vr10gi/solution)
    Finished dev [unoptimized + debuginfo] target(s) in 5.46 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

История (2 версии и 4 коментара)

Георги качи първо решение на 26.12.2017 01:31 (преди над 7 години)

Получаваш една бонус точка за итерирането по думи, но индексирането е доста, доста неефективно -- виж коментара, който съм ти написал, и пробвай да го оправиш, и ще ти пусна и другите бонус точки.

Един hint, обаче: тествай си разбиването на думи по-внимателно. Бонус точка ще получиш, но погрижи се да докараш базовите точки също :).

Георги качи решение на 26.12.2017 14:10 (преди над 7 години)

use std::collections::{HashSet, HashMap};
use std::rc::Rc;
macro_rules! set {
($($item:expr),*) => {
{
let mut hash_set = ::std::collections::HashSet::new();
$( hash_set.insert($item); );*
hash_set
}
};
}
pub struct TextIndex {
pub strings: HashMap<String, HashSet<Rc<String>>>,
}
impl TextIndex {
pub fn new() -> Self {
Self { strings: HashMap::new() }
}
pub fn push(&mut self, text: &str) {
let words = extract_words(text);
for word in words {
- match self.strings.clone().get_mut(&word) {
- Some(v) => {
- v.insert(Rc::new(String::from(text)));
- }
- None => {
- self.strings.insert(word, set!{Rc::new(String::from(text))});
- }
- };
+ self.strings
+ .entry(word)
+ .or_insert(set!{Rc::new(String::from(text))})
+ .insert(Rc::new(String::from(text)));
}
}
pub fn search(&self, query: &str) -> HashSet<&str> {
let mut res: HashSet<&str> = HashSet::new();
let words = extract_words(query);
for word in words {
match self.strings.get(&word) {
Some(v) => {
for text in v.iter() {
res.insert(&*text);
}
}
None => {}
}
}
res
}
}
struct WordIterator<'a> {
text: &'a str,
}
impl<'a> WordIterator<'a> {
fn new(text: &'a str) -> Self {
Self { text }
}
}
impl<'a> Iterator for WordIterator<'a> {
type Item = &'a str;
fn next(&mut self) -> Option<Self::Item> {
if self.text.is_empty() {
return None;
}
let mut idx = 0;
for c in self.text.chars() {
if !c.is_alphabetic() {
break;
} else {
idx += 1;
}
}
let mut new_word_idx = idx;
- for c in self.text[idx..].chars() {
- if !c.is_alphabetic() {
- new_word_idx += 1;
- } else {
- break;
+ if idx < self.text.chars().count() {
+ for c in self.text[self.text.char_indices().nth(new_word_idx).unwrap().0..].chars() {
+ if !c.is_alphabetic() {
+ new_word_idx += 1;
+ } else {
+ break;
+ }
}
}
- let word = &self.text[..idx];
- if idx < self.text.len() {
- self.text = &self.text[new_word_idx..];
+ let word;
+ if idx == self.text.chars().count() {
+ word = self.text;
} else {
+ word = &self.text[..self.text.char_indices().nth(idx).unwrap().0];
+ }
+
+ if new_word_idx < self.text.chars().count() {
+ self.text = &self.text[self.text.char_indices().nth(new_word_idx).unwrap().0..];
+ } else {
self.text = "";
+ }
+
+ if idx == 0 {
+ return self.next();
}
Some(word)
}
}
pub fn extract_words(text: &str) -> Vec<String> {
WordIterator::new(text).map(String::from).collect()
}

Така, така, този път се усети :).

Имайки това предвид, все още оставаш само с 1 бонус точка (за индексирането). Начина, по който си имплементирал итерирането по думи сега е доста неефективен, дори и вече да работи за кирилица. Всяко викане на chars().count(), .chars().nth(), и .char_indices().nth(), итерира през целия низ, наново. Целта на задачата е да измислиш как да итерираш по думи ефективно, с едно минаване по низа.