4
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • \$\begingroup\$ If you ask performance questions, you should mention a) what machine you're running on, b) how fast it is now and how fast it has to be. c) What is the sample size? Solutions which are fast with 1000 elements might perform poorly with 1000000 elements. d) Then you have to do some measurements with a profiler, which tells you, where the most amount of time is spent. \$\endgroup\$ – user unknown Apr 27 '11 at 4:29
  • \$\begingroup\$ Yes, unfortunately my teacher did not disclose the sample size or the grammar file that is to be run...Thanks for trying to help though, appreciate it! :) \$\endgroup\$ – Mr_CryptoPrime Apr 27 '11 at 4:52
  • \$\begingroup\$ Your sample file doesn't correspond with the what the program is parsing. The program is obviously looking for curly brackets, which are missing. \$\endgroup\$ – RoToRa Apr 27 '11 at 7:13
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks, that is very helpful! Turns out the competition was actually yesterday, but I will post my updated code and possibly another updated version later. \$\endgroup\$ – Mr_CryptoPrime Apr 27 '11 at 20:20

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.