Python vs. Java Runtime on Euler 22 - Name Scores

Question

I want to know why Java is accepted over Python when it comes to runtime. 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 (http://projecteuler.net/problem=22)

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);
    }
}

Answer 1

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.

Answer 2

So, what exactly do you want to know, what is your question? I do not think you have to refactor anything here. Maybe you can push the limits, but first read this (and you should know why java is choosen):

1. Are you counting just the time of program execution (your code does not show this), or the total time of jvm startup, program execution and jvm shutdown (the same for python startup, exec, shutdown). You have to remember that this time differs between different interpreters/jvm's. And it can influence your computation. For such a small problem it will be the main factor.

If you have a bigger problem, that runs for a longer period of time, then the jvm startup does not matter. If your program has to run for a month it does not matter if jvm starts in 1 ms, 1 second or even 1 hour.

Be sure that you know what you want to measure.

1. Java starts by interpreting, which is not the fastest way of runnig programs, and after some time, and hot-spots analysis the Java HotSpot JIT compiler kicks in, and the you will see that the program speeds up.

I have taken your example, and run it a few times (counting the time of each execution). It starts from about 130ms, and after a few cycles it runs in less than 8ms. And I know that file read and access time is a factor also, but after first read the file should be in Operating System cache.