patternjavaMinor
Base converting with strings from bases 1 to 36 to bases 1 to 36
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:
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:
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
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:
This parses the given String from the given base and converts it back into a String with the target 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:
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
Here's the benchmark code:
StringBuilder to create the String to return, instead of appending to new Strings each time infor (; 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/opThey 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/opimport 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.