Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm writing a challenge over at PPCG relating to base conversion of bases 1 to 36, and as a part of the process for writing the competition, I decided to write my own program for it. This is the code I wish to be reviewed:

public class BaseConv {

    // Disallow instantiation
    private BaseConv() {
    }

    // Base setup
    private static final String BASEINFO = "0123456789abcdefghijklmnopqrstuvwxyz";

    /**
     * Converts a string as though it was an integer in base "fromBase" to base
     * "toBase".
     * 
     * @param toConvert
     *            The string to convert bases from.
     * @param startbase
     *            The base to convert from. Must be less than 37 and greater
     *            than 1.
     * @param endbase
     *            The base to convert to. Must be less than 37 and greater than
     *            1.
     * @return converted The converted integer as type String.
     */
    public static String convBase(String toConvert, int fromBase, int toBase) throws NumberFormatException {
        if (toBase > 36 | fromBase > 36 | toBase < 2 | fromBase < 2) {
            throw new NumberFormatException("Bases specified must be less than 36 and greater than 2.");
        }
        String converted = "", thisBase = BASEINFO.substring(0, fromBase);
        char[] argument = toConvert.toCharArray(), baseinfochar = BASEINFO.toCharArray();
        int sum = 0, i = argument.length, multi = 1, baseind;
        for (; i > 0; multi *= fromBase) {
            baseind = thisBase.indexOf(argument[--i]);
                    if (baseind == -1)
                        throw new NumberFormatException("Character " + argument[i] + " is not a valid number in base " + toBase);
                    else 
                        sum += multi * baseind;
        }
        multi = (int) (Math.log(sum) / Math.log(toBase));
        for (i = multi, multi = 1; i > 0; i--)
            multi *= toBase;
        for (; multi >= 1; sum %= multi, multi /= toBase) {
            converted += baseinfochar[sum / multi];
        }
        return converted;
    }
}

I wish to make sure that this code, with its current algorithm, is in the fastest setup possible, as well as being "proper" code (I plan on using this for more formal stuff later).

The current algorithm goes something like this:

  1. The code checks to make sure that it's not attempting to exceed the bounds for possible base conversions.
  2. The code creates its own String and char[] variables from the first Base String, limiting the string to what the input fromBase base is (needn't change the char array size, since we use that specifically for output and it will never go over the specified output base).
  3. The code generates a sum of the numbers by multiplying according to their respective powers of the base.
  4. Calculates the log base toBase of the sum in order to find the largest power that it will be finding (to get rid of fluff).
  5. It then divides the sum by the respective power of the sought base, finding the indexes of the 'BASEINFO' (as a char array for the slightest speed increase) that align with them, and enacting a modulo on the sum to reduce its size.

Note: The PPCG challenge explicitly forbids the use of built-in base conversion methods.

share|improve this question
1  
Do you need to support arbitrary Strings as input? Or is the number in the range of int or long? – Tunaki Feb 28 at 19:26
    
@Tunaki The range is assumed 32-bit signed integer. I suppose I could use BigInteger for sum to support arbitrary size, but I don't think that's necessary. – VoteToClose Feb 28 at 19:27
1  
for starters, you say 1 to 36, but you only accept 2-36 as input. – njzk2 Feb 29 at 2:14

I don't see anything particularly wrong with your code, except that you could benefit from using a StringBuilder to create the String to return, instead of appending to new Strings each time in

for (; multi >= 1; sum %= multi, multi /= toBase) {
    converted += baseinfochar[sum / multi];
}

But, in your case, you need to support only 32-bit signed integer. So it would be way easier to use built-in methods to make that conversion:

public static String convBase(String toConvert, int fromBase, int toBase) {
    return Integer.toString(Integer.parseInt(toConvert, fromBase), toBase);
}

This parses the given String from the given base and converts it back into a String with the target base. Integer.parseInt(s, radix) works for all bases between 2 and 36, like your requirement. It doesn't throw an exception on an invalid base; it defaults to 10, but you could add a simple check for that. Similarly Integer.toString(i, radix) works for base 2 to 36, defaulting to base 10 in case of invalid base.

I ran a JMH benchmark of your current code versus that simple solution on random integers between 0 and 100,000, 1,000,000 and 10,000,000. The benchmark simply converts the number from base 10 to 8; you could make it accross all bases but the result would be pretty much the same. Here are the results:

Benchmark               (length)  Mode  Cnt    Score    Error  Units
StreamTest.convBase       100000  avgt   30  139,514 ± 11,276  ns/op
StreamTest.convBase      1000000  avgt   30  151,537 ±  6,123  ns/op
StreamTest.convBase     10000000  avgt   30  176,489 ±  8,768  ns/op
StreamTest.convBaseInt    100000  avgt   30   51,728 ±  3,473  ns/op
StreamTest.convBaseInt   1000000  avgt   30   54,398 ±  2,329  ns/op
StreamTest.convBaseInt  10000000  avgt   30   64,694 ±  6,240  ns/op

They show that the built-in solution is actually faster than your current code, about 3 times faster. I also ran it with making the StringBuilder change mentioned above but the results were practically the same.

Here's the benchmark code:

import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

@Warmup(iterations = 10, time = 700, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 700, timeUnit = TimeUnit.MILLISECONDS)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Fork(3)
public class StreamTest {

    @State(Scope.Benchmark)
    public static class StringContainer {

        @Param({ "100000", "1000000", "10000000" })
        private int length;

        private String value;

        @Setup(Level.Iteration)
        public void setUp() {
            value = String.valueOf(ThreadLocalRandom.current().nextInt(length));
        }

    }

    private static final String BASEINFO = "0123456789abcdefghijklmnopqrstuvwxyz";

    public static String convBase(String toConvert, int fromBase, int toBase) throws NumberFormatException {
        if (toBase > 36 | fromBase > 36 | toBase < 2 | fromBase < 2) {
            throw new NumberFormatException("Bases specified must be less than 36 and greater than 2.");
        }
        String converted = "", thisBase = BASEINFO.substring(0, fromBase);
        char[] argument = toConvert.toCharArray(), baseinfochar = BASEINFO.toCharArray();
        int sum = 0, i = argument.length, multi = 1, baseind;
        for (; i > 0; multi *= fromBase) {
            baseind = thisBase.indexOf(argument[--i]);
                    if (baseind == -1)
                        throw new NumberFormatException("Character " + argument[i] + " is not a valid number in base " + toBase);
                    else 
                        sum += multi * baseind;
        }
        multi = (int) (Math.log(sum) / Math.log(toBase));
        for (i = multi, multi = 1; i > 0; i--)
            multi *= toBase;
        for (; multi >= 1; sum %= multi, multi /= toBase) {
            converted += baseinfochar[sum / multi];
        }
        return converted;
    }

    public static String convBaseInt(String toConvert, int fromBase, int toBase) {
        return Integer.toString(Integer.parseInt(toConvert, fromBase), toBase);
    }

    @Benchmark
    public String convBase(StringContainer container) {
        return convBase(container.value, 10, 8);
    }

    @Benchmark
    public String convBaseInt(StringContainer container) {
        return convBaseInt(container.value, 10, 8);
    }

}
share|improve this answer
2  
:o Huh. That's something I missed that might be super important for the more formal stuff I do with this, but the source of me doing this in the first place explicitly forbids the use of built-in base conversion methods. Really good to know though, great answer. :D – VoteToClose Feb 28 at 20:20

After a review of some more code style issues, I'll come back to some algorithmic considerations.

Style review

  • Introduce more space into your code – Condensing the code like you've done is great for obfuscating code (and code golfing for bytes). But especially if you want this code to live for some time, and be maintable you should focus on making it readable and understandable. Here are some issues I have where you add space to increase readability:

    • Only one variable on each line – Instead of jamming together all String variables on one line, let each have their own line. Especially when these are calling different initialisers to get the value to store.

      Instead of this code:

      String converted = "", thisBase = BASEINFO.substring(0, toBase);
      char[] argument = toConvert.toCharArray(), baseinfochar = BASEINFO.toCharArray();
      

      I would much rather see:

      String converted = "";
      String thisBase = BASEINFO.substring(0, toBase);
      
      char[] argument = toConvert.toCharArray();
      char[] baseinfochar = BASEINFO.toCharArray();
      
    • Add lines between logical groups of code – I would a blank line inbetween logical group of code. I.e. Add a blank line after the initial validation of parameters, around the variable declarations, around for and/or while loops, and similar other logical groups

    • Don't hide the loop parameters – Looking at these three lines you've hidden the loop parameters:

      int sum = 0, i = argument.length, multi = 1, baseind;
      for (; i > 0; multi *= fromBase) {
         baseind = thisBase.indexOf(argument[--i]);
      

      The initialisation part is found in the middle of the previous line, then end part is OK, the increment part is suddenly something related to multi variable, and the actual incrementation is done in the first line of the loop. All in all, this simple code segment is confusing.

  • Be consistent in indentation – After the preceding code example there is a sudden indentation for the if loop. Be consistent related to indentation level, and don't suddenly introduce a new indentation level.

Algorithmic consideration

I think you might improve on your speed by skipping some unnecessary initialisation which you do for each call, and avoid some calculation which is not needed. But I'm getting ahead of my self, let's talk it through item for item after repeating my understanding of your code:

  • Validate input parameters
  • Initialisation of various parameters used later one
  • Calculate sum the integer version of the number to convert
  • Find the length of the new number
  • Find converted number using modulo operation

Here are my concerns:

  • No need to substring BASEINFO – Why use time to slice down this string. If it's done for veryfying input string, I would rather get the maximum character and check directly on that later on
  • Why convert to char arrays each time? And why the indexOf()? – Instead of doing the toCharArray() on BASEINFO followed by the indexOf() I would rather initialise the BASEINFO directly into the type you need, or even better to make BASEINFO a hashmap where you directly can lookup a character and get the converted value directly.

    Added: Using a hashmap could be a microoptimisation as most of the strings to convert is rather small, see How to map character to numeric position in java? which suggest using indexOf() or simple subtraction (see my solution below).

  • Use StringBuilder instead of string concatenation – The former is supposed to be faster. Or possibly you could use a simpler array for each of the digits, and then convert that later on through a join operation of sorts.
  • Why do you need the length of output? – Instead of using the double loop with the length calculation, you could do with a simple loop just pairing down using the modulo operator until you don't have anything more to convert. See final part of my alternate implementation.

So in short I think you should pre-initialise everything before you start, skip calculations which are not needed, and use StringBuilder for faster build-up of the new string.

Addendum: Alternate implementation

Here is an alternate implementation correcting some of the issues I've mentioned:

class BaseConv {

    // Disallow instantiation
    private BaseConv() {
    }

    // Convert to map
    private static final char[] toMap = "0123456789abcdefghijklmnopqrstuvwxyz".toCharArray();

    public static int convertCharToNum(char ch)
        throws NumberFormatException
    {

        int digitValue = 0;

        // Based on character subtract the correct offset
        if (ch >= '0' && ch <= '9') {
            digitValue = ch - '0';
        } else if (ch >= 'a' && ch <= 'z') {
            digitValue = ch - 'a' + 10;
        } else if (ch >= 'A' && ch <= 'Z') {
            digitValue = ch - 'A' + 10;
        } else {
            throw new NumberFormatException("Character '" + ch + "' is not legal as digit");
        }

        return digitValue;
    }

    public static String convBase(String toConvert, int fromBase, int toBase) throws NumberFormatException {

        // System.out.println("fromBase: " + fromBase + ", toBase: " + toBase + ", toConvert: " + toConvert);

        if (toBase > 36 | fromBase > 36 | toBase < 2 | fromBase < 2) {
            throw new NumberFormatException("Bases specified must be less than 36 and greater than 2.");
        }

        // Find integer value of toConvert
        int intValue = 0;
        int base = 1;

        for (int i = toConvert.length() - 1; i >= 0; i--) {
            digitValue = BaseConv.convertCharToNum(toConvert.charAt(i));

            if (digitValue >= fromBase) {
                throw new NumberFormatException("Found character digit out of range for this base - Character: " + toConvert.charAt(i) + ", value: " + digitValue + ", base: " + fromBase);
            }

            intValue += base * digitValue;
            base *= fromBase;
        }

        // Convert to new base
        StringBuilder converted = new StringBuilder();
        while (intValue > 0) {
            converted.append(toMap[intValue % toBase]);
            intValue /= toBase;
        }

        return converted.reverse().toString();
    }
}

In this alternate implementation I separated the char to digit value into a separate function as well as allowing for A through Z to be used as digits. There are surely more to be done, at least related to adding javadoc's, but it does work in my tests at least! And hopefully it is somewhat easier to read and understand.

share|improve this answer
    
This is a truly fantastic answer, thanks! To address a few points: One of the reasons I hid the loop parameters is that I could reuse them later on in the code (though not for the same purpose); initializing them once made more sense to me. As for the portion relating to "hashmap" - I have not heard of this (although it looks as though I should have). Is there anywhere with a good tutorial on this subject that you would suggest? I'm struggling with the direct documentation. – VoteToClose Feb 28 at 21:37
    
@VoteToClose, You could have stuff like int i in front of the loop as you would use it more than once, but I would still use the for (i = ...; ) in the for loop. Regarding HashMap I might have been a little of (long time since coding in Java), but see the link I provided in the related section, and the alternate implementation where I use another option. – holroy Feb 28 at 22:09

Bug

According to one of the OP's comments, the range of input is 32-bit signed integers. However, this test case:

    System.out.println(convBase("ffffffff", 16, 2));

fails with java.lang.ArrayIndexOutOfBoundsException: -1.

The problem is that sum will be a negative value, and then this loop will start indexing negative values:

    for (; multi >= 1; sum %= multi, multi /= toBase) {
        converted += baseinfochar[sum / multi];

Bug 2

This line is bad for several reasons:

    multi = (int) (Math.log(sum) / Math.log(toBase));

First of all, for negative sums, Math.log(sum) is NaN. The whole expression then evaluates to multi = 0, when it should be the length of the output string. Secondly, for a sum of zero, Math.log(0) is -inf. This makes multi become some large negative number. Lastly, calling Math.log() twice is much slower than just using a loop to compute the number of digits required.

Speed concerns

The slowest parts of your sample program are:

  1. Using indexOf to locate each input character within the BASEINFO string. You could do better by using a dedicated lookup table that converts a char to an int.

  2. Using Math.log() to find the length of the output string. You could just build the output string and later reverse it. Or you could build your output string starting from the end of a buffer and work backwards, and then return a substring of that buffer.

  3. Building the output string using concatenation instead of using a StringBuffer or some other method.

I wrote a version that fixed all 3 of the problems above, and it was faster than the version that uses Integer.parseInt() and Integer.toString(). Since the OP indicated that this was part of some challenge, I'll withhold posting the code until the challenge is over, or until the OP says it's OK to post it.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.