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

hexadecimal java

Question

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

Answer 1

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

Answer 2

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

Answer 3

Character.getNumericValue (char) es otra forma:

char c = ''a'';
System.out.println(c + "->" + Character.getNumericValue(c));

Imprime ''a-> 10'' como desee, por ejemplo. Alguien más tendría que comentar sobre la eficiencia de una llamada de método estático frente a una búsqueda de HashMap, o podría verificarlo usted mismo. Sin embargo, parece más limpio / más legible para mí.

Answer 4

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'']);

Answer 5

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.

Answer 6

Usar una matriz debería ser el más rápido.

Una matriz puede ser de tamaño 16, 16 ^ 2, 16 ^ 3, 16 ^ 4, etc.

Convertir el número en grupos más grandes que uno daría un aumento en el rendimiento.

Habrá un punto ideal donde vale la pena, posiblemente 4 dígitos (tabla de 64k).

Answer 7

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.

Answer 8

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

Answer 9

Amigo, soy programador de microcontroladores y en este pequeño mundo, la velocidad realmente importa. La forma más rápida de convertir un dígito ''ASCII'' en byte (de ''A'' a 0x0A) es usar este pequeño fragmento de código

c|=0x20;
return c<=''9''? c+0xD0 : c+0xA9;

La magia de este comando es simple, si miras la tabla ascii encontrarás números que comienzan con 0x3_ y letras en las columnas 0x4_ y 0x6_ respectivamente. 1) si "o" el carácter entrante (variable "c") con 0x20, nunca cambiará los números ... pero en el caso de las letras, convertirá de mayúscula a minúscula. Como solo buscamos valores A ... F (a ... f) ... no me importan los demás. 2) ahora la magia. Para evitar restas, uso operadores aditivos. el 0xD0 es el mismo de -0x30, y 0xA9 es el mismo de -''a ''+ 10;

¡la instrucción de bifurcación generada por la comparación es bastante simple y no tomó la sobrecarga de las búsquedas de tabla y ni "mod" u otros operadores!

Disfrutar...

Answer 10

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.

Answer 11

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.

Answer 12

Una matriz preinicializada sería más rápida que una HashMap. Algo como esto:

int CharValues[''f''-''0''+1] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, ... -1, 10, 11, 12, ...};
if (c < ''0'' || c > ''f'') {
throw new IllegalArgumentException();
}
int n = CharValues[c-''0''];
if (n < 0) {
throw new IllegalArgumentException();
}
// n contains the digit value

Debe comparar este método con otros métodos (como el método directo de Jon Skeet ) para determinar cuál será el más rápido para su aplicación.