3
\$\begingroup\$

The Task:

The user enters a path to a dictionary file (one word per line) and a phrase as system arguments. My code must then find phrases containing only valid English words, generated by removing one consonant from the user's phrase.

I wrote this as part of an effort to learn Rust, the task is copied from a piece of homework that I had to answer in Java. As such I have written a solution in both Java and Rust, however I was under the impression that Rust was generally faster than Java, but my Java code is significantly quicker. Being new to Rust I don't know what is slowing down my code.

use std::env;
use std::fs::File;
use std::io::BufReader;
use std::io::BufRead;

fn main() {
    let args: Vec<String> = env::args().collect();
    if args.len() == 3 {
        let dict_path = &args[1];
        let mut phrase = args[2].clone();

        let dict_file = File::open(dict_path).expect("Failed to open file");
        let br = BufReader::new(dict_file);
        let dict: Vec<String> = br.lines().map(|l| l.unwrap()
                                                    .to_string()
                                                    .to_lowercase())
                                          .collect();

        let mut num_alter = 0;
        for (i, ch) in phrase.clone().chars().enumerate() {
            if is_consonant(&ch) {
                phrase.remove(i);
                num_alter += print_if_word(&phrase, &dict);
                phrase.insert(i, ch);
            }
        }

        println!("Number of alternatives: {}", num_alter);

    }
}

fn print_if_word(phrase: &String, dict: &Vec<String>) -> u8 {
    let words: Vec<&str> = phrase.split(" ").collect();
    let all_words_match = words.iter().all(|w| dict.contains(&w.to_string().to_lowercase()));
    if all_words_match {println!("{}", phrase); 1} else {0}
}

fn is_consonant(ch: &char) -> bool {
    let consonants = vec!['a', 'e', 'i', 'o', 'u'];
    ch.is_alphabetic() && !consonants.contains(ch)
}

Java Code:

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class LostConsonants {
    private static HashSet<String> dict = new HashSet<>();
    private static final HashSet<Character> CONSONANTS = new HashSet<>(Arrays.asList('q', 'w', 'r', 't', 'y', 'p', 's', 'd',
                                                              'f', 'g', 'h', 'j', 'k', 'l', 'z', 'x', 'c', 'v', 'b',
                                                              'n', 'm', 'Q', 'W', 'R', 'T', 'Y', 'P', 'S', 'D', 'F',
                                                              'G', 'H', 'J', 'K', 'L', 'Z', 'X', 'C', 'V', 'B', 'N', 'M'
                                                              ));

public static void main(String[] args) {
    if (args.length != 2) {
        System.out.printf("Expected 2 command line arguments, but got %d.\n", args.length);
        System.out.println("Please provide the path to the dictionary file as the first argument and a sentence as the second argument.");
        System.exit(1);
    }

    String dictPath = args[0];
    String phrase = args[1];
    vaildWords(dictPath);
    int num = 0;

    StringBuilder phraseBuilder = new StringBuilder(phrase);

    for (int i = 0; i < phrase.length(); i++) {
        Character curr = phraseBuilder.charAt(i);
        if (CONSONANTS.contains(curr)) {
            phraseBuilder.deleteCharAt(i);
            num += printIfWord(phraseBuilder);
            phraseBuilder.insert(i, curr);
        }
    }

    System.out.println(num > 0 ? "Found " + num + " alternatives." : "Could not find any alternatives.");

}

static int printIfWord(StringBuilder phrase) {
    String[] words = phrase.toString()
            .replace("[.,]", "")
            .toLowerCase()
            .split(" ");
    if (Stream.of(words).allMatch(dict::contains)) {
        System.out.println(phrase);
        return 1;
    } else {
        return 0;
    }
}

static void vaildWords(String dictPath) {
    try (BufferedReader reader = new BufferedReader(new FileReader(dictPath))) {
        reader.lines().map(String::toLowerCase).forEach(dict::add);
    } catch (FileNotFoundException e) {
        System.out.printf("File not found: %s (No such file or directory)\n", dictPath);
        System.out.println("Invalid dictionary, aborting.");
        System.exit(1);
    } catch (IOException e) {
        e.printStackTrace();
        System.exit(1);
    }
}
}
\$\endgroup\$
  • 1
    \$\begingroup\$ while knowing nothing about rust, I will say that is_consonant looks inefficient. Use a hash type rather than an array, and store the list of consonants to avoid a call to is_alphabetic. Define consonants such that it's only initialized once, not on every call. Also make sure that phrase.remove + phrase.insert is faster than moving phrase.clone inside the loop (and discarding the modified phrase). \$\endgroup\$ – Oh My Goodness Feb 24 at 5:38
  • 1
    \$\begingroup\$ I'd say the biggest thing I see is that dict should be a HashSet. Seeing the Java code would make it easier to compare, so we know what to critique regarding the algorithm itself vs how it was translated. \$\endgroup\$ – JayDepp Feb 25 at 6:17
1
\$\begingroup\$

In terms of comparing the two implementations, I only see two differences.

Your Java code uses a HashSet for dict while your Rust code uses a Vec. Since the desired use of dict is simply lookups, a HashSet is indeed the best data structure to use. This change is very easy to make, mostly since collect is a generic method. You can simply change the type of dict to HashSet<String> and the words will be collected into a hashset. This should result in a very large improvement, assuming your dictionary is sufficiently large.

The other difference is with is_consonsant. I don't see this change being very significant. I think the way you're doing it in the Rust implementation may actually be faster, especially if you use is_ascii_alphabetic instead. My reasoning for this is that a linear search through an array is typically faster than a hashset when the number of elements is very small. An array-based static lookup table would probably be best anyways. Overall though, this optimization is likely insignificant and only if you need this boost, you should benchmark different approaches.

Here's how I might write this program, with some comments for explanation. (Note: I compiled this but didn't actually test it.) If you have any questions about why I do something a certain way, feel free to ask.

use std::collections::HashSet;
use std::env;
use std::fs::File;
use std::io::BufRead;
use std::io::BufReader;

pub fn main() {
    let args: Vec<String> = env::args().collect();
    if args.len() != 3 {
        // eprintln prints to stderr
        eprintln!("Expected 2 command line arguments, but got {}.", args.len() - 1);
        eprintln!("Please provide the path to the dictionary file as the first argument and a sentence as the second argument.");
        return;
    }

    let dict_path = &args[1];
    let phrase = &args[2];

    let dict_file = File::open(dict_path).expect("Failed to open file");
    // You can collect into a hashset
    let dict: HashSet<String> = BufReader::new(dict_file)
        .lines()
        .map(|l| l.unwrap().to_string().to_lowercase())
        .collect();

    let mut num_alter = 0;
    let mut phrase_alter = phrase.to_string();
    for (i, ch) in phrase.chars().enumerate() {
        if is_consonant(ch) {
            phrase_alter.remove(i);
            num_alter += print_if_word(&phrase, &dict);
            phrase_alter.insert(i, ch);
        }
    }

    println!("Number of alternatives: {}", num_alter);
}

// &str is almost always prefered over &String
fn print_if_word(phrase: &str, dict: &HashSet<String>) -> u8 {
    // No need to collect to a vector, just chain iterator methods.
    let all_words_match = phrase
        .split_whitespace()
        .all(|w| dict.contains(&w.to_string().to_lowercase()));
    if all_words_match {
        println!("{}", phrase);
        1
    } else {
        0
    }
}

// prefer taking by value instead of reference whenever the type is Copy and reasonably small
fn is_consonant(ch: char) -> bool {
    // Since your Java code only allowed ascii consonants, I will do the same here.
    if !ch.is_ascii() {
        return false;
    }

    // Fastest solution is most likely a static lookup table like
    // static CONSONANT: [bool; 256] = [false, false, ...];
    // However, the solution below is reasonably fast and is likely
    // dwarfed by other costs in the program.

    let b = (ch as u8).to_ascii_lowercase();

    b.is_ascii_lowercase()
        && match b {
            b'a' | b'e' | b'i' | b'o' | b'u' => false,
            _ => true,
        }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.