Fast Character Replace Contest

Fast Character Replace Contest

At the office, we have quite a bunch of Java developers. However, because we are quickly growing (way, way, way too quick in my opinion), there was an intake exam created, as part of sourcing in new Java coders from external companies. One of the questions on the intake was an interesting one, so we took it upon ourselves (the existing oldies) to try creating not the most beautiful, but the FASTEST way to get the job done 😉

See github for our quest; github.com/atkaper/contest-java-character-replacer

I started in the lead, but Jan took over and he then was fighting the battle with Milo for a while. But finally Milo did win with the most ugly but fastest way, using the buffer inside an immutable String to be modified to hold the end result. But hey, we said speed… not niceness 😉

The algorithms are all run 5 times, to get the JIT compiler active. At first, I did run it 5 times with the same input, but then clever Milo did win (with 0 ms or 1 ms runtime), because he cached the result of the first run (on a thread local), and returned it in the subsequent runs. So we are running with 5 different inputs now…

Here’s the content of the README file on there, it does explain the contest in further detail;

Contest, find the quickest run/algorithm for converting a “deoxyribonucleic acid” chain. (We keep the abbreviation of the chain on purpose out of this code, this challenge is part of some “exam”… so we do not want to be found on the abbreviation).

Code readability (just for the convert methods) is also nice, but speed was the main challenge here…

The objective is to replace all the characters in the chain, according to these rules:

    A chain consists of 22000000 characters.
    The characters are chosen from (uppercase) A, T, C, G.
    We replace them like this: A by T, T by A, C by G, G by C.

The only methods of importance here are the “convert” implementations. The rest is used to run the different implementations, and do some basic timing.

We write and run this for java 8, 9, and 10.

You can run this using:

javac Contest.java java Contest

Or give one of the run script's a try, after updating for your java path's.

There's an example output in the files “example-run-java[8,9,10].txt”. 

If there’s anyone who has a faster way of doing this (please no libraries, just plain java), then let me know (via contact form, or pull request), and we will add you to the contest.

Thijs.

Leave a Reply

Your email address will not be published. Required fields are marked *