Parsing random phrases from a file

Question

This essentially reads a specially-structured file from the scanner and then parses random phrases and prints them:

{
<start>
<greeting> <object>
}

{
<greeting>
hello
bonjour
aloha
}

{
<object>
world
universe
multiverse
}

Possible random phrases could be: "hello world", "bonjour universe", etc...

Does anyone have some ideas as to how I might decrease the runtime? I heard you could run your code in parallel using multiple threads but was both unsure exactly how to do this and whether it would help at all? The slightest increase in runtime would be beneficial (having a little competition to see who can do it the fastest).

It is not considered cheating so long as I do the majority of the programming, so please just point me in the right direction and provide suggestions.

package comprehensive;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;
import java.util.Scanner;

/**
 * Generates random phrases by reading the specified grammar file 
 * and outputting the number of phrases specified by the user.
 * @author Jun Tang and John Newsome
 *
 */
public class RandomPhraseGenerator {

    public static HashMap<String,ArrayList<String>> map;

    public static void main(String[] args) throws FileNotFoundException{
        Scanner k = new Scanner(new File(args[0]));
        int numPhrases = Integer.parseInt(args[1]);
        addKeys(k);
        while(numPhrases > 0){
            parseStrings();
            numPhrases--;
        }
    }

    /**
     * Assimilates all of the keys and their associated values into map (a public static hashmap).
     * @param scan The scanner that is reading from the specified file.
     */
    public static void addKeys(Scanner scan){
        map = new HashMap<String, ArrayList<String>>();
        while(scan.hasNextLine()){
            if(scan.nextLine().equals("{")){
                String key = scan.nextLine();
                map.put(key, new ArrayList<String>());
                String next = scan.nextLine();
                while(!next.equals("}")){
                    map.get(key).add(next);
                    next = scan.nextLine();
                }
            }
        }
    }

    /**
     * Parses random String phrases from map and prints them. 
     * Must already have assimilated keys and values prior by using the addKeys() method. 
     */
    public static void parseStrings(){
        Random random = new Random();
        StringBuilder strBuf = new StringBuilder((map.get("<start>").get(0)));
        int firstInstance  = strBuf.indexOf("<", 0);
        int secondInstance = strBuf.indexOf(">", firstInstance);
        while(firstInstance >= 0 && secondInstance >= 0){
            String nonTerminal = strBuf.substring(firstInstance, secondInstance+1);
            strBuf.replace(firstInstance, secondInstance+1, (map.get(nonTerminal).get(random.nextInt(map.get(nonTerminal).size()))));
            firstInstance  = strBuf.indexOf("<", firstInstance);
            secondInstance = strBuf.indexOf(">", firstInstance);
        }
        System.out.println(strBuf);
    }
}

Answer 1

I'm no expert in performance optimization or even threads, so my code review will mostly be some style suggestions, but I do have suggestions how I would implement the the phrase building to be faster - purely from my gut :-)

• A nitpick at the beginning: You should try and clean up your indentations. They are all over the place and make reading the code a bit more difficult

• You should declare variables to use interfaces where appropriate instead of concrete class. That makes the code more flexible for example in case you get the keys for a different source. In your case declare your map as Map<String,List<String>>.

• Avoid global variables. If would be better to have addKeys return the map (and thus be renamed readKeys) and pass it on to parseString as an argument.

• In the main function a for loop is probably more appropriate instead of the while.

• Try to get rid of the duplicate scan.nextLine(); in the inner while loop, by moving the exiting condition inside the loop.

Now to optimizing the phrase building. There are two main points I would consider here:

• Avoid copying data. Currently you convert your string with the placeholders into a StringBuilder and insert the text in place of the placeholder. Both creating the StringBuilder and inserting into them requires allot of data copying internally.

• Don't repeat the parsing of the placeholder text. Instead I would parse the text once into a data structure and then generate the random phrases using that structure.

I could write some (pseudo) code to demonstrate, what I mean, but you should be writing it yourself, so I'll wait and see, if you can come up with an implementation based on those two points.