up vote 3 down vote favorite

On performing the following Euler problem, Python takes up less lines and runs faster (Python ~0.05s, Java ~0.3s on my machine).

Could I optimize this Java code in any way? The problem is here

Python:

def main():
    names = open("names.txt", "r").read().replace("\"", "").split(",")
    names.sort()
    print sum((i + 1) * sum(ord(c) - ord('A') + 1 for c in n) for i, n in enumerate(names))

if __name__ == "__main__":
    main()

Java:

import java.util.Arrays;
import java.lang.StringBuilder;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class euler22
{
    public static String readFileAsString(String path) throws IOException
    {
        StringBuilder builder = new StringBuilder();
        BufferedReader reader = new BufferedReader(
                new FileReader(path));
        String buffer = null;

        while((buffer = reader.readLine()) != null)
        {
            builder.append(buffer);
        }

        reader.close();

        return builder.toString();
    }

    public static void main(String[] args) throws IOException
    {
        String[] names = fileAsString("names.txt").replace("\"", "").split(",");
        int total = 0;

        Arrays.sort(names);

        for(int i = 0; i < names.length; ++i)
        {
            int sum = 0;

            for(char c : names[i].toCharArray())
            {
                sum += c - 'A' + 1;
            }

            total += (i + 1) * sum;
        }

        System.out.println(total);
    }
}
share|improve this question
8  
It might just be JVM startup time...hard to compare when runtimes are so short. – Dougal Apr 19 '12 at 3:27
1  
Profile your code, but I think most of the time is spent on reading the input files. You read the file line by line in Java which is slower than reading all at once in Python. – Dikei Apr 19 '12 at 3:32
4  
You simply cannot benchmark a Java program without running the code being benchmarked at least ten thousand times -- enough for the JIT to kick in. Anything else isn't a fair comparison. – Louis Wasserman Apr 19 '12 at 3:37
1  
There are many solutions on the forum for this problem. Did none of them help? BTW: Add to the run time, the time it took you to write the code, to get the total time from when you started to when you had a solution and you might see the runtime doesn't matter in this case. – Peter Lawrey Apr 19 '12 at 5:42
2  
@Louis? Not fair? Why? This code is short enough that it doesn’t need the JIT to kick in. Furthermore, Python hasn’t got one either. The comparison is fair – it’s just not very meaningless precisely because the problem is too small to make a difference in practice. – Konrad Rudolph Apr 19 '12 at 13:12

migrated from stackoverflow.com Apr 19 '12 at 12:26

2 Answers

up vote 3 down vote

As Dougal said: It might just be JVM startup time...hard to compare when runtimes are so short

share|improve this answer
up vote 1 down vote

Broadly speaking try creating less objects. ;)

You can

  • read the entire file as a series of lines or as a string with FileUtils.
  • iterate through each character rather than building an array which you iterate.
  • as the program is so short, try using -client which has shorter start time.

To maximise the performance

long start = System.nanoTime();
long sum = 0;
int runs = 10000;
for (int r = 0; r < runs; r++) {
    FileChannel channel = new FileInputStream("names.txt").getChannel();
    ByteBuffer bb = channel.map(FileChannel.MapMode.READ_ONLY, 0, channel.size());
    TLongArrayList values = new TLongArrayList();

    long wordId = 0;
    int shift = 63;
    while (true) {
        int b = bb.remaining() < 1 ? ',' : bb.get();
        if (b == ',') {
            values.add(wordId);
            wordId = 0;
            shift = 63;
            if (bb.remaining() < 1) break;

        } else if (b >= 'A' && b <= 'Z') {
            shift -= 5;
            long n = b - 'A' + 1;
            wordId = (wordId | (n << shift)) + n;

        } else if (b != '"') {
            throw new AssertionError("Unexpected ch '" + (char) b + "'");
        }
    }

    values.sort();

    sum = 0;
    for (int i = 0; i < values.size(); i++) {
        long wordSum = values.get(i) & ((1 << 8) - 1);
        sum += (i + 1) * wordSum;
    }
}
long time = System.nanoTime() - start;
System.out.printf("%d took %.3f ms%n", sum, time / 1e6);

prints

XXXXXXXXX took 27.817 ms

Its pretty obtuse, but works around the fact its not warmed up.

You can tell this is the case because if you repeat the code in a loop 10000 times, the time taken is only 8318 ms or 0.83 ms per run.

share|improve this answer

Your Answer

 
or
required, but never shown
discard

By posting your answer, you agree to the privacy policy and terms of service.