HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Base converting with strings from bases 1 to 36 to bases 1 to 36

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
baseswithconvertingfromstringsbase

Problem

I'm writing a fastest-code 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  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:

  • The code checks to make sure that it's no

Solution

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

}

Code Snippets

for (; multi >= 1; sum %= multi, multi /= toBase) {
    converted += baseinfochar[sum / multi];
}
public static String convBase(String toConvert, int fromBase, int toBase) {
    return Integer.toString(Integer.parseInt(toConvert, fromBase), toBase);
}
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
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);
    }

}

Context

StackExchange Code Review Q#121376, answer score: 4

Revisions (0)

No revisions yet.