<!-- HTML generated using hilite.me -->
struct Node<T: std::cmp::Ord>
{
key: T,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>
}
struct Tree<T: std::cmp::Ord>{
head: Option<Box<Node<T>>>
}
impl<T> Tree<T>
where T: std::cmp::Ord{
fn new()->Self{
Self{
head:None
}
}
fn insert(&mut self, key:T)->Option<T>{
let mut node:*mut _ = &mut self.head;
unsafe{
while let Some(ref mut v ) = *node{
use std::cmp::Ordering;
match v.key.cmp(&key)
{
Ordering::Equal=>return Some(key),
Ordering::Greater=>{
node =&mut v.left;
},
Ordering::Less=>{
node =&mut v.right;
}
}
}
let new_node = Box::new(Node{key:key, left:None, right:None});
*node = Some(new_node);
}
return None;
}
fn search(&self, key:&T)->Option<&T>{
let mut node = &self.head;
while let Some(ref v ) = *node{
use std::cmp::Ordering;
match v.key.cmp(&key)
{
Ordering::Equal=>return Some(&v.key),
Ordering::Greater=>{
node =&v.left;
},
Ordering::Less=>{
node =&v.right;
}
}
}
return None;
}
}
fn main() {
use std::io::{BufReader};
use std::io::prelude::*;
let mut a = Tree::<String>::new();
let file = std::fs::File::open("./dict.txt").unwrap();
let reader = BufReader::new(file);
for line in reader.lines(){
if let Ok(v) = line{
a.insert(v);
}
}
let file = std::fs::File::open("./search_key.txt").unwrap();
let reader = BufReader::new(file);
use std::time::Instant;
let vec:Vec<_> = reader.lines().filter_map(|it| if let Ok(v)=it{Some(v)}else{None} ).collect();
let start = Instant::now();
for line in &vec{
if let None = a.search(line){
println!("찾지 못함!");
}
}
let end = Instant::now();
println!("{}", end.duration_since(start).subsec_nanos() as f64 / 1_000_000_000f64);
}
내 컴퓨터에서는 0.32초 정도 걸림.
댓글 0