recursivo - programa para convertir de hexadecimal a decimal en java




Pregunta de rendimiento: ¿La forma más rápida de convertir caracteres hexadecimales a su valor numérico en Java? (8)

Quiero convertir de char que representa un valor hexadecimal (en mayúscula o minúscula) en byte, como

'0'->0, '1' -> 1, 'A' -> 10, 'a' -> 10, 'f' -> 15 etc...

Voy a llamar a este método con mucha frecuencia, por lo que el rendimiento es importante. ¿Hay una manera más rápida de usar un HashMap<Character,Byte> preinicializado HashMap<Character,Byte> para obtener el valor?

Responder

Parece que es una sacudida entre el uso de un switch-case y la solución informática directa de Jon Skeet; sin embargo, la solución de la caja del interruptor parece oscilar ligeramente. El método de matriz de Greg gana. Aquí están los resultados de rendimiento (en ms) para 200,000,000 ejecuciones de varios métodos:

Character.getNumericValue:
8360

Character.digit:
8453

HashMap<Character,Byte>:
15109

Greg's Array Method:
6656

JonSkeet's Direct Method:
7344

Switch:
7281

¡Gracias chicos!

Código de método de referencia

Aquí tienes, JonSkeet, tu viejo competidor. ;-)

public class ScratchPad {

    private static final int NUMBER_OF_RUNS = 200000000;

    static byte res;

    static HashMap<Character, Byte> map = new HashMap<Character, Byte>() {{
        put( Character.valueOf( '0' ), Byte.valueOf( (byte )0 ));
        put( Character.valueOf( '1' ), Byte.valueOf( (byte )1 ));
        put( Character.valueOf( '2' ), Byte.valueOf( (byte )2 ));
        put( Character.valueOf( '3' ), Byte.valueOf( (byte )3 ));
        put( Character.valueOf( '4' ), Byte.valueOf( (byte )4 ));
        put( Character.valueOf( '5' ), Byte.valueOf( (byte )5 ));
        put( Character.valueOf( '6' ), Byte.valueOf( (byte )6 ));
        put( Character.valueOf( '7' ), Byte.valueOf( (byte )7 ));
        put( Character.valueOf( '8' ), Byte.valueOf( (byte )8 ));
        put( Character.valueOf( '9' ), Byte.valueOf( (byte )9 ));
        put( Character.valueOf( 'a' ), Byte.valueOf( (byte )10 ));
        put( Character.valueOf( 'b' ), Byte.valueOf( (byte )11 ));
        put( Character.valueOf( 'c' ), Byte.valueOf( (byte )12 ));
        put( Character.valueOf( 'd' ), Byte.valueOf( (byte )13 ));
        put( Character.valueOf( 'e' ), Byte.valueOf( (byte )14 ));
        put( Character.valueOf( 'f' ), Byte.valueOf( (byte )15 ));
        put( Character.valueOf( 'A' ), Byte.valueOf( (byte )10 ));
        put( Character.valueOf( 'B' ), Byte.valueOf( (byte )11 ));
        put( Character.valueOf( 'C' ), Byte.valueOf( (byte )12 ));
        put( Character.valueOf( 'D' ), Byte.valueOf( (byte )13 ));
        put( Character.valueOf( 'E' ), Byte.valueOf( (byte )14 ));
        put( Character.valueOf( 'F' ), Byte.valueOf( (byte )15 ));
    }};
    static int[] charValues = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, -1, 10, 11, 12, 13,14,15,-1,-1,-1,-1,-1,-1,-1,-1,-1,
                    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,10, 11, 12, 13,14,15};
    static char[] cs = new char[]{'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','A','B','C','D','E','F'};

    public static void main(String args[]) throws Exception {
        long time = System.currentTimeMillis();
        for( int i = 0; i < NUMBER_OF_RUNS; i++ ) {
            res = getNumericValue( i );
        }
        System.out.println( "Character.getNumericValue:" );
        System.out.println( System.currentTimeMillis()-time );
        time = System.currentTimeMillis();
        for( int i = 0; i < NUMBER_OF_RUNS; i++ ) {
            res = getDigit( i );
        }
        System.out.println( "Character.digit:" );
        System.out.println( System.currentTimeMillis()-time );
        time = System.currentTimeMillis();
        for( int i = 0; i < NUMBER_OF_RUNS; i++ ) {
            try {
                res = getValueFromArray( i );
            } catch (IllegalArgumentException e) {
            }
        }
        System.out.println( "Array:" );
        System.out.println( System.currentTimeMillis()-time );
        time = System.currentTimeMillis();
        for( int i = 0; i < NUMBER_OF_RUNS; i++ ) {
            res = getValueFromHashMap( i );
        }
        System.out.println( "HashMap<Character,Byte>:" );
        System.out.println( System.currentTimeMillis()-time );
        time = System.currentTimeMillis();
        for( int i = 0; i < NUMBER_OF_RUNS; i++ ) {
            char c = cs[i%cs.length];
            res = getValueFromComputeMethod( c );        
        }
        System.out.println( "JonSkeet's Direct Method:" );
        System.out.println( System.currentTimeMillis()-time );
        time = System.currentTimeMillis();
        for( int i = 0; i < NUMBER_OF_RUNS; i++ ) {
            res = getValueFromSwitch( i );

        }
        System.out.println( "Switch:" );
        System.out.println( System.currentTimeMillis()-time );
    }

    private static byte getValueFromSwitch( int i ) {
        byte res;
        char ch = cs[i%cs.length];
        switch( ch ) {
            case '0':
                res = 0;
                break;
            case '1':
                res = 1;
                break;
            case '2':
                res = 2;
                break;
            case '3':
                res = 3;
                break;
            case '4':
                res = 4;
                break;
            case '5':
                res = 5;
                break;
            case '6':
                res = 6;
                break;
            case '7':
                res = 7;
                break;
            case '8':
                res = 8;
                break;
            case '9':
                res = 9;
                break;
            case 'a':
            case 'A':
                res = 10;
                break;
            case 'b':
            case 'B':    
                res = 11;
                break;
            case 'c':
            case 'C':    
                res = 12;
                break;
            case 'd':
            case 'D':    
                res = 13;
                break;
            case 'e':
            case 'E':    
                res = 14;
                break;
            case 'f':
            case 'F':    
                res = 15;
                break;
            default:
                throw new RuntimeException("unknown hex character: " + ch );
        }
        return res;
    }

    private static byte getValueFromComputeMethod( char c ) {
        byte result = 0;
        if (c >= '0' && c <= '9')
        {
            result =  (byte)(c - '0');
        }
        if (c >= 'a' && c <= 'f')
        {
            result = (byte)(c - 'a' + 10);
        }
        if (c >= 'A' && c <= 'F')
        {
            result =  (byte)(c - 'A' + 10);
        }
        return result;
    }

    private static byte getValueFromHashMap( int i ) {
        return map.get( Character.valueOf( cs[i%cs.length] ) ).byteValue();
    }

    private static byte getValueFromArray( int i ) {
        char c = cs[i%cs.length];
        if (c < '0' || c > 'f') {
            throw new IllegalArgumentException();
        }
        byte result = (byte)charValues[c-'0'];
        if (res < 0) {
            throw new IllegalArgumentException();
        }
        return result;
    }

    private static byte getDigit( int i ) {
        return (byte)Character.digit( cs[i%cs.length], 16 );
    }

    private static byte getNumericValue( int i ) {
        return (byte)Character.getNumericValue( cs[i%cs.length] );
    }

}

int CharValues[256] = 
{
16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,
16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,0,1,2,3,4,5,6,7,8,9,16,16,16,16,16,16,16,
16,10,11,12,13,14,15,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,
16,10,11,12,13,14,15,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,
16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,
16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,
16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,
16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16
}

int n = CharValues[c];

if (n == 16)
 throw new IllegalArgumentException();

// n contains the digit value

Aquí está mi versión ajustada del código de Greg. En mi caja es marginalmente más rápido, pero probablemente dentro del ruido. Evita la verificación de límite inferior, y no necesita hacer ninguna resta. Crear una matriz de 64K y evitar una verificación encuadernada parecía ralentizar las cosas, pero de nuevo, con un calendario como este, es prácticamente imposible saber qué es real y qué es ruido.

public class HexParser
{
    private static final byte VALUES = new int['f'];

    // Easier to get right for bozos like me (Jon) than
    // a hard-coded array :)
    static
    {
        for (int i=0; i < VALUES.length; i++)
        {
            VALUES[i] = (byte) -1;
        }
        for (int i='0'; i <= '9'; i++)
        {
            VALUES[i] = (byte) i-'0';
        }
        for (int i='A'; i <= 'F'; i++)
        {
            VALUES[i] = (byte) (i-'A'+10);
        }
        for (int i='a'; i <= 'f'; i++)
        {
            VALUES[i] = (byte) (i-'a'+10);
        }
    }

    public static byte parseHexChar(char c)
    {
        if (c > 'f')
        {
            throw new IllegalArgumentException();
        }
        byte ret = VALUES[c];
        if (ret == -1)
        {
            throw new IllegalArgumentException();
        }
        return ret;
    }
}

No creo que puedas vencer a una búsqueda de matriz directa.

static final int[] precalc = new int['f'+1];
static {
    for (char c='0'; c<='9'; c++) precalc[c] = c-'0';
    for (char c='A'; c<='F'; c++) precalc[c] = c-'A';
    for (char c='a'; c<='f'; c++) precalc[c] = c-'a';
}

System.out.println(precalc['f']);

Una tabla hash sería relativamente lenta. Esto es bastante rápido:

if (c >= '0' && c <= '9')
{
    return c - '0';
}
if (c >= 'a' && c <= 'f')
{
    return c - 'a' + 10;
}
if (c >= 'A' && c <= 'F')
{
    return c - 'A' + 10;
}
throw new IllegalArgumentException();

Otra opción sería probar una declaración de cambio / caso. Una matriz puede estar bien si está en el caché, pero una falla podría ser costosa.


simple, pero lento:

int i = Integer.parseInt(String.ValueOf(c), 16);

Más rápido:

int i = Character.digit(c, 16);

No utilizaré ningún código especial para "problemas de rendimiento". Si realmente usa esto, el JIT creará código compilado y la ejecución será rápida. Mantenga su código limpio. Puede intentarlo y escribir una prueba de rendimiento que compare el tiempo de ejecución con el código anterior y cualquier implementación especial. Apuesto a que no obtendrá mejoras significativas.


Vale la pena señalar que está calculando el tiempo de la operación% en la mayoría de sus pruebas. Esta operación lleva aproximadamente la misma cantidad de tiempo que algunas de las otras opciones.

private static byte lookUpTest(int i) {
    return (byte) cs[i%cs.length];
}

Una tabla de valores de 16 bits donde podría buscar dos dígitos a la vez debería ser más rápida que las matrices de 8 bits sugeridas en otras respuestas. Usted estaría iterando los datos dos veces más rápido, accediendo a la matriz con la mitad de frecuencia, y accediendo a los cortos en lugar de a los bytes, lo que le da a la CPU menos que hacer y más para hacerlo.

Los valores de 8 bits se calcularán previamente como x[Integer.toHexString(i).charAt[0]] = i para 0 <= i < 256 . Luego buscaría x[c] para cada carácter en la cadena hexadecimal. Probablemente desee duplicar las entradas para las variantes en mayúscula y minúscula de cada valor hexadecimal.

Una tabla de valores de 32 bits debería ser incluso más rápida, según la cantidad de espacio que pueda permitirse.


No recuerdo haber visto este método antes, pero Mikko Rantanen señaló esta ecuación en un comentario sobre la pregunta, Código golf - conversión hexadecimal a (binaria) binaria

(char | 32) % 39 - 9

No sé lo que sería un punto de referencia (quizás alguien pueda agregarlo al punto de referencia anterior y ejecutarlo, pero supongo que el% mata el rendimiento), pero es un trazador de líneas sencillo y sencillo para hexadecimal de un solo carácter a conversión decimal Manijas 0-9, AF, af.





algorithm