5
\$\begingroup\$

I have this code that reads in a "scrambles" and a "words" file. It compares both files using their canonical form and prints out the words from the "words" file that match a particular scrambled word. I'm looking for ways to make this quicker.

public class scramble
{

    public static void main(String[] args) throws Exception
    {
        if (args.length < 2 ) die( "Must pass name of input files on cmd line." );

        BufferedReader scrambles = new BufferedReader( new FileReader( args[1] ) );
        BufferedReader words = new BufferedReader ( new FileReader( args[0] ) );
        ArrayList<String> scramblesList= new ArrayList<String>();  // default initial capacity is 10
        ArrayList<String> wordList= new ArrayList<String>();

        long startTime = System.currentTimeMillis();  // like clicking START on your stopwatch

        while (scrambles.ready())
        {
             String scramble = scrambles.readLine();
             scramblesList.add( scramble );
         }

        Collections.sort( scramblesList );
        while (words.ready())
        {
            String word = words.readLine();
            dictionaryList.add( word );
        }
        Collections.sort( wordList );

        for(String scramble: scramblesList)
        {
            System.out.print(scramble + " ");
                for(String word: wordList)
                {
                if(toCanonical(scramble).equals(toCanonical(word)))
                    System.out.print(word + " ");
                }
        System.out.println();
        }
        long endTime = System.currentTimeMillis();  // like clicking STOP on your stopwatch
        long ms = endTime-startTime;
        System.out.println("Elapsed time in seconds: " + ms/1000.0 + "\n"); // 1 ms is a 1,000th of a second
    } // END MAIN

    private static void die( String errmsg )
    {
                System.out.println( "\nFATAL ERROR: " + errmsg + "\n" );
                System.exit(0);
    }

    private static String toCanonical( String word )
    {
        char[] array = word.toCharArray();
        // #1 declare a char[] array and assign into it the return value from word.toCharArray() 

        Arrays.sort(array);
        // #2 pass that char[] into Arrays.sort(...)
        String C = new String (array);
        // #3 return a new a new String that is constructed using that char[]
            return C; 

    }
}
\$\endgroup\$
  • \$\begingroup\$ I rollbacked your edit. I don't know what you're trying to do, but please do not do this. If you need the content deleted, there are other options. \$\endgroup\$ – Marc-Andre Mar 20 '15 at 17:57
8
\$\begingroup\$

There are a bunch of things in here that @nanny has not yet covered, so let's go through some of those:

  1. Java class names should be CamelCase. Your class scramble should be Scramble.

  2. use whitespace in lines consistently, especially around keywords and operators. Lines like:

    ... wordList= new ....
    

    should be:

    ... wordList = new ....
    

    You have done this correctly in most places, so the places you have it wrong stand out....

  3. There is no need, and it is now discouraged, for you to add the generic type to instance constructor calls. The generic type can be inferred from the target. i.e. your line:

    ArrayList<String> scramblesList= new ArrayList<String>();
    

    should be:

    ArrayList<String> scramblesList = new ArrayList<>();
    
  4. When possible, you should use the interface type for your variables, not the concrete type. For example, the line above should actually be:

    List<String> scramblesList = new ArrayList<>();
    
  5. No need to "type" variable names ... (hungarian notation). We know that scramblesList is a list, so there's no need for the List suffix on scramblesList, it should just be scrambles (good thing we renamed the class to Scramble to avoid confusion...).

  6. 1-liners are a maintenance problem. Sure, they look smart, and take less space, but the person maintaining your code in the furture will dislike you. This:

    if (args.length < 2 ) die( "Must pass name of input files on cmd line." );
    

    should be:

    if (args.length < 2 ) {
        die( "Must pass name of input files on cmd line." );
    }
    
  7. while we are on it, you have successfully turned your Java semantics in to Perl... was that the intention? If so, there's better ways to handle problems like this... an IllegalArgumentException is the better/right solution.

  8. try-with-resources is your friend, learn to use it: try-with-resources

  9. Know your standard libraries... Java can do a lot of what you are doing in it's native libraries. Learn them....

  10. use printf:

    long endTime = System.currentTimeMillis();  // like clicking STOP on your stopwatch
    long ms = endTime-startTime;
    System.out.println("Elapsed time in seconds: " + ms/1000.0 + "\n");
    

    can be:

    long ms = System.currentTimeMillis() - startTime;
    System.out.printf("Elapsed time in seconds: %.3f\n", ms / 1000.0);
    

    Oh, and you have added a \n to a println which seems redundant.

Let Java work for you:

This code throws lots of potential exceptions which you don't handle... and there's a lot simpler ways to do things....:

   BufferedReader scrambles = new BufferedReader( new FileReader( args[1] ) );
    BufferedReader words = new BufferedReader ( new FileReader( args[0] ) );
    ArrayList<String> scramblesList= new ArrayList<String>();  // default initial capacity is 10
    ArrayList<String> wordList= new ArrayList<String>();

    long startTime = System.currentTimeMillis();  // like clicking START on your stopwatch

    while (scrambles.ready())
    {
         String scramble = scrambles.readLine();
         scramblesList.add( scramble );
     }

    Collections.sort( scramblesList );
    while (words.ready())
    {
        String word = words.readLine();
        dictionaryList.add( word );
    }
    Collections.sort( wordList );

The above code, excluding the sorts, and stopwatch, can be replaced with:

List<String> words = Files.readAllLines(Paths.get(args[0]));
List<String> scrambles = Files.readAllLines(Paths.get(args[1]));

As @nanny pointed out, the sorting is unnecessary.

Performance

Once you have your two word lists, the fastest way to match these things is to use a map...., a map of Lists....

Convert the words in to a Map<String,List<String>>:

    Map<String, List<String>> canonWords = new HashMap<>();

    for (String word : words) {
        String canon = toCanonical(word);
        if (!canonWords.containsKey(canon)) {
            canonWords.put(canon, new ArrayList<>());
        }
        canonWords.get(canon).add(word);
    }

Then, with canonWords, search for matches with scrambled words:

    for (String scram : scrambles) {
        String canon = toCanonical(scram);
        List<String> match = canonWords.get(canon);
        if (match != null) {
            System.out.printf("Scramble %s Matches words %s\n", scram, match.toString());
        }
    }
\$\endgroup\$
  • \$\begingroup\$ Your suggestion under "Performance", to use a Map, addresses the fundamental flaw in the original code, that it uses an O(n^2) algorithm. For each scramble in the original program it looks at every word in the words list, so the overall program performance will degrade proportionally to the square of the number of words. That's not terrible, but it can be better. By converting the words list to a Map, the lookup will occur in approximately constant time. If sorting is also removed as you suggest, the program becomes O(n). That's a huge improvement. \$\endgroup\$ – Erick G. Hagstrom Mar 21 '15 at 15:41
7
\$\begingroup\$

Comments

To be blunt, I think all of your comments are really bad, so I'm going to review them first. They're all either redundant or wrong or useless.

// default initial capacity is 10

Are you sure? I don't know Java, but that doesn't sound right. Also, why is that useful information? Even if it is always correct, what's the point of telling the reader?

// like clicking START/STOP on your stopwatch

No, it's like looking at a clock that has millisecond precision and recording the time. Again, this comment adds no information.

// END MAIN

Comments like these usually indicate that your functions are too long or the code is not written with nice indentation or spacing. Speaking of which, you should indent you code more consistently. You IDE likely has a key binding that reindents the entire file.

// 1 ms is a 1,000th of a second

Yep, but I don't know a single person who doesn't know that. Perhaps you were trying to comment on the use of "1000" as a magic number, but I think dividing a variable named "milliseconds" (or "ms") by 1000 is pretty self-explanatory. This gripe is more personal preference than the rest of my answer.

In toCanonical:

// #1, #2, #3

Why bother with these comments? They're just restating exactly what the code is but with more verbosity. Comments are not for translating code into English.

Performance

I don't see any reason to sort the scramblesList or wordsList. That should save a bit of time.

I'm assuming that both lists match up to each other 1-to-1? That is, for each word in the scramblesList there is exactly one match somewhere in the wordsList?

If so, once you find the matching words with this:

if (toCanonical(scramble).equals(toCanonical(word)))

You can break out of the loop:

if (toCanonical(scramble).equals(toCanonical(word)))
{
    System.out.print(word + " ");
    break;
}

Because once you've found a match, you don't need to check the rest of the words. Also, assuming the lists are 1-to-1, you can delete the match from the wordsList, that way the program won't check it again.

What happens when you encounter words like time and item? Say you have both in the wordsList. You'll also have the scrambles miet and eitm. Which scramble matches to which word? How should handle this case? This problem might preclude you from making some performance changes.

Other

String C = new String (array);
    return C;

You can combine this into:

return new String(array);

I'm also unsure of what you mean by "canonical". I do not think it means what you think it means.

\$\endgroup\$
  • \$\begingroup\$ The sorting is to avoid branch prediction issues. You should check this link: stackoverflow.com/questions/11227809/… . Also, I'm not the author of the code and this is purely speculative \$\endgroup\$ – Ismael Miguel Mar 20 '15 at 19:19
  • \$\begingroup\$ @IsmaelMiguel Very interesting link, thanks! \$\endgroup\$ – nanny Mar 20 '15 at 19:34
  • 1
    \$\begingroup\$ @Ismael The tiny tiny amount of time saved avoiding branch-prediction failures is going to be vastly outweighed by doing the sort in the first place. If sorting matters, he should be using a collection which always keeps itself sorted (and which leverages that sorting to speed up searching). He could also pull the call to toCanonical() outside of the inner-loop. \$\endgroup\$ – BlueRaja - Danny Pflughoeft Mar 20 '15 at 22:55
  • \$\begingroup\$ @BlueRaja-DannyPflughoeft Quoting myself: "` this is purely speculative`". \$\endgroup\$ – Ismael Miguel Mar 21 '15 at 0:25
  • 1
    \$\begingroup\$ This code doesn't have a branch prediction issue. The branch is on .equals(), so will only be taken rarely. The "predictor" should and will correctly guess false in the vast majority of cases. Sorting doesn't change that, it just puts the single true in a different place in the list. Kill the sort. \$\endgroup\$ – Erick G. Hagstrom Mar 21 '15 at 15:50

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.