Skip to content

Instantly share code, notes, and snippets.

@kenwuuu

kenwuuu/rust benchmark: 466k word file load and sort

Last active April 12, 2023 21:05
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save kenwuuu/88e272f6c0ea0034b6baeca8a9eba9f6 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save kenwuuu/88e272f6c0ea0034b6baeca8a9eba9f6 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
rust benchmark: 466k word file load and sort
use std::collections::HashMap;
use std::fs::File;
use std::io::{BufRead, BufReader};
use rand::seq::SliceRandom;
use std::time::Instant;
// This function takes a query string, a vector of possible queries, and a maximum number of suggestions to return.
// It returns a vector of strings containing all the possible queries that start with the given query string, up to the maximum number of suggestions.
fn autocomplete_fast(query: &str, possible_queries: &[String], max_suggestions: usize) -> Vec<String> {
// Convert the query string to lowercase.
let query = query.to_lowercase();
// Create an empty vector to store the matches.
let mut matches = Vec::new();
// Iterate over all possible queries.
for possible_query in possible_queries {
// If the possible query starts with the lowercase query string,
if possible_query.to_lowercase().starts_with(&query) {
// Add the possible query to the matches vector.
matches.push(possible_query.to_string());
// If we have reached the maximum number of suggestions,
if matches.len() >= max_suggestions {
// stop iterating.
break;
}
}
}
matches
}
// This function takes a filename and reads each line of the file as a string, adding it to a vector of strings.
// It returns the vector of strings containing all the lines of the file.
fn read_words_file(filename: &str) -> Vec<String> {
// Create an empty vector to store the words.
let mut words_list = Vec::new();
// Open the file with the given filename and create a buffered reader.
let file = File::open(filename).expect("failed to open file");
let reader = BufReader::new(file);
// Iterate over all lines of the file.
for line in reader.lines() {
// Read the line as a string and trim any leading or trailing whitespace.
let word = line.expect("failed to read line").trim().to_string();
// Add the word to the words vector.
words_list.push(word);
}
words_list
}
fn search(query: &str) -> Vec<(&'static str, f64)> {
// start timer
let start_time = Instant::now();
// read words file
let filename = "words.txt";
let mut words_list = read_words_file(filename);
let file_read_end_time = Instant::now();
let file_read_time = (file_read_end_time - start_time).as_secs_f64();
// randomly shuffle word list
words_list.shuffle(&mut rand::thread_rng());
let shuffle_end_time = Instant::now();
let shuffle_time = (shuffle_end_time - file_read_end_time).as_secs_f64();
// Sort the list of words
words_list.sort();
let sort_end_time = Instant::now();
let sort_time = (sort_end_time - shuffle_end_time).as_secs_f64();
// Get the query from the user
// print!("query: ");
// io::stdout().flush().unwrap();
// let mut query = String::new();
// io::stdin().read_line(&mut query).expect("failed to read line");
// let query = query.trim();
// You can set the desired number of suggestions here or ask the user for input.
let max_suggestions = 500;
// Slice the words_list based on the first character of the query
// This speeds up the search by preventing autocomplete_fast() from
// iterating the entire length of the list to get to the latter strings
let search_start_time = Instant::now();
let first_char = query.chars().next().unwrap();
let lower_bound = words_list.binary_search_by_key(&first_char.to_string(), |s| s.chars().next().unwrap().to_string()).unwrap_or_else(|x| x);
let upper_bound = words_list.binary_search_by_key(&((first_char as u8 + 1) as char).to_string(), |s| s.chars().next().unwrap().to_string()).unwrap_or_else(|x| x);
// Search for the query
let sliced_words_list = &words_list[lower_bound..upper_bound];
let suggestions = autocomplete_fast(query, sliced_words_list, max_suggestions);
let search_end_time = Instant::now();
let search_time = (search_end_time - search_start_time).as_secs_f64();
let total_time = file_read_time + shuffle_time + sort_time + search_time;
// print suggestions
println!("{:?}", suggestions);
// push times to vector
let mut times = Vec::new();
times.push(("File read time: ", file_read_time));
times.push(("Shuffle time: ", shuffle_time));
times.push(("Sort time: ", sort_time));
times.push(("Search time: ", search_time));
times.push(("Total time: ", total_time));
return times;
}
fn main() {
// call search function n times, and add each time to a vector
let run_times = 50;
let mut total_times = HashMap::new();
total_times.insert("File read time: ", 0.0000);
total_times.insert("Shuffle time: ", 0.0000);
total_times.insert("Sort time: ", 0.0000);
total_times.insert("Search time: ", 0.0000);
total_times.insert("Total time: ", 0.0000);
for i in 0..run_times {
println!("Run {}:", i + 1);
let times = search("x");
total_times.insert("File read time: ", total_times.get("File read time: ").unwrap() + times[0].1);
total_times.insert("Shuffle time: ", total_times.get("Shuffle time: ").unwrap() + times[1].1);
total_times.insert("Sort time: ", total_times.get("Sort time: ").unwrap() + times[2].1);
total_times.insert("Search time: ", total_times.get("Search time: ").unwrap() + times[3].1);
total_times.insert("Total time: ", total_times.get("Total time: ").unwrap() + times[4].1);
}
// print average times
println!("Iterations: {}", run_times);
println!("Average times:");
for (key, value) in total_times {
println!("{}: {:.4}", key, value / run_times as f64);
}
}
Raw
words
used words.txt from https://github.com/dwyl/english-words
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment