1
\$\begingroup\$

The code converts hexadecimal into octal. The function is working, but it takes more than a second to process the input. How can I optimize this?

import java.util.Scanner;
public class BasicTranformSixteenToEight {

    public static void toBinaryTransform(int n, char[][] arry,
            String[] arryBinaryStr) {
        String[] arryOctalStr = new String[10];
        String str = "";
        StringBuilder octalStb = new StringBuilder();
        StringBuilder binaryStb = new StringBuilder();
        String[] arryOctalBinaryStr = { "000", "001", "010", "011", "100",
                "101", "110", "111" };
        for (int i = 0; i < n; i++) {
            arryBinaryStr[i] = "";
            for (int j = 0; j < arry[i].length; j++) { 
                switch (arry[i][j]) {
                case '0':
                    binaryStb.append("0000");
                    break;
                case '1':
                    binaryStb.append("0001");
                    break;
                case '2':
                    binaryStb.append("0010");
                    break;
                case '3':
                    binaryStb.append("0011");
                    break;
                case '4':
                    binaryStb.append("0100");
                    break;
                case '5':
                    binaryStb.append("0101");
                    break;
                case '6':
                    binaryStb.append("0110");
                    break;
                case '7':
                    binaryStb.append("0111");
                    break;
                case '8':
                    binaryStb.append("1000");
                    break;
                case '9':
                    binaryStb.append("1001");
                    break;
                case 'A':
                    binaryStb.append("1010");
                    break;
                case 'B':
                    binaryStb.append("1011");
                    break;
                case 'C':
                    binaryStb.append("1100");
                    break;
                case 'D':
                    binaryStb.append("1101");
                    break;
                case 'E':
                    binaryStb.append("1110");
                    break;
                case 'F':
                    binaryStb.append("1111");
                    break;
                default:
                    break;
                }
                arryBinaryStr[i] = binaryStb.toString();
            }
            if (arryBinaryStr[i].length() % 3 == 1) {  // Correct the Binary in order to convert it into Octal.
                arryBinaryStr[i] = "00" + arryBinaryStr[i];
            } else if (arryBinaryStr[i].length() % 3 == 2) {
                arryBinaryStr[i] = "0" + arryBinaryStr[i];
            }
            arryOctalStr[i] = "";
            for (int j = 0; j < arryBinaryStr[i].length() / 3; j++) { //convert Binary into Octal
                str = arryBinaryStr[i].substring(j * 3, j * 3 + 3);
                for (int k = 0; k <= 7; k++) {
                    if (str.equals(arryOctalBinaryStr[k])) {
                        octalStb.append(k);
                    }
                    arryOctalStr[i] = octalStb.toString();
                }
            }
            str = arryOctalStr[i].substring(0, 1);
            if (str.equals("0")) {  // Remove the first zero and print Octal.
                System.out.println(arryOctalStr[i].substring(1,
                        arryOctalStr[i].length()));
            } else {
                System.out.println(arryOctalStr[i]);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] arry = new char[10][100000];
        String[] arryHexStr = new String[10];

        if (n >= 1 && n <= 10) {
            for (int i = 0; i < n; i++) {
                String number = sc.next();
                if (number.length() <= 100000) {
                    arry[i] = number.toCharArray();
                }
            }
            // binaryTransform(n,arry,arryHexStr);
            toBinaryTransform(n, arry, arryHexStr);
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! This question is incomplete. To help reviewers give you better answers, please add sufficient context to your question. The more you tell us about what your code does and what the purpose of doing that is, the easier it will be for reviewers to help you. See also this meta question. \$\endgroup\$ – Vogel612 Jan 23 '16 at 8:24
  • \$\begingroup\$ Is it a requirement that your function also convert to binary? What is the purpose of the arrayBinaryStr argument? \$\endgroup\$ – JS1 Jan 24 '16 at 3:03
2
\$\begingroup\$

Profiling your code

You could use a profiler to get more insight into what takes up most of the time. Does the program spend much time on calculations, string operations, and/or something else? Are some of these taking longer and/or called more often than you expected?

The NetBeans IDE has the very nice VisualVM tool already built in, which makes it easy to give performance analysis a try. JProfiler and YourKit are popular profilers as well. See this list of Java performance analysis tools on Wikipedia, this blogpost on Java profilers, and this discussion on Stack Overflow for more information.

Processing numbers in six character blocks

To optimize your current code, you could use the fact that six characters from the hexadecimal string can be converted in eight characters for the octal string. If the hexadecimal string does not have a length that is a multitude of six, you can add zeroes in front of it to compensate for that; this will simplify the rest of your program.

Now you can process all the blocks of six hexadecimal characters and convert those into blocks of eight octal characters. The maximum value of a block "FFFFFF" fits in a Java Integer or int, which makes this conversion possible:

Integer.toOctalString(Integer.parseInt(hexadecimalBlockString, 16));

This converts from hexadecimal to decimal to octal, but without using strings. Finally, when a number has been converted to octal, you can strip the leading zeroes of if you want.

For example, this is a single block (the binary strings are only added for clarification and are not calculated during the actual conversion):

hexadecimal: "1    2    3    4    5    6"
binary:      "0001 0010 0011 0100 0101 0110"
------
binary:      "000 100 100 011 010 001 010 110"
octal:       "0   4   4   3   2   1   2   6"

Another approach: BigInteger

Another approach could be to use the BigInteger class:

private void convertHexadecimalToOctal() {
    List<BigInteger> numbers = new ArrayList<>();

    Scanner scanner = new Scanner(System.in);
    int numberCount = scanner.nextInt();

    if (numberCount >= 1 && numberCount <= 10) {
        for (int numberIndex = 0; numberIndex < numberCount; numberIndex++) {
            String hexadecimalNumber = scanner.next();
            if (hexadecimalNumber.length() <= 100000) {
                numbers.add(new BigInteger(hexadecimalNumber, 16));
            }
        }
    }

    for (BigInteger number : numbers) {
        System.out.println(number.toString(8));
    }
}

Some remarks

Some remarks about your code:

  • arry can be an array (or a list) of String
  • as JS1 already mentioned, arryHexStr is not a real parameter since it is not used to pass data to or from the toBinaryTransform method and could be a local variable
  • I would break the toBinaryTransform method up into smaller methods and declare variables closer to where they are used

Some very minor remarks about your code:

  • BasicTransformSixteenToEight instead of BasicTranformSixteenToEight?
  • array instead of arry?
  • hexToOctalTransform instead of toBinaryTransform?
\$\endgroup\$
  • \$\begingroup\$ Thank you! Although it can work,it also takes more than a second to process the input. \$\endgroup\$ – li li Feb 2 '16 at 7:49
  • \$\begingroup\$ Did you analyze the performance with a profiler? You could add an input file to your question to clarify how much work you are trying to do. Do you have a specific performance target? \$\endgroup\$ – Freek de Bruijn Feb 2 '16 at 8:10
  • \$\begingroup\$ Pretty late in testing, I stumbled upon one feature of BigInteger.toString(base): it suppresses leading zeroes, which I would not generally want with hexToOctal. (Regarding speed, do measurements or/and see the end of my answer) \$\endgroup\$ – greybeard Feb 13 '16 at 10:56
  • \$\begingroup\$ Thanks for your input! Yes, BigInteger doesn't store leading zeroes (see stackoverflow.com/a/34746549/1694043). Suppressing unnecessary zeroes seems fine to me, but if I wanted to preserve them, I'm not sure how many there should be (since the hexadecimal string will often be longer than the octal one and since a hexadecimal leading zero is equal to four bits while an octal zero is equal to three bits). When the preferred number of leading zeroes is clear, you could use String.format("%064o", number) to print the BigInteger number (and replace "64" with the desired total length). \$\endgroup\$ – Freek de Bruijn Feb 14 '16 at 21:47
1
\$\begingroup\$
  • You present code that is essentially not documented/commented.

    Foremost, it is difficult to tell whether toBinaryTransform's main purpose is to produce a binary representation (which it assigns via one of its parameter, main never uses, neither title nor text mention) or to print an octal representation to System.out, which it also does and the title sort of singles out. (Or both, which might be an Awful Idea to begin with. If you implement a "multi result method" that strains resources, be sure to let the method know what will not be used.)

  • Prefer functions to void methods.
  • If you modify a parameter's value in a way observable outside a method, document that.
  • Use the runtime's searches until you find cause and time to do better.

  • Regarding performance:

    • Don't instantiate many/big elements without necessity
      String[] arryOctalStr = new String[10] doesn't get exposed or iterated, should have length n or arry.length, if any.
    • In main(), instantiate arry after checking n, with the length "needed": char[][] arry = new char[n][];
    • If you code a search and the first match is as good as the last, stop looking.
    • If you walk an array in steps of, e.g., 3, code it that way:

      binary = binSb.toString();
      //convert binary into octal
      for (int j = 0, n ; j < binary.length ; j = n) {
          n = j + 3;
          str = binary.substring(j, n);
          int k = Arrays.binarySearch(arryOctalBinaryStr, str);
          if (k < 0)
              wail(str + " is weird, or *gone*!");
          else
              octalStb.append(k);
      
    • Do not assign to "result variables" in each iteration of a loop if the only value needed is that after termination.

For micro-benchmarks and profiler runs, I coded a variant closer to the runtime library:

 /** convert an array of hex digits to a String of octal digits,
  *  avoiding <em>one</em> leading 0. */
    public static String hexToOctal(char[]hexDigits) {
        int h = hexDigits.length;
        if (h <= 0)
            return "";
        char[] octalDigits = new char[(h * 4 + 2) / 3];
        int o = octalDigits.length;
        while (3 <= h) { // byte value should do :-/
            int value = (char) hexValues[hexDigits[--h]];
            octalDigits[--o] = (char) ('0' + (value%7));
            value = (value >> 3) + doubleValues[hexDigits[--h]];
            octalDigits[--o] = (char) ('0' + (value%7));
            value = (value >> 3) + quadValues[hexDigits[--h]];
            octalDigits[--o] = (char) ('0' + (value%7));
            octalDigits[--o] = (char) ('0' + (value>>3));
        }
        int value = 0, conv[] = hexValues;
        switch (h) {
        case 2: value = hexValues[hexDigits[1]];
            octalDigits[2] = (char) ('0' + (value%7));
            conv = doubleValues;
        case 1: 
            value = (value >> 3) + conv[hexDigits[--h]];
            octalDigits[1] = (char) ('0' + (value%7));
            octalDigits[0] = (char) ('0' + (value>>3));
        }
        return '0' != octalDigits[0] ? new String(octalDigits)
            : new String(octalDigits, 1, octalDigits.length-1);
    }

 /** char for index */
    final static char[] digitChars
        = new char[9 - 0 + 1 + 'Z' - 'A' + 1];
 /** bit 1<<n set if a power of n<=6 (6*6<=digitChars.length) */
    final static int[] powerOf = new int[digitChars.length];
 /** exponent of base of lowest bit set in powerOf */
    final static int[] exponent = new int[digitChars.length];
    static final int
        digitValues[] = new int[Math.max('z', 'Z')+1],
        hexValues[]   = new int[Math.max('f', 'F')+1],
        doubleValues[]= new int[hexValues.length],
        quadValues[]  = new int[hexValues.length];
    static {
        try {
            for (char i = 0, c = '0' ; i <= 9 ; i++, c++) {
                digitValues[c] = i;
                digitChars[i] = c;
            }
            for (char i = 10, c = 'a' ; c <= 'z' ; i++, c++) {
                digitValues[Character.toLowerCase(c)] =
                    digitValues[Character.toUpperCase(c)] = i;
                digitChars[i] = c;
            }
            System.arraycopy(digitValues, 0,
                hexValues, 0, hexValues.length);
            for (int i = hexValues.length ; 0 <= --i ; ) {
                doubleValues[i] = 2 * hexValues[i];
                quadValues[i] = 4 * hexValues[i];
            }
        // iteration direction makes a difference with exponent:
        // going down, the entries at 4 and 16 end up with their
        // logarithm base 2 (2 and 4) instead of base 4 (1 and 2)
            for (int i = 6, b = 1 << i ; 1 < i ; i--, b >>= 1)
                for (int e=1, p=i ; p < powerOf.length ; p*=i) {
                    powerOf[p] |= b;
                    exponent[p] = e++;
                }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

Indications of work done in the same amount of time in my system, take with an appropriate amount of salt (baseToBase is much the same as hexToOctal, just for "all" conversions that can be done on groups of digits ("2,4,8,16->4,8,16,32"; 3->9,27; 5->25; 6->36; 9->27 and reverse)(and operating from the big end, probably slightly slower than backwards)):

toBinaryTransform  203
hexToOctal        3676
baseToBase        1730
parseLong&toString 981
BigInteger           6

BigInteger comes a surprise - almost all ticks in <init>(?!), would do about 10 times better with construction/parse as costly as toString.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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